ICPC 2016 国内予選 G -- ワープ航法
問題文:
http://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.html#section_G
テストデータ:
http://icpc.iisf.or.jp/past-icpc/domestic2016/judgedata/G/
「二点を通る直線で切るパターンを全部試す」はよくありそうで、「円で切り分けられた領域ごとに考える（ために二円の交点を列挙する）」のもよくありそうだけど、このふたつの組み合わせは見たことがなかった気がする。
求めるのが最小値なので、領域を切り分けるといいつつ、各領域における包含のパターンだけが列挙できればよくて、計算するときはワープ位置は平面上の好きな点にとれると考えてもいいのも面白かった。
続きを読むお誕生日コンテスト 解説
この記事は Competitive Programming Advent Calendar 2015 - Adventar の 1 日目のものとして書かれました。
ICPC のチーム戦略についての記事を書きましたが、ICPC もう引退したよ、そもそも ICPC 出てないよ、ICPC って何、という人も多いと思うのでおまけです。
去る 2014 年 2 月 2 日に、お誕生日コンテストというコンテストを開きました。
ふつうのコンテストではあまり見ないような変な問題を集めたコンテストなので、知らなかった方は是非解いてみてください。時間を無駄にできること請け合いです。
ところでこのコンテスト、解説記事をほぼ準備していたにもかかわらず最終的に完成しなかったので長い間解説がありませんでした。そこで、これを機に解説を完成させ公開しました。
こういう変なコンテストに出たいと思っているので誰か開いてください。
ICPC のチーム戦略について
この記事は Competitive Programming Advent Calendar 2015 - Adventar の1日目の記事です。
はじめに
私 (JAPLJ) は今年の 5 月にモロッコで開催された ACM-ICPC の世界大会で（世界大会出場は 2 回までのルールにより）現役選手を引退となったので、ICPC についてなにかを書いておこうと思いました。
ICPC といえば特筆すべきルールはやはり 3 人で 1 台の PC を使うチーム戦というところで、これまでにも様々なチーム戦略に関する記事が書かれています：
- ICPCに向けたUECodersの戦略 - とどの日記
- ~shiokawaのICPCに向けたチーム練習、コンテスト直前の準備について - しおしおたのブログ
- ICPC のチーム体制について - (iwi) ｛ 反省します - TopCoder部
（少し探して見つけたものと覚えていたものを順不同に挙げただけなので他にも探せばあるかもしれません）
そういうわけでチーム戦略についての記事を書こうと思いますが、一般的な話をしても仕方がない（というより iwi さんの記事がたいへん役に立ちます）ので、自分の経験に基づいたチーム戦の話をしたいと思います。つまり、特殊な例についての記録ということになるので、これがそのまま他のチームの戦略に役立つことはあまりなさそうですが、一部でも参考になれば幸いです。
対象
この記事で対象になるチームは以下の条件を満たしているようなチームです。
- チームメンバーにりんごさん (rng_58) がいる。
おっと、りんごさんも既に現役選手を引退となったので、対象チームがなくなってしまいました。ここまで読んで頂いてありがとうございました。明日の記事は 1_000_000_007 さんで「悪問の具体的事例とどうすればその問題をよりよくできるか」です。楽しみですね。
というわけにもいかないので、粛々と続きを書きます。
チーム構成
ここからは基本的にモロッコへ行った際のチームをもとにします。
- rng_58 (りんごさん)
チームの司令塔です。問題の概要をいち早く把握し、迅速に解法を導き、それら解法の複雑さや現在の順位表をもとにどの問題から手をつけるべきかを判断し、適切なコーダーに仕事を割り振ります。
- semiexp (準急)
コーダー 1 です。圧倒的なデータ構造力とタイピング速度、自身も TopCoder の target である強みを活かして、序盤の簡単な問題・データ構造を活用する問題・複雑な DP の問題などを担当することが多くありました。
- japlj
コーダー 2 です。TopCoder のレーティング等では上 2 人に遠く及ばないところがあるので、その分を練習量でカバーし、幾何・探索・複雑な実装を要する問題を多く担当しました。
チーム戦略
とにかく、実際のコンテストでどういう戦略をとるかについて書きます。
開始時
計算用紙を 1 枚使って、現状の記録を行います。10問のコンテスト (A問題からJ問題まで) の場合は、まず大きく A から J までのアルファベットを紙に書きます。
コンテスト中は、問題の簡単な分野や内容を表す語句、既に担当コーダーが決まった場合はその名前 (うちの場合は s か j)、解き終えた場合にはそのアルファベットに大きく丸を書いていきます。この問題はどういう解法で時間がかかる、この問題をまずやって次はこれ、などといった相談はこの紙を使って行います。
最序盤
ICPC において最序盤の問題選択は非常に重要です。最初の 1 問を解くまでに余計な時間を 5 分かけてしまうと、その後解く全ての問題に +5 分ぶんのペナルティがかかることになってしまい、これは無視できない量です。特に World Finals のように問題の並び順と難易度に関係がない場合、簡単な問題を迅速に探しだす必要があります。
タイピング速度のある準急にテンプレートの準備などを行ってもらっている間、急いで問題文を読んでいきます。ここでは明らかに幾何のような図がある問題や問題文が長すぎる問題は一旦放っておいて、短くて単純そうなものを直感的に選んで読んでいきます（この辺の選択は経験がモノを言う場面でもあります）。準急が一通りの準備を終えた段階で、簡単な問題を渡すことができればベストです。
また、りんごさんは問題文の短いもの、数学の要素が強そうなものを優先して読みます。数学の問題は解法は難しくとも実装が容易であることが少なくなく、またりんごさんは数学の問題が非常に得意なので最序盤にこういった問題を通すことも多くありました。
序盤
開幕が落ち着いたら、序盤の比較的容易な問題を片付ける作業に入ります。ここをいかに滞り無く行えるかがかなり大切です。
この段階では、基本的に semiexp, japlj のどちらか片方が PC 前で実装を行い、もう片方がまだ読めてない問題文を読んで概要（とすぐに分かれば解法）をりんごさんに伝えていきます。りんごさんは自分で読んだり受け取ったりした問題概要から、次にどの問題をやるべきかを判断します。このあたりではまだ問題が比較的容易なためコーダーがどちらでも大差なく、また効率の観点からいっても同じコーダーが連続しないようにします。
あまりに簡単な問題という場合を除いて、りんごさんが問題を担当コーダーに任せるときには「何分ぐらいかかりそうですか？」という質問をします。これに正確に答えるのは非常に難しいですが、5 分や 10 分ぐらいの単位で大まかな値を申告します。解法がわかっている複数の問題のうちどれを優先して解くかを考えるときに、同じコーダーが連続しないことに加え、この申告時間の短い方を優先することになります。（この申告が間違っていることももちろん往々にしてありますが、申告より短く終わった場合はそれでよし、申告より長くかかった場合はその時点で戦略を考えなおして交代するなりの処置をとります）
中盤
だいたい全問題の概要がわかり、容易な問題が片付いたあたりです。コンテストの難易度にもよりますが、この時点で開始から 1〜2 時間程度、解いた問題数が 5〜6 問であることが多かったと思います。
このあたりに来ると、コンテスト終了時の順位表の推測が行えます。「この問題はまずどこのチームも解かない」「上位の間ではこれを解けるかどうかが重要になる」といったことから、「あとはこの 4 問にこういう順で挑戦して時間内に全て解ければベストで、5 位以内には入れる」のようにコンテスト終了までの大まかな見通しを立てます。
semiexp, japlj はそれぞれ担当する（わりと重めの）問題があってそれに取り組むという状態になっています。りんごさんは、難しい数学の問題があってそれに取りかかっているという状態になると良いですが、問題セットによってはこの時点ですでに暇になっている（残った問題はとても解けるものではない or コーダーが考えるべきことしか残っていない）ことも多くなります。
終盤
コンテストの残りが 1〜2 時間ほどになってくると、WA が出てしまってとれないといった問題も出てきます（中盤までにこういう問題を出すとかなりまずい）。このときデバッグに印刷は積極的に行いますが、コーダー交代は比較的慎重に行います。printf デバッグ等明らかに PC を使ったほうがデバッグが捗ること、コーダーの交代は頻発するとそれによる時間のロスも無視できなくなってくることが理由です。
手元で WA が出るケースを探して、見つけたら printf デバッグ等の結果も含めて全部を印刷し、それについて吟味している間はコーダーを交代する、といったケースが多かったように思います。手元でどうしたも WA になるケースが見つからずどうしようもない（もはやソースとにらめっこするしかなく、PC を使うメリットがない）と判断した場合もコーダーを交代します。
コンテスト後
コンテストが終わったあとは反省会を行います。
まず全問題を振り返って、それぞれについて吟味します。このとき、コーダーはもう一方のコーダーが担当した問題を（概要も含めて）全く知らない状態が良いです。これはりんごさんの采配と、その後のコーダーによる実装が詰まらず上手くいったということを意味しているためです。逆にバグが出て詰まってしまい印刷などをした場合、デバッグに協力するためにもう一方のコーダーにも問題概要と解法が伝えられる、といったことが起きてしまいます。
また、全問題のアルファベットを大きく書いた紙を使って全体の流れを確認します。解く問題の選択ミスはなかったか、順番は正しかったかの確認や、実装に申告より長い時間がかかってしまった問題についての検討などを行います。
練習について
個人練習
このチームの戦略は、それぞれの人がどういった能力を発揮するかが分かりやすくなっています。たとえばりんごさんは 5 時間の間、PC には全く触れません。一方僕や準急はふつうのコンテストと比べ、問題の解法を考える時間というのが圧倒的に少なく、ひたすらコーディングに偏った時間を過ごすことになります。
そのため個人としての練習もわかりやすく、たとえば僕は AOJ-ICPC の問題を全て（当時）埋めるなどの練習をしていました。
チーム練習
このチームの戦略はやはり明快で、コンテスト中の各人の動きはかなり分かりやすくなっています。そのためチーム練習に特別に時間を割くことはほとんどありませんでした（JAG の開催する模擬大会に出る程度）。
しかしモロッコに行ったときだけはチーム練習を行いました。序盤の戦略で「容易な問題をいかに滞り無く片付けられるかが重要」と言いましたが、りんごさんの分析により「序盤で詰まったコンテストでは最終的な成績も悪く、序盤がスムーズにいった場合最終的な成績もよい」ことがわかったためです（これはあくまでもこのチームの話です）。
確かに、これまでに調子の良かったコンテストを振り返ると、序盤の容易な問題を片付けた段階で 2 位に 2, 3 完の差をつけて 1 位ということが少なくありませんでした。一方、調子の悪かったコンテストでは、序盤にそこまで他チームをぶっちぎることが出来ていなかったように思われます。
そこで、モロッコにて「5時間コンテストの最初の1時間だけ練習」を行いました。これはその名の通り、5時間コンテストの過去問をひとつ選んできてそれで練習をするのですが、開始1時間が経った時点で終了とします。もちろん、戦略としては 5 時間コンテストに挑むつもりで行います。
つまり、直前になって 5 時間フルで使って難しい問題に取り組んだところで、いまからそういった実力を底上げするのには無理がある。だったら、コンテストに重要な序盤の動きだけを集中的に鍛えればよいし、そういった立ち回りなら直前からでも改善できる、という発想です。5 時間の練習で得られる成果を 1 時間で得ようという最高の練習です。効率 5 倍、スゴイ！
東京工業大学プログラミングコンテスト2015 P問題 - Dancing stars on regular expession!
Looksery Cup 2015 B. Looksery Party
リンク: http://codeforces.com/contest/549/problem/B
こういうのどういう思考過程で思いついたのかメモしておこう。
問題
人が n 人いて、それぞれ互いの電話番号を知っていたり知っていなかったりする。
パーティに人を呼ぶと、呼ばれた人は知っている電話番号すべてに電話をかける。自分の電話番号は知っているので自分にもかける。
数列 a1, a2, ..., an が与えられる。パーティに呼ぶ人をうまく選んで、人 i が電話をかけられた回数が ai にならないようにできるか。できる場合は呼ぶ人の集合を具体的にひとつ求めよ。
思考
（最初、「自分の電話番号は知っているので自分にもかける」ことを読み落とす）
結局、行列 P とベクトル a があって Px と a がどの要素も異なるような x ∈ {0, 1}^n があるかを判定する問題。でもこんなの解けるはずがない。
（問題文を読み直して「自分の電話番号は知っているので自分にもかける」ことを知る）
あからさまに怪しいのでこれの意味について考える。
人 i が電話をかけられた回数が ai に一致してしまったら、人 i を呼ぶ/呼ばないをひっくり返せば、少なくとも人 i については大丈夫。
でも他の人がやばくなるかもしれない。その時は他の人もひっくり返せばいいかと思いきや、また人 i がだめになってしまって、循環するかもしれない。
落ち着いて自明なパターンから考える。誰も呼ばないと ai = 0 の人がやばい。そういう人がいたら、とりあえず呼ぶとする（他の人を呼ぶ手もあるけど、あからさまに怪しい制約を活かすとしたら、その人自身を呼ぶことにするのがよさそう）。
その結果やばい人が現れたら、その人も呼ぶことにする。とやっていくとどうなるか？いやさっきと同じで循環するのでは？
よく考えると循環はしない。最初誰も呼んでいなくてやばい人がいたらその人を呼ぶ、をやると電話された回数は増えるだけで減らない。だから、一度やばくなって呼ばれた人がまたやばくなることはない。
GCJ 2015 Round 2 C - Bilingual
グラフと睨めっこしなくてもわりと機械的に作れますという話。
なので、「準備」までは分かっていて最小カットにしたいところまでは前提。
コンテスト中はすぐ作れたので機械的にできると思ってたけど記事を書いてみるとそうでもない気がしてきた。
問題
文章（単語の列）が N 個ある。各文章は英語かフランス語のどちらかである。
英語の文章に出てくる単語はすべて英語の単語で、フランス語の文章に出てくる単語はフランス語の単語である。
文章 1, 2 がそれぞれ英語、フランス語であることが分かっている。
文章 3 … N は分からないが、英語とフランス語で共通する単語の個数を最小にするように文章の言語を決めるとき、その最小値はいくらか。
準備
面倒なので英語、フランス語を E, F と書く。N 個の文章を S_1, S_2, ..., S_N と書く。S_1 = E, S_2 = F で、S_3 … S_N は E, F のどちらか。
入力に出てくる単語 w について、その単語がどの文章に出てきたかを考える。
- 文章 1, 2 の両方に出てくるなら、どうやっても E, F 共通の語（どうでもいいやつ）
- 文章 1 (E) に出てくるが文章 2 (F) に出ないなら、S_3 から S_N のうち w を含むような文章の中に F があれば共通の語（E, F が逆の場合も同じ）
- 文章 1, 2 の両方に出てこないなら、S_3 から S_N のうち w を含むような文章の中に E, F が両方あれば共通の語
やることは、S_3 から S_N までを E のグループと F のグループに分ける。文章の部分集合がいくつかあって、それぞれに対して条件がある。部分集合 A について
1. A が E グループの文章を含めば +1
2. A が F グループの文章を含めば +1
3. A が両グループの文章を含めば +1
のいずれかの形で条件が決まる。
グラフの作り方
※以下では E, F をそれぞれフローの source と sink の意味でも使います。
重要なこと
容量無限の辺は
- a が E なら b も E
- b が F なら a も F
を意味する（切ってしまうとカットが無限になる）。
E を含めば +1
たとえば a, b, c のうち誰かが E なら +1 というコストをつけたいときは
- a, b, c のうち誰かが E なら必ず E になる点(☆)を作って
- ☆から F に容量 1 の辺を張る
☆の作り方は「重要なこと」を使うと簡単。
F を含めば +1 も同じようにできる。
両方含めば +1
文章の部分集合が空でないから E か F のどちらか片方は少なくともあるので
- E を含めば +1
- F を含めば +1
の両方をやって、答から 1 を引く。
CodeFestival 2014 上海 コンテスト感想
CodeFestival 2014 上海のコンテストは僕 (JAPLJ) ときゅうり (kyuridenamida) で writer/tester をしていました。
全体的には、セット前半は
- 落ち着く、焦らない
- 気づく
- しっかり実装する
あたりが試される感じで、セット後半はこれといった難問こそないものの、どの問題もそこそこの手応えがあるという感じを目指していました。
2 人で 3 時間 10 問のセットを準備する (しかも参加者は皆かなりの熟練者) ということでかなり大変ではありましたが、その分思い入れも強いセットになったので、ここで各問題について振り返ってみます。(解説をするわけではありません、オフィシャルな解説がそのうち出るはず？もう出てる？)
僕の書いた writer/tester 解も載せます。テンプレを略しているので謎の関数が出てきますが in() は整数入力、chmax(a, b) は a = max(a, b) で chmin も同様です。ライブラリとかも略。
続きを読む