ICPC２０１８国内予選参加記

ニャ

先日開催されたICPC国内予選に参加してきました。その感想などを書きたいと思います。 チーム名はTigerzet、チームメンバーは

etonagisa(@eto_nagisa)
nikutto(@nikutto_)
gazelle(@gzlcp)

チーム名はメンバーの名前から少しずつとって作りました。そうは見えないでしょうけども。

戦略

基本的に考察はnikuttoが最強なので、gazelleとぼくでABCを解いている間にD,Eあたりをnikuttoに考察してもらうという作戦でやっていっています。 しかし今回は実験室のプリンターが使えず、問題を同時にせいぜい２つぐらいしか読めなかったので作戦が破綻しました(チーン)

できごと

開始直後

nikuttoにテンプレートを書いてもらいつつ、A問題を読む。やるだけなので実装方針を考えつつテンプレートの完成を待つ。double嫌いマンなのでn*v[i]<=sumで比較しましたね。

(3:57)

A問題AC。
Aを書いている間にgazelleにBを読んでもらっていた。こーれは大変そうだと思いつつ、しばらくBを任せる。その間にCを読んでいた。

(7:00ぐらい)

アーこれは√bまで累積和をとるだけですねハイ(嘘)と言ってBに戻る。戻ってすぐnikuttoが方針を提案してくれた。可能なフロアの長さの最大値は√bぐらいなのでこれを全探索して判定問題にすればよいといわれる。確かにこれでよさそう。紙コーディングしつつBを見る。 Bは計算量はなんとでもなるのできれいな方針で実装するだけのやつだとわかる。折る旅にあたらしい配列を用意して、折り目から折り目と垂直にたどって新しい配列に足していくという方針を提案、これが受け入れられ実装をしてもらう。これが結構大変だった。

(37:41)

B問題AC。

(43:44)

Cは方針も実装も固まっていたので一瞬で書けた。 C問題AC。
Cを書いてnikuttoに進捗どうですかをすると、Dは枝刈り全探索するだけだという。確かにサンプルに最大ケースがあり、計算回数がこれで抑えられそうであるので、それでいいですといいペアプロに入る。ぼくは隣で些細なミスを指摘するだけで終わり、一瞬でDが書きあがる。天才か？

(58:05)

D問題AC。
F,G,Hを読んで考えていたgazelleと一緒に考察を進める。その間にnikuttoがEを書くというので任せる。Fの知見が少し生まれたり、Gを考えたりHがフローっぽいな～～～って言っていた。

(1:29:28)

そうこうしているうちにEのサンプルが合わなかったり合ったりした。提出。通った。nikutto天才か？？？？
E問題AC。
この時点で順位表を見たところ４位だったので盛り上がっていた。 Fは我々には解けませんとなったのでGを頑張ることにした。

(2:00ごろ)

gazelleからGの完全な考察がわいてきた。曰く、カッコの途中で文字列を打ち切ることは許されないので、カッコを使う場合はカッコ内全体をすべて使う必要がある。すると、カッコは定数と見なせるので、定数と+と*からなる式で、計算結果がnになる部分文字列を見つければよいという問題になった。式の値は広義単調増加であるので、これはしゃくとり法でできる。カッコ内についても部分問題を解くことで答えが求まる。これで合っていると確信。ただし実装がクソ重いことがわかっていた。 nikuttoはHを解いていたが、諦めて３人全員でGに取り組むことにした。

(2:50ごろ)

Gがかけた。実行！！どんなケースでも０が返ってくる！！(これは間に合わんな・・という雰囲気になった)がまあしばらく頑張ってみる。

(3:00)

Gは無理でした。

結果

5完8位、学内では3位。まず、ここまでの高順位をとれるとは思っていませんでした。5完早解きセットで早解きができたことが大きいのかなと思います。 それと今年はKUが強い・・。KUの上位は6位、7位、8位、11位となって、11位のチームが予選落ちしそうというまさかの結果になってしまいました・・かわいそう

今回はnikuttoにだいぶ活躍してもらいました。アジア予選横浜大会ではもっとチームの力になりたいですね。