rickytheta's blog

競プロ

CODE FESTIVAL 2016 本戦 参加記 #CODE_FESTIVAL

去年に引き続き2回目の参加でした。楽しかった。

朝

去年同様の若干の遅刻でした。

着いてすぐにお昼ごはんを食べました。今年はTシャツの説明をちゃんと聞けたためTシャツが恵まれました。

本戦

今年のパーカーボーダーは1600点。

結果はABCDF+E部分+H部分で3700点(全体33位、国内15位)でした。去年に比べたら成長を感じられる結果。以下解答方針。

A

書きました。cin>>sしながらチェックするだけでとても楽。

B

N<=107なのでO(NlogN)が怪しい気がしたんですけど大丈夫でした。多分「メモリアクセスは√Nと考えるべき」みたいなのが効いてるんだと思う(つまりメモリアクセスが無い分若干大きい計算量見積もりでも大丈夫という意味)。

使える数の上限を決め打ちすると貪欲に取れるので、それで二分探索しました。

C

結局「同じ言語話せる人たちをuniteしたUFで全部連結になるか」ってことなのでUFを書いて提出。誤読が多かったらしい(この日は珍しく誤読しなかった)。

D

サンプルでも分かる通り、mod MがiとM-iのものをできるだけ組み合わせるほうが良い。

まずmodMで分けて、組み合わせて、余ったやつの中で同じ数のやつを組み合わせる、ということを貪欲っぽくやる。4WA。

E

部分点のみ。dp[i] := 速度iで始めてN枚クッキーを焼けるまでの最短時間 というDPを考える。

dp[i] = max( (N+i-1)/i, max{ j+A+dp[j*i] } ) という更新式を考えるとO(NlogN)。対数は自然数の逆数和。

F

DP。「A:頂点0から行き来可能な頂点」「B:未訪問の頂点」「C:訪問済みだけど行き来可能にはなってない頂点」の状態で考える。

この3つをキーにすると空間O(N3)時間O(MN3)っぽく見えるけど、1つのキーはNから他の2つのキーの値を引けば求まるのでNが一個落ちる。

Aに移動する場合はCの頂点がAに追加される。Bに移動する場合はBが1つCに遷移する。Cに移動する場合は変化なし。という感じでDPの漸化式を求めるとOK。

H

この時点でEの満点を考えつつ順位表を見るとHの部分点があることに気付いたので着手。

部分点は数列A上でのゲームなのでDP。

dp[i] := 自分がi、相手がi+1の場所にいる場合の最適なスコア と定義して漸化式を考える。

j>=i+2にジャンプすることが出来るので、大きい方から求めていってmaxを取っていけば良い。segment treeは不要。

残り時間

E満点、H満点、Gを考えていました。

E満点については「数を掛け算してN以上を作る」という発想はあったのですが、DPの考えが抜けず割り算をするDPだと思いこんでいたのが失策。

H満点はDPの式をもうちょっといじると満点に繋がったらしいので考察力が足りないんだなぁと実感しました。

Gは考察はだいぶいい線いってたと思うんですけど考察と実装どっちがミスっていたのか今でもはっきりわかってないです(Gを通せていたら20位or21位だったのでかなりへこんでいる)。

無事パーカーをもらえました。今回は事故が多発したらしくパーカーボーダーが高かった。

夜

7歳で競プロ始めたガチプロやばい。

講演の後は東工大15勢で🍕🍕🍣🍣🍕🍣🍣したり書道したりしていました(エンディングムービーに書道の光景が若干写っていた)(phi氏は賞ももらっていた)。

エキシビションパラレルも一応出ていたのですが、脳が停止していたので考察漏れ多数でダメでした。

その後はリレーで英語話せない辛いを多発しつつホテルに行きました。

今年は短縮王も無くやることがTwitterとTypingWarぐらいしか無かったのでポットの水を沸かしてお茶をいれることにしたのですが、

WAをたくさん出しました。

2日目朝

最近はリポビタンDにはまっています。

トーナメント

今年はあさプロではなくトーナメントが行われました。本戦順位が近い人同士で刺し合う血祭り。

30分2問なので早解き有利でした。

Round1及びRound2で0完でした。部分点すらない……

Round1 A

どう見てもMST+ダブリングLCAクエリです本当にありがとうございました。とD: たこ焼き屋とQ人の高橋君 - AtCoder Regular Contest 048 | AtCoderのソースを持ってきます。

めっちゃ古かったので使い方を完全に間違えてバグらせました。終了。

その後はパラレルで並走してましたが、Round2Aを眺めてはバグらせ、Round3Aを眺めてセグ木を書いてはTLE、スライド最小値を書いてはDPの初期化をミスってWAと散々でした。Round3Bは終わってから読んだのですがパット見D: Median Pyramid Hard - AtCoder Grand Contest 006 | AtCoder感がある。

昼

いくらと聞いてテンションが上がっていましたが速攻で完売。競プロ勢は🍣といくらが好物。

ご飯(とんかつ)を食べた後はchokudaiさんの生ハンドスプリングを見てrngさんの謎クイズを見て昼の部を終了しました。

リレー

お　　　ま　　　た　　　せ

今回は33位で海外勢抜いてチーム内最高順位なので一体どんな難しい問題が来るんだとめっちゃ緊張してました。

私はJを担当しました。リレー中の流れとしては、Jを考えた後、Iをみんなで考えていました。

J

N*Nのチェスボード( (i,j)はi+jが偶数なら黒、奇数なら白に塗られている)があるので、適切に白いマスを黒く塗って黒いマスを連結にしろという問題。N<=1000、黒く塗れるマスの数の制限が170000個。

これは割と簡単で、一番上の行と一番右の列をまず黒く塗って(N個ぐらい)、それから3列に1列を黒く塗っていけばOK(N2/6個ぐらい)。合計すると1000+166666=167666で問題なし。(行と列の内半分はすでに黒く塗られている点に注意)

I

N<=100で、条件を満たす写像をN-1個作れという問題。f_i(x)を写像とすると(1<=i<=N-1, 1<=x<=N)、

  • 全てのxについて、 f_i(x) != x
  • 全てのxについて、 i != j ならば f_i(x) != f_j(x)
  • 全てのiについて、 f_i(f_i(x)) != x

というのが条件。

解けてないのと疲れたので詳細には書かないのですが、素因数分解して分割統治すると解ける形にはなりましたが、実装量がめちゃくちゃ重い……

後で聞いたところもっと簡単な方法があるらしいです。

Kは海外勢の方におまかせしていたのですがなんかバグってしまったらしい。もうちょい議論しておくべきだった……

コンテンツ表彰

書家さんが今年はめちゃくちゃおもしろいタイプの人でした。今後も腕立てしてから書いて欲しい。

と思ったら芸人のおさるって人だったんですね……気付かなかった……(小さい頃に見た記憶がある)

解散

今年は懇親会的なやつないんですね……

感想

去年と比べるとかなり成長できたと感じられた点と、まだまだ詰めが甘いと感じた点があって、微妙な気持ちになりました。特に国内だけなら賞金圏内だったことを考えるとかなり悲しい。

来年こそは20位に入れる実力を持って挑みたいです。

運営の方々お世話になりました。ありがとうございます。

ちなみに来週はDDCC2016の方に行く予定です。よろしくお願いします。