ICPC におけるチーム Cxiv-Dxiv の基本戦略
- この記事は何か
2015 年から 2018 年にかけて活動した、チーム Cxiv-Dxiv(Hujiwara, hogloid, DEGwer) のコンテスト中の立ちふるまいについてです。
- メンバー紹介
Hujiwara: 幾何とか非典型実装をやる
hogloid: データ構造とか文字列とかをやる
DEGwer: 数え上げとかロシアゲーをやる
実力が似通っている && 各々の得意分野が異なるチームです。全員の得意分野を合わせるとほぼ全分野が網羅されます。
解くスピードは遅いので序盤はダメですが、逆に終盤まで速度が落ちないのが強みです。多分難しいセットほど強いと思います。
- 実績
WF 2017 12位(銅)
WF 2018 4位(金)
アジア地区予選 2015 つくば 5位
アジア地区予選 2016 つくば 2位
アジア地区予選 2016 バンコク 2位
アジア地区予選 2017 ホーチミン 2位
アジア地区予選 2017 つくば 1位
国内予選はひどい
- 戦略
初期は戦略が固まっていなかったですが、チームで何回か 5 時間をやっているうちに固まってきました。
固まる前のものを書いても仕方ないので、最終形態だけ記述しておきます。
コンテストが始まったら問題を機械的に配分します。WF やロシア合宿のセットなど問題の並び順が完全ランダムな場合は何も考えずに等分します。
そうでない場合(国内予選や日本のアジア地区予選など)は、前の方を Huji, hog の 2 人が分担して読み、ぼくはまったり後ろの方を読んで解法を考えておきました。
これは、ぼくの実装が遅い && ぼくは考察系担当なので、前の方をぼくがやる利点がないし、そんな暇があったら後ろの方を考えて詰めるなり適切に前を解いた人に投げるなどしておいた方がいいためです。あと英字キーボードには早く慣れておいた方がいいです。どこで使うのも英字配列なので。
ただ、他の 2 人とて特段速いわけではないので、毎回スタートはかなり悪いです。ということで、全完速度勝負とかになると弱くて、よって国内予選は勝てない。
ペナルティのシステムを考えると序盤の速度はペナルティにかなり大きな影響を与えるわけですが、結局何しても無理だし運もかなり絡むので諦めました。
WF 二年連続で 8 完内最下位だしね…… 特に序盤の問題の実装が重めだとどうしようもないです。逆に序盤の実装が無だと(ロシアセットとかでたまにある)上手くいくことがあります。
ロシアとかだとたまに変なものの FA を取ったりします。
本題に戻ります。問題を配分した後適当に見た目がよさそうなものから順に読んで考えていきます。できる && ある程度実装が軽い とわかったら他のを読む前にそれを書き始めます(どうせ実装しているうちに他の人が読んでくれるため)。ここで注意すべきは、できるからと言って実装が重めなものに手を付けるのはやめておいた方がいいということです。まあパソコンが空いている && 実装方針を間違いようがない なら手を付けてもいいんですが、たいていの場合そういうのは終盤まで残って一人戦線離脱という感じになります。
ある問題ができる状態になったら、何分くらいかかりそうかを聞いて実装をかわるかどうかとかを判断します。30 分以上かかるのを序盤に始めるのはあまりよくなくて、そういうのは解法が分かっても放置しておくべきです(パソコンが空いていない場合)。
問題を見て明らかに他の人に向いているようならその人に投げつけます。
サンプルが明らかに文字列だった時点でぼくは hogloid に投げるし、10^9+7 と書いてある問題が無条件でぼくに飛んできます。たまに本質が数え上げじゃなかったりするので投げ返します。
データ構造だったら考察しきってから hogloid に投げつけたりします。幾何は図を見た瞬間に Hujiwara に投げていました。
どの問題がどの状態になったかの表みたいなのを管理した覚えはありません。各々がやっている問題や解いた問題は聞けばすぐわかるので、暇になった人が適宜やることをあぶり出していけるためです。
ということで、序盤は各人のところに得意分野が集まっている状態になります。よほどのことがない限り、開始 1 時間ちょっとで各人がメインでやる問題が 1 個か 2 個に絞られている状態になります(簡単枠は既に解いた or 実装中 or パソコン待ち になっていて、やることはわかるが明らかに実装が重すぎることが分かりきっているものとかは見なかったことにするため)。
とはいえ大抵実装キューが詰まっているので、軽そうなものから順にやっていきます。もちろんバグったら印刷して交代しますが、パソコンをちょっと使えばデバッグ効率が数倍良くなる場合はパソコン上でデバッグするのも選択肢には入ります。簡単セットだともうしばらくするとパソコンに触れていない人のやることがなくなります。
順位表ですが、最序盤は適当に選んだものを通せるかどうかなので気にしません。実装が重めなもの以外にできることがなくなったタイミングで確認して、コンテストの全体像を把握します。簡単そうな問題を把握するのは早いタイミングでできているので、やる問題を選ぶ目的というよりはコンテストの性質を見極める目的に使います。
もし実装が重いと判断したものがガンガン通されているようであればそのセットは重いセットです。そうでない場合は軽いものはその時点でたいてい通せているので、AC が 1 つ以上出ているものに重点的に取り組むことにします(ライブラリゲーとか既出とかだと判断した場合は放っておきます)。
十分軽いのに解かれていないことは国内はおろかロシアでも普通にあるので、順位表よりも自分の判断を信頼して軽い順にやっていきましょう。FA がおまけでついてきます。
たまにとても難しいセットだと序盤からパソコン空きまくりということがあります。そういう時は通されている実装枠があるならそれに手を付けるのが最適だと思います。
大抵そういう時は序盤に通されるものがバラバラになりがちですが、0 と 1 は大きく違うので 1 回以上通されているものを重点的に考察します。
大量の WA が出ているものは地雷なので敬遠しますが、解法に自信がある場合はやります。もちろんライブラリゲーとかなら適切に諦めます。
そんな感じでできるものを消化していくと 4 時間経過して順位表が固まります。と言っても、この時間帯の順位表から読み取れる情報はあまりないので特に困らないのですが。解法が分かっているものが残っていても、重い場合はこの時間帯から手を付け始めて通ることは少ないです。特に、残り 20 分で何かはじめて通せる、と言ったことはまずない(そういうのは序盤に通っている)ので、デバッグに集中します。どうしようもないもの以外残っていない状態になった場合も同様です。
人数分印刷して全員でデバッグをするのが良いでしょう。これで結構バグが取れます。運よく通ったり運悪く通らなかったりしてコンテストが終わります。
もし通ったらおやつを食べに行きます。
一人が詰まっても他がカバーできるので、問題の配分を間違えなければ大崩れすることは少ないです。逆に、配分を間違えると大変なことになりうるので積極的に人に投げつけていきましょう。
- どうやって練習するべきか
WF でメダルを目指すとなると日本国内ではどうしてもレベルが足りないため、現状海外に出るしかありません。
twitter を見ると RedCoder たちがたまに集団で旅行していることがあると思います。これはりんごさん主催の合宿で、ロシア合宿などからとってきた 5 時間セットをやりがてら旅行をします。
ロシア合宿の問題は基本的に非公開なので、現地に行くかこういうのに参加するしかなさそうです(ただしかなりレベルが高いので、最低でも AtCoder 橙、できれば赤はないと厳しい)。
あと、Open Cup というのがあって、これもりんごさんが日本 admin をしているのでアカウントをもらって参加することができます。
これは日曜日に開催される ICPC 形式のコンテストで、何人かのチームから毎回 3 人までを選んで出ることができます。ただ、集まって出ると帰宅がかなり遅くなる(コンテストは 17:00-22:00)のと、そもそもロシア合宿で使って非公開にしておいたセットを使ったりするので、あまり出ませんでした。
というわけで、ロシア合宿の紹介をします。年に何度か各地で合宿をしていて、だいたい 1 週間強の期間で毎日 1 セット(休憩日はある)をやります(年中こんなのに参加してるんだからロシア人はそりゃ強いに決まっている)。
Petrozavodsk Camp: 夏と冬の二回がある。夏に 1 回参加した。9 セット行う。一番シンプルで、コンテストと解説以外ほぼ何もない。北緯 62 度なので夏でもそこそこ寒いし、冬はお察し。
MIPT Camp: World Final の前にモスクワで行われる。おそらくもっともレベルが高い。メダルを取る 12 チームの内 8 チームがいたりする。
Hello Barcelona Bootcamp: スペインのバルセロナで行われる。強いチームが少なくてレベルが低めではあるが、問題のレベルはちゃんとしている。
インドで行われたこともある。講義とかがちゃんとあるタイプの合宿。東大にいると謎の伝手で参加費が無料になることがある。ありがとうございます。
中国: どうやら中国人が集まる合宿もあるらしいが、詳しいことはよくわからない。
その他: あまり詳しくないがベラルーシでやったりもしているらしい。多分年ごとに変わってくる。この 7 月にウラジオストクで開催されるらしく、近いので参加してみては。
