Hatena::Grouptopcoder

zerokugi's contest memo

2014-10-23ICPC2014 東京地区大会 参加記

ICPC2014 東京地区大会に参加しました

メンバーは @logicmachine @zerokugi @n_vip の3人です

結果は ABCDEFG の7完で全体6位、大学別順位5位でした

@logicmachine さんによる参加記も合わせてどうぞ http://d.hatena.ne.jp/logicmachine/20141020

基本的な方針はいつもどおり @zerokugi と @n_vip君 が問題を読んで解法を考える → @logicmachineさんに伝えて実装してもらう

という感じ

とりあえず最初は

  • A: @logicmachine
  • B: @n_vip
  • C: @zerokugi

から読むと打ち合わせてスタート

開始(00:00)

@logicmachine さんが環境設定をしてる間にAを読む(なぜかいきなり予定と違うことをやりだす)

そのまま概要と解法をパパっと伝えてBが大丈夫そうなことを確認しつつCを読む

A問題AC(00:08)
B問題AC(00:16)

B問題は俺の知らないうちに通ってました

Cはちょっと悩んだけど区間が重なってない時だけ引き返すようにしたら良さそう、って感じで伝える

すると依存関係が折り重なってる時にうまくいかない事を指摘される

あれーこれ難しくないかと思ってたら c_i < d_i という制約を見逃していたことに気づく(あまりにも杜撰すぎた)

C問題ならこのぐらいだろうという勝手な思い込みで解法を詰めていなかったので反省

C問題AC(00:30)

@n_vip君からDの様子を聞くと,式変形して解く感じの問題らしいのでとりあえずもう少し任せておくことに

D以降は適当に読んでいく予定だったので読みやすそうなGを読んでみる

カッコの平衡を取る問題だったのでとりあえず折れ線を書いてみたところ,一番左にある閉じカッコと、フリップした所に一番近い0を取ってこれれば解けそう

そう伝えると遅延セグツリーで解けると言われたのでとりあえず写経しといてもらい式を整理する

あらかた式を整理できたのでぼちぼちACが増えていたFを読んでみるとクラスカルしまくるだけだと判明

写経中のGを置いておいてFから解いてもらうことに

2回ほどミスでペナルティを出してしまったものの無事AC

F問題AC(01:03 +2)

Dが難航してたようなので先にEの読解を@n_vip君にお願いしつつIJらへんを読んでおく

するとGが書けたけどサンプルが通らないらしいのでコードを読んで,想定してたのと違う部分をいくつか指摘する

サンプルが一致,そのまま提出するもWA

いろいろケースを試した結果、一番近い0を探して来るのではなく一番近い1を探してくる必要があることに気づく

SegTreeの実装を変えてそのまま求めるのは難しいらしいので二分探索で求める方法を提案

O(nlog^2n)になってTLEがする恐れがあるが,TLEしたらSegTreeをもぐりながら二分探索する方法に変えればいいやーということでとりあえず提出 すると無事AC

G問題AC(01:53 +1)
E問題AC(02:31)

Eもほとんど関与してません DPっぽく状態まとめて探索すれば求まるんじゃない的なことを言った気がする

Dは聞いたところバウンド回数を固定して建物を全て超えられるギリギリの角度を二分探索で求めれば解けそう

そこらへんを伝えて実装してもらう

角度で二分探索するうまい方法が考えられなかったけど出来上がったソースを見るとvyで二分探索していてなるほどなーと思った

サンプル2だけ合わないので適当に図を書いて考えてみると答えより下を通ってるらしい事が分かる

よく考えたら45度が一番効率が良いことに気がついて二分探索の下限を45度にしてもらうとサンプルが合ったので提出してAC

D問題AC(02:59)

なんとか必須っぽい7問を解いて一安心

確かこの時点で全体4位国内2位(かなりテンション上がった)

あと10分耐えればColorful Jumbo Chickenに7完されてもペナルティで勝てる…と思ってたら2分間に合わず追いぬかれてしまう

気を取り直してとりあえず残り4問を全員共有して方針を考えることに

  • H: 実装重い幾何 @logicmachine さん曰く頑張ればできるらしい
  • I: DPっぽいゲーム探索 できそうな気はするがうまい方針が見当たらない
  • J: なんか三次元幾何に落とし込めそうな問題 凸包取ったり平面で切ったりするのかなーと思うもうまく落とし込めず
  • K: あまり考察してないけど見るからにヤバそうだしとりあえず放置しておくが吉?

HIJ をそれぞれ一人ずつ担当することに決定

おなか空いたので休憩室に行きご飯を食べながらIを考える

dp[A or B][n][おいしさの総和] = min(必要な相手との栄養価の差)

というdpで解けそうだなーと思って紙上で再帰したりループしたりいろいろ試すもなぜかうまくいかない

もしかしてもっと複雑なことしないといけないのかなーとか若干諦め気味になる

ずっと悩んでたけど残り40分ごろであたらしい解法を思いつく

(http://topcoder.g.hatena.ne.jp/zerokugi/20141020)

方針は思いついたもののメモ化部分の実装をどうすればいいか迷う

この時ものすごい勢いでHを実装中の@logicmachine さんに変わる?と聞かれたもののH問題ACの芽を潰してPCを奪い取る勇気がなくて断ってしまう

その後残り20分ごろでHのコードが完成しサンプルを走らせるものの答えが合わず,デバッグも絶望的とのことだったので交代してIを書いてみることに

残り2分でとりあえず書き終わったもののサンプルでセグフォが出てデバッグが間に合わずに7完のまま終了・・・

コンテスト終了

Iは解法も実装の方針も間違っていなかったのでもうちょい時間があれば通せていたかもしれず、ものすごい後悔に襲われる

あと予定になかったとはいえ自分が実装する準備を何一つしてなかったのも問題だった

Trial Useでの練習とか自分用テンプレの印刷すらしてなかったのは論外

5時間コンテストになると流石にコーダー一人じゃ疲労がヤバいし、今後はもう少し自分が実装することも想定しておいた方がいいかもしれないなーと思った

個人としての課題はかなり残ったものの、チームとしてはとても良い結果を残せたのでそっちは満足です

イマイチ選抜ルールがわかっていないのですがとりあえずWF参加の可能性は高そうなので発表を期待してます

あと、台湾大会ではColorful Jumbo Chickenへのリベンジを目指してがんばりたいと思います

みなさん, 来年は, Twitter ID とアイコンが書いてある名札を下げてきましょう!!!!