ヘクトのメモ

なんとなくいろいろ書いていくと思います．

ICPC 2017 国内予選

去年と同じくチームnocowとして今年も参加しました．(5回目のICPC国内予選)
http://osrehun.hatenadiary.jp/entry/2016/06/25/205342:embed_cite

チームメンバー

@osrehun コーダー担当
@icchyr インフラ担当
@xthexworldx コーダー担当

結果は7完5位でした! アジア地区予選に行けます!
今年の国内予選は順位表を荒らせたと思うので、観戦者には非常に楽しんでもらえたようですw

あと，学内の国内予選の最高順位を更新しました. (抜かれることがある記録なのだろうか?)
以下詳細なタイムスケジュールと感想

使用した競技環境

  • Lubuntu 16.04
  • GCC 5.4.0

-1:30
icchyrが環境構築バトルを始める.
Linuxでプリンタの設定は大変なんだな...
Chromeを利用してhtmlをpdfに変換し、全問題を印刷するコマンドを考案してくれたので、本番に採用した.

0:00
まず，全問題を印刷してもらうが、練習のURLと本番のURLが違いに気づかずに「Not Found」を大量印刷しかける.
この後に、icchyrが環境構築を行いながら，自分がA問題を読む．xthexworldxにはB問題を任せる．
icchyrがターミナルで作業している間に、断片的に読み取れるA問題の情報から問題文を推測した.

0:05
印刷クエリを投げ終えたので、実装します.
icchyrにテンプレートを少し書いてもらい、バトンタッチ
A問題を書き終えるが、サンプルが合わない.
maxを取り忘れたことに気づいて、はい.
サンプルが通ったので提出

0:10
A AC (実は大学内でAを通すのが一番遅い)
xthexworldxがB問題の方針立ったということで、バトンタッチ
自分とicchyrはC問題以降を読んでいくことにする.
C問題を読むと、実装するだけでは...
というわけで、簡単な紙コーディングを行い、ループの範囲をちゃんと書き出しておく.
ある程度まで書いたところで、icchyrからD問題の概要を聞く.
制約の 1 ≦ n ≦ 500, 1 ≦ m ≦ 500 だけを見るとヤバイ問題にしか見えないけど、1 ≦ n*m ≦ 500 を見た瞬間に 25*20 = 500を連想する.
というわけで、m ≦ 20 の時はbitDP、m > 20の時は全探索、はいとか言って、計算量を議論する.
(2^25が10^9とかいうチームメイトの発言にパニクるけど、冷静に考えると約3200万です)

0:20?
xthexworldxがBの実装終えたらしい.
実行してみると、サンプルが合わない.
とりあえず、紙デバッグを行ってもらう.
Cのコーディングを始める.
少し書いたところで、B問題のコードに初期化ミスがあることに気づいたので、修正
サンプルが通ったので提出

0:28
B AC

引き続き、Cのコーディングを行う.
実装を終えたので、実行してみると、サンプルが合わない.
適当にプリントデバッグしてみると、池の内側を正しく探索できていないので修正
サンプルが通ったので提出


0:38
C AC

方針は自明なので、Dも引き続きコーディングを行う.
全探索解とbitDP解の両方を実装して、サンプルを両方の解で試す.
bitDP解がバグっている...
解が存在しないものを「-1」とかで区別し忘れていたなどに気づいてすぐに修正
サンプルが通ったので、実行する.
この時、D1.inを走らせている時にセグフォする.
ここでインフラ担当のicchyを呼び、gdbを動かしてもらい、セグフォの位置をすぐに特定
無事に動いたので、提出

0:56
D AC
この間にチームメイトが残りの問題を読んでくれたらしい.
簡単な概要を聞いていく.
E問題は初見では解けなさそうという気持ちになった.
チームメイトがF問題の考察に勤しんでおり、インフラ担当により便利なツールができていた.


F問題は多分、折り方と数の位置が 1:1対応の関係になっているだろうと踏んで考え始めた.
まず、上からi番目を下から何番目に変換して、jを1引く.
i回目の折り方が 上位iビット目に対応付くのは、サンプルケース1つ目で把握した.
L = {1,0} R = {0,1} という対応になっている。

いろいろ試行錯誤していくうちに、上位 iビット目(0-indxed)の状態は
i番目の文字がLの場合　下から [L...L(長さ　2^(i+1)] [R...R(長さ　2^(i+1)] [L...L(長さ　2^(i+1)] [R...R(長さ　2^(i+1)] ...
i番目の文字がRの場合　下から [R...R(長さ　2^(i+1)] [L...L(長さ　2^(i+1)] [R...R(長さ　2^(i+1)] [L...L(長さ　2^(i+1)] ...
となる.

あとは、便利なツールでサンプル1と戦いながら、強引にコーディングをしていく.
サンプル1が通ったので、残りも試すと全部一致した.
チームメイトにマジでサンプル通ったのと驚かれる.
F1.inを提出してみる.　「Correct Answer!」
チームメイトにプロと言われる (1回目)




1:28
F AC

ここで、チームメイトからG問題の方針(右手法)が立ったことを伝えられる.
G問題を把握するも、解法が正しいか判断つかなかったけど、反例も見つからなかった.
個人的には嘘解法じゃないかと疑っていて、Mengerの定理かなと考えたけど、頭が働いていなかった.
ただ、xthexworldxがコーディングできる状態だと聞かされたので、迷わずGOサインを出した.

他の問題の解法も思いつかないし、コーディングするのがICPCではボトルネックになるので、コーディングしてもらうべきと判断した.
解いた問題の数が直に影響するICPCでは、解ける可能性も0ではないかつやることがなければ、賭ける価値は大いにある.
(最悪、方針ミスしても入力パートのコーディングはサボれるので)

G問題についてはチームメイトを信じて(完全に投げる)、E問題に取り組みます.
E問題を改めて読むと、2項演算に括弧がついているので、変数を1つ増やすと最低4文字増える.
構文木の数は少ないのでは?と考える. あとは適当に16通りの変数の割り当てを調べて一致するか判定かな?

1:50?
G問題のコーディングが終わったみたいけど、サンプルが通らない...
という訳で、チームメイトには紙デバッグを行ってもらい、E問題のコーディングを始める.
まずは、構文木をちゃんと書く.
ここで、G問題のバグを発見(グローバル変数を参照するつもりなのに、ローカル変数を定義していた.)
修正してもらう.サンプルが通ったので投げてもらう.

2:00
G WA
やっぱり反例があるのかなと疑問に思いつつ、E問題に集中したいので、チームメイトを信じる方針を取る.
ここから、5分くらいで G1.in のうち、w ≦ 20 and h ≦ 20 のケースを抽出して反例探しをしてもらった.
反例を探してもらっている間にEの構文解析パートを書いていく.

2:20
Gの反例が判明して、それに対する修正も分かり、やっぱり方針は正しいとチームメイトが主張してくれた.
ただ、自分もコーディングが終わりそうなので、書き終えるまで紙コーディングで詰めておいてと言っておいた.

2:28
Eを書き上げて、サンプルを投げる.　サンプル通るが重い...
とりあえず、E1.inを入力として実行する.
ただ、ICPC数日前に二分(にふん)探索とかのツイートを見たので、とりあえず五分以内に答えが出なかったら修正しようという話になった.


実行してもらっている間に、G問題を修正してもらう. やることないのでね.
E1.inは結局、三分で答えが出たので提出する.　「Correct Answer!」
チームメイトにプロと言われる (2回目)
もう三分でE2.inも答えが出たので提出する.　

2:35
E AC

xthexworldxもG問題の修正を終えて、WAの出力とdiffを取る.良い感じっぽい
G問題の提出を行う. 「Correct Answer!」
チームメイトにプロと言う. チームコンテスト参加した中で最高の瞬間だった.

2:36
G AC

というわけで、7完です.
ここで順位表を観たら、4位で騒ついた.
この時点で上3つ東大(8完)、下3つ東大(7完、6完) という状況になって、チーム全体で上位争いに食い込んだことに対する感慨深さを感じた.

そのあと、H問題を読むかと考えるが時間足りない.
そもそも、東大が3チーム解いていることを考えると、解けないことはないけど、どうしようか悩んでいた.
実は簡単枠なのではと考えを張り巡らせたが、疲れ切っていたので幾何ライブラリの写経を行っていた.

ここで，タイムアップ

3:00

感想

後輩チームに負けるかとヒヤヒヤしていました.
去年の上手く行ったチーム体制をベースとして、去年の反省点をちゃんと活かした上に、チームメイトが大活躍してくれたので大満足です!
osrehun.hatenadiary.jp

国内予選に関しては有終の美を飾れたかと.
これ以上の成果を残すには、国内予選全完を目指さないといけないですね... (つまり、H問題を解ける人材が必要となる)

チーム面

特に，チームメイトがG問題をACしてくれたのが，今年の特筆すべき点だと思います．
正直な話、これまでのコンテストでは自分が解ける問題しか解いていなかった気がします.
レーティングとコンテスト成績から、チームのメインコーダーは自分です.
ただ、1人コーダーは非常に消耗するので，全部問題を担当するのは非常に辛い面があります.
そんな中で，自分がほぼ関与せずにG問題を解いてくれたのは、非常に良い面だなと思います.
そのおかげで、E問題とF問題を解くリソースが確保できたのでね.
あと，インフラ担当の機転と環境構築にはいつも感謝しています. 土台部分は非常に重要です.
チームコンテストならではの良さが発揮できていました.

個人面

自分は、解ける問題の数が増えて、Fまで解いたのが特筆すべき点です.
今年になってから、AtCoderで問題の作問やテスターに携わる中で、作問者視点でコンテストを考えることができたのも大きいかな...
「G1.inのテストケースを用いた反例探しなど」

今年の国内予選の反省点
特になしと言いたいけど、やっぱり5問も解くと疲れるので、もう1問くらいアウトソーシングしたい...

というわけで，アジア地区予選の練習をしていきましょう!

大学のサークルとしては，今年は去年と同じ3チーム参加でした.
「I MUST GO」(初参加)は4完、「.」は3完していました．
ICPCを終えたら、後輩育成に力を注ぎたいかな...
後輩チームにもこのレベルを目標に頑張って欲しいです.

国内予選の振り返り

nocowは2014年に結成されたチームで、このチームで出場するのは4回目で、今年で引退です.
これまでの国内予選の結果は次の通りです.
2014年 (国内予選落ち)
icchy.hatenablog.jp
2015年 (国内予選落ち)
osrehun.hatenadiary.jp
2016年 (国内予選通過)
osrehun.hatenadiary.jp

これらから分かることは、nocowは最初から強いチームという訳ではありません.
また、3人とも大学入学してから競プロを始めています. (多分そう)
練習すれば強くなる余地は大いにあるんだなとこの4年間で感じました.

追記

f:id:osrehun:20170715130933p:plain

インフラ担当の記事
icchy.hatenablog.jp