ゆらのふなびと

競プロ, Python, C++

CODE FESTIVAL 2016 に参加しました

予選

A

焼肉を食べていたので出なかった。

B

4完したが108分かかり落ちた。冷えた。

C

3完+部分点で通過!

夏合宿や会津合宿で「こどふぇすで会いましょう!」と言いまくっていたのが嘘にならなくてよかった。

1日目

集落を6時半に出発した。なんだかテンションが上がっていて、新幹線の中で過去問の練習コンテストをしていた。11時半頃着いた。

ちょくだいさんやsnukeさんを発見したので声をかける。仕事なので忙しそうだった。見つかった知り合いには挨拶して、席に用意されていた軽食(コッペパンのサンドイッチみたいなやつ)を食べた。

しばらくするとBGMやオープニングムービーが流れてきて、すごいという感じだった(ムービーではみんなのIDがぐるぐるしていた)

本戦

4完+部分点でパーカーを取るぞ!と意気込んでいたら3完で激冷え。

Aは今朝動画で見ていたりんごさんの挑戦状のやつだ、と思いながら解く。AC。

Bを読むが全然わからない。1 + 2 + ... + k を取れるだけとって余った分を他に振り分けるみたいなことをやっていたけどWA。30分くらい取り組んでいたけど光が見えないので、まじか……と思いながらCに行く。

Cは頂点を人と言語で分けて(人,言語)の辺を張れば2乗にならないことにすぐ気づいたので、書く。AC。↓で似たようなことをした記憶があった。

arc061.contest.atcoder.jp

Dは2つ目のルールから使う方がよさそうというのは第一感であった。modをとってiとM-iのやつを貪欲にマッチングした後余ったやつで同じ数字のをマッチングする(0と真ん中(あれば)は自分の中だけ)としたけどサンプルが合わない。それはそうで、同じ数字のペアをできるだけ残さないといけない。ということで奇数個残っているやつから貪欲に使うというのを書いたけどWA。バグってたのか見落としがあるのかわからなかったけど、Bを飛ばしていたので腹をくくってBに戻る。

Bは最大値を決めうちしてあとはいい感じにやるというのを考える。Nをdistinctな正整数の和で表すとき、最大値Mを決めると、あとはN-MがM-1以下のdistinctな正整数の和で表せればよい。そのための必要条件は N-M <= 1 + 2 + ... + M - 1であることだけど、実はこれが十分条件でもあるらしく大きい方から貪欲にやるとできるっぽかったので投げた。通った。終了5分前だった。

以後は安静にして精神の回復に努めていた。

~~~

この後touristのトークライブがあって、これまでの人生で一番「英語を聴けるようになっておけばよかった」という気持ちになった。

ここから割と自由行動になる。メシを食べないとやってらんないですよという気分だったので、メシを食べる。おいしかった(鳥を煮たような洋風のやつとチーズケーキが特に好きだった)。前々から面識のあったYazatenさんやmemphimさん、kazu0x17さん、tubo28たちと話しながら食べていた。ドラクエのマップを歩くのがIDA*だという話が出て面白かった。

歩いていたら高校の同期に出会う。kobae964さんだった。こういう場所で5年ぶりに会えるとは思っていなかったので感激する。

秋葉さんのペアプロを聴く。問題は知っていたやつだったけど、解法が洗練されていく過程がわかって面白かった。

エキシビションマッチを見る。座ってるだけじゃつまらないので立ち見であちこち動いていた。スクリーンがいくつかあってそこに各チームの画面が映し出されていたのだけれど、やっぱり強い人はコーディングも速いなという感じだった。順位表を見ながらみんなで一喜一憂したりして、結構盛り上がった。

あとこれは1日を通しての感想なんですが、りんごさんがずっと徘徊しているのが面白かった。

~~~

そんなこんなで1日目終了。ホテルがみんなバラバラで、徒歩で移動した後はお風呂に入ってすぐ寝た。

2日目

トーナメントなるものがあった。今年初の試みらしい。1日目の成績で8人ずつのグループに分けられ、グループ内で上位4人が通過(Round 1)、4人のグループ2つをマージしたグループからまた上位4人が通過(Round 2)、また4人のグループ2つがマージされ最後は各グループでの順位で表彰(Round 3)という感じだった。ラウンドは各2問で時間が30分,30分,40分と短く、しかも部分点が多い(どの問題にも3個ずつくらいある)ということで、かなり戦略性を問われるスタイルだった。

このときcamypaperさんと初対面して、最初に問題を読んでどっちに賭けるか見極めるのが大切そうという話をしていた。motiさんとも初めてお話できた。

Round 1

Aを読む。Kruskalをいじればいけそう。500点取れる気がしたので書こうかとも思ったが、とりあえずBを読む。

Bの200点はビット全列挙で、400点は区間DPっぽいことをするのかなあという気がした。トーナメントのルールとして正の得点を取らなければ次に進めないとのことだったので、とりあえず正の得点を取ろう思い200点に手をつける。さすがに手癖で書けた。10分くらいでAC。

Aに戻って500点解法(のつもりで実は200点だった)を書いた。Kruskalの判定部分に「sのグループとtのグループをマージするような辺は採用しない」を入れた。Q<=105, M<=4*105なので当然TLEするのだがQ=1の200点分は取れた。

結局、A200+B200でRound 2に進出できた。

終了後は周りの人たちと解法の議論ができて楽しかった。t8m8さんに、A問題はsとtの間にコスト0で辺を張ると考えてよいという話を聞いて、天才かなと思った。

Round 2

Aを見てすぐ「確率だ!逃げろ!」と思ったのでBに行く。

Bは200点なら書けそうな気がしたので書く。4分でAC。順位表を見るとAの200点が解かれていたのでAに戻る。

Aを読むと200点がド自明でビビる。AC。ここまで8分。あとはAの300点を考えていたが、間に合わず。

またA200+B200で、Round 3に進出できた。

Round 3

Aは問題文がぱっと見よくわからなかったのでBへ。

Bは400点分ならセグ木やるだけを感じる。M...Mm...mということは最初に幅固定の最大値を取って、最後にそれらのminを取ればよい。ACしたけど17分くらいかかっていたらしい。

Aの100点は大きい数字から採用すればよさそうと思って書いたがWA。200点はDPだろうなと思うもうまく落とし込めず、そのまま終わった。

結局Bの400点だけで入口から1番近い列グループの1位になってしまった。akiさんがBの満点解法を書いていたらしいので、それが通れば圧倒的に負けていた。

今回はラウンドを1つ勝ち進むごとにステッカーをもらえてそれをコンプするとCODE FESTIVALのロゴが出来上がる(+ちょっとイラストがある)という感じだったのだが、そのステッカーのコンプ&表彰で登壇をさせてもらえて光栄だった。

トーナメントは、競技プログラミングの「競技」面を強く感じるイベントだった。普段は自明な部分点を取っても学ぶことがないと思い満点を考えにいくことも多いが、今自分が出せるものを最大限活かして勝ち進むというのも楽しいと感じた。GCJとか割とそんな感じなのかもしれない。

~~~

昼を食べる。お弁当争奪戦でキジ肉弁当なるものを珍しさから選んだが、肉が硬くてあまりおいしくなかった。海鮮にすればよかった。

トイレに行ったりしていたらきゅうりさんのライトニングトークを聞き逃した。ちょくだいさんのを立ち見していたけど、ひたすらテンションで押し切っていて面白かった。

りんごさんの挑戦状2(トークライブ)を見た。りんごさんが出すよくわからない問題に競プロ界の強い人たちが答えるというイベント。いろいろゆるくて好き(競プロ界隈のアットホームさを表していると思う)。今回の解答者の皆さんはhogloidさん、semiexpさん、snukeさん、tozangezanさんだった。snukeさんが自己紹介でクソなぞなぞコンテストの戦歴を語っていて面白かった。世界地図のやつを見ていたら皆さん地理力高すぎてビビった。

そして最終イベント、チームリレーへ。

チームリレー

大人数での団体競技ということで不安もあったが、いざ始まってみると結構楽しめた。チームはKチーム(黒)で、海外勢はsevenkplusさん。戦略としては順位順に1問ずつ割り当てて、必要なら適宜相談しながらやるという感じだった。

自分はとりあえずA問題を解いた。さすがにやるだけだったのですぐAC。帰ってきてからは色々ちょっかいを出していた。Cを考えていたutsubo_21さんにシミュレーションだが実装はどうするのが楽だろうと聞かれ、vectorを2段持ってバケツリレーしていくのが良さそう的なことを言った。Fを、担当していたnkshnさん&既にBを通していたt8m8さんと一緒に考えた。切る回数を最大化するには 1, floor((N-1)/2), ceil((N-1)/2) と切るのが良さそうで、これを使えば二分探索で解けそうということを言った。あとはパソコンの順番が回ってくるまで一緒に紙コーディングをしていた。割と翻弄してしまって申し訳なかった。

以降は強い人たちが既に解法を作りきっていてあまりすることがなかったので、レッドブルを飲んでいた。後半の問題の解き方をdrafearさんやsortreewさんに教えてもらったり、Kを解くsevenkplusさんの姿をみんなで見守ったりしていた。J問題が面白いと思った。

~~~

あとは表彰式。川柳とか太鼓の達人とかいろいろあったけど自分はノータッチだったのでひたすら拍手を送る機械になっていた。書道コーディングでまさかの芸人書道家が出てきて面白かった。natriumさんが「劣モ」をリクエストしていてさすがだったのと、「十億七」は普通にかっこいいので欲しかった。

表彰式が終わるとついにこどふぇすも終わりで、関西勢と一緒に新幹線に乗って帰った。駅弁の牛肉弁当がおいしかった。

まとめ

CODE FESTIVAL、とても楽しかった。コンテストは良問揃いだったし、一口にコンテストと言ってもいろんな楽しみ方があるのだと思った。イベント面でも有名な人の話を聞けたりして貴重だった。

競プロ界の知り合いたちに再会できたのもよかったし、初めてお話しできた方はたぶんもともと名前を知っていた人だけでも10人以上いて、またどこかで会えるといいなと思った。今回お話しできなかった人もいるが、競プロをやっていればまたいつか出会えるだろうからいいということにした。

ぜひ来年もやってほしい。もしやるならばぜひ出たいし、出られるように頑張りたい。

AOJ-ICPC 400 インビジブル

問題

インビジブル | Aizu Online Judge

D: インビジブル - JAG Contest 2016 Domestic | AtCoder

解法

先手はスコアの最大化、後手は最小化を目指すのでミニマックス法で解ける。

先手, 後手のデッキでスタックにつまれている区間をそれぞれ[l0, r0), [l1, r1)とすると、状態として(l0, r0, l1, r1, 今どちらの手番か, スタックが空になってから何回パスが連続したか)を持つだけでよいというのがポイント。パスで得点が変化するときには相手が最後に置いた妨害カードより上にある自分の得点カードの和がわかればよいので、実装ではこれらも引数に入れると楽だった。

あとこれはインビジブルあるあるなんですけど、スタックが空になってないのにパスの回数を足して死んでいた。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8A%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf

gist.github.com

AOJ-ICPC 300 Line Gimmick

問題

Line Gimmick | Aizu Online Judge

解法

実装しんどいなーと思いながら書いたら一発で通って最高↑↑な気持ちで解説を見たらすごい簡単で悲しくなったので書きます。

ある'>'(=R0)からスタートすると、向きが変わるのはR1より右側にある1つ目の'<'(=L1), R0より左側にある1つ目の'>'(=R1), R0より右側にある2つ目の'<'(=L2), ...という風に続きます。左から順にR0をすべて試すとすると、どこが最後の反射になるかをしゃくとり(?)っぽく更新していくことができます。詳しくはコードのようにやりました。

ところがしゃくとりっぽくやる必要はなくて、累積和だけわかればどこが最後の反射かわかります。

mayokoex.hatenablog.com

実は n - min(左端に連続する'<'の個数, 右端に連続する'>'の個数) でいいらしい。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2015%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9C%B0%E5%8C%BA%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf

AOJ-ICPC 300 ABC Gene(☆)

問題

ABC Gene | Aizu Online Judge

解法

操作を逆順に考える。ある文字列 t を1段階前の文字列sに戻すことを考えると、t の中にある任意の"ABC"は、sにおいては直前の置換で選んだ文字Xだったはずである。仮にsに"ABC"が含まれていれば、必ずXが"ABC"に置換されるのでsの中の"ABC"がそのまま t に残ることはない。また、Xを置換するという操作以外から"ABC"という文字列は生まれえない。

t に"ABC"以外の形で含まれる文字はXたりえない。先に述べたように、s中のXと t 中の"ABC"が1対1に対応するからである。

以上を踏まえてdfsしたら通った。

gist.github.com

AOJ-ICPC 450 Encryption System

問題

Encryption System | Aizu Online Judge

解法

入力の文字列を s, 暗号化前の文字列をtとする

任意のiについて、t_i = s_i or s_i + 1 の2通りしかないので 220 の全探索が間に合う

左から見ていくと、t_i = s_i としてよいのは i の前に少なくとも1つ s_i と同じ文字があるとき

t_i = s_i + 1 としてよいのは i の前に1つも s_i + 1 と同じ文字がないとき

よって、(i, 構成中の文字列, 既に使われた文字)を引数とする再帰が書ける

やざてんさんのブログで見て気づいたけど、dfsの末尾で文字列をvectorに入れていくと勝手に辞書順になって最高

yazaten.hatenablog.com

gist.github.com

AOJ-ICPC 400 Restrictive Filesystem

問題

Restrictive Filesystem | Aizu Online Judge

解法

setで頑張る。

計算量がやばそうだったけど意外とそうでもないらしい

最初は区間の(左端, 番号)だけでやろうとしていたけどそれだと隣り合う空の区間をマージしないといけない場合がでてきてつらかったので(左端, 右端, 番号)にした

gist.github.com

AOJ-ICPC 300 Mirror Cave

問題

Mirror Cave | Aizu Online Judge

解法

脳筋BFS

DFSで書いたらREしたのでスタックオーバーフロー?

縁を'#'で埋めると楽

「片方だけが先にゴールについたらダメ」を忘れて死んでいた

gist.github.com