beet's soil

競プロのことなど

CODE FESTIVAL 2016 Final - Day 2

おつかれさまでした!!
1日目 -> CODE FESTIVAL 2016 Final - Day 1 - beet's soil

〜会場

n度寝していたら時間がやばくなった。
TLEしなかったので実質AC(?)

トーナメント

30分のコンテスト*3という精神力をゴリゴリ削られる闘いだった。

【Round 1】

AはなんかMSTやるっぽかったのでprimを書こうとしたらdijkstraになってしまった。
諦めてBの100点を取ろうとしたけどなぜか全然合わない。
minとmaxを間違えていた()。直して100点。全探解を書いて200点。終了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inf= 1<<28;
string s;
ll rec(ll p,ll m,ll k){
  ll res = inf,x=0;;
  if(k){ 
    for(ll i=p;i<s.size();i++){
      x=x*10+s[i]-'0';
      res=min(res,rec(i+1,max(m,x),k-1));
    }
  }else{
    for(ll i=p;i<s.size();i++) x=x*10+s[i]-'0';
    return max(m,x);
  }
  return res;
}
int main(){
  ll k,ans=0;
  cin>>k>>s;
  if(s.size()>100) return 0;
  cout << rec(0,0,k) << endl;
  return 0;
}

なぜか通ってしまったのでRound2へ。

【Round 2】

B部分点がやるだけなので通す。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m,i,j,k,ans=0;;
  cin>>n>>m;
  ll st[n][m];
  for(i=0;i<n;i++)
    for(j=0;j<m;j++)
      cin>>st[i][j];
  bool ok=1;
  for(i=0;i<n-1;i++) ok&=(st[i][0]<=st[i+1][0]);
  if(!ok){
    cout << -1 << endl;
    return 0;
  }
  for(i=0;i<n-1;i++){
    while(1){
      bool f=1;
      for(j=0;j<m;j++){
	if(st[i][j]>st[i+1][j]){
	  f=0;
	  break;
	}
	if(st[i][j]<st[i+1][j]){
	  break;
	}
      }
      if(j==m) f=0;
      if(f) break;
      for(j=1;j<m;j++) st[i+1][j]+=st[i+1][j-1];
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Aが確率DPであってなったけど一つ目の制約が100%だったのでちょっと考えて出す。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll x,p,i,j,k;
  cin>>x>>p;
  if(p!=100) return 0;
  printf("%.8lf\n",(double)((x-1)/2+1));
  return 0;
}

もう一つの部分点を取ろうと愚直解を書いたが誤差死。
Bが早めに解けていたのでRound3へ。

【Round 3】

劇冷え(完)
DP解を書いたら初期化の部分で落ちたっぽい(なぜだかわからない。
もし通っていたらステッカー揃っていたので悔しかった。

楽しかったけどアホみたいに疲れた(褒め言葉
時間制限が短い中でどう立ち回るのかが重要になってくるなあと思った。

LT & rngさんトーク

  • 幅優先探索は忍者わかる
  • ハンドスプリングは自然(?)
  • 東大生のコンテンツ力
  • 座布団は積み上げるもの

チームリレー

ei1333さんと同じチームだったので話しかけようかと思ったけど話題もないのでやめた。
同じサブグループになれたので問題を解く中で交流(?)できてよかった。

Fを担当したんですけど塩弟さんの考察力が凄すぎて5分ぐらいで解法が降ってきた。
Gの考察を手伝うなどしていた。

肝心の実装では*と+を間違えて1WA(ギルティ
横着してpowを使ってまた1WA
なんとか3回目で通せました(後半の中では一番実装量少ないのにドウシテコウナッタ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll x;cin>>x;
  cout << (1LL<<(x+2LL)) - 2LL << endl;
  return 0;
}

F通してすぐぐらいにei1333さんがGを通していた。
塩弟さんがHを直接送信フォームで実装していてやばかった(しかも一発AC
fatalさん、huziwaraさんは一人でそれぞれ最後の二問を通していて流石のプロという感じ。
いつのまにか残りがIだけになっていてみんなで考えていた。
奇数の時は自明なので分割して逆向きにするみたいな解法ができたのでkobaさんが実装し始める。
WAが取れなくてHuziwaraさんが確認したらreturn文が抜けていた。プロ。
ややこしい構築ゲーなのにしっかり通して全完!!チーム2位でした。

しばらく順位表を眺めるなどしていた。
1位のチームは特別なTシャツをもらっていて羨ましかった。
best collaboration賞でマグカップをもらった。

魔剤が大量に用意されていた。
f:id:beet_aizu:20161128235529j:plain

表彰式

  • アカウント
  • 劣モ
  • 十億七
  • 69cm

その後

eiの方達と夕食をとった。おいしかった。
JOIとかPCKの話を聞きながらもっと早く始めてればなあという気持ちになった。
さてさんがPCを忘れていた。(4人もPCを忘れていたけど全員に連絡ついたようでよかった。)

新幹線が激混みだったので結局終電で帰ることになって時間を潰すためにあんみつを食べた。
東京はなんでもおいしくてすごいなあという感じ。
f:id:beet_aizu:20161128235550j:plain

今日の試験のために過去問を解いて勝利を確信するなどしていた。
指定席は必ず座れるので神。

終わりに

色々な人を見れて面白かった(知り合いになれたとは言ってない)。
recruitさん、indeedさん、atcoderさんに圧倒的感謝✊
来年もぜひ参加したいです!!!