Hatena::Grouptopcoder

zerokugi's contest memo

2014-07-11ICPC2014 国内予選参加記

ICPC2014 国内予選に参加しました

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

結果は ABCDEF の6完で全体3位、大学別順位2位でした

分担は

A @logicmachine

B @logicmachine

C 解法:@zerokugi @n_vip 実装:@logicmachine

D 解法:@zerokugi    実装:@logicmachine

E 解法:@zerokugi @n_vip 実装:@logicmachine

F 解法:@zerokugi @n_vip 実装:@zerokugi

(G) @logicmachine


基本的な方針は @zerokugi @n_vip の二人でひたすら問題読んで解法を考える

決まったら @logicmachine に投げて実装してもらう

ってかんじです

開始前

使う予定だった部屋が16:30まで授業で使用するらしくて急遽実施場所を変更することに。

模擬の時と違う環境になったのでひと通りの動作確認をしなおしてから2時間ほど暇な時間を過ごす。

コンテスト開始

@logicmachine A読んで実装

@zerokugi B読む

@n_vip 印刷した問題の整理とC読む

A問題 AC (0:06)

とくに問題なく通る

B問題 AC (0:14)

とくに難しいところはなかったので問題概要と制約だけ伝えて任せたら通っていた

Dがすぐに解法浮かんで実装も楽そうだったのでCより先にDから書いてもらうことに

そのままCの解法を考えてみるも実装がめんどくさそうな解法しか思いつかない・・・

D問題 WA (0:25?)

列挙した文字列から重複を削除するのを忘れていて1WAが出る

自分が想像していた実装は重複は現れない感じだったので指摘し逃してしまった。

D問題 AC (0:28)

Cをちょっと相談して最終的にビルのてっぺんに線分貼って円を少しずつズラしながら交差判定を行う感じで実装してもらう


Cを実装してもらってる間にEFGの問題概要を @n_vip から聞く

Eは典型木DPだな(思考停止)って感じだったので適当に紙に式をまとめたりする

各部分木について「葉ノードを除いた全子ノードを巡るコスト」と「葉ノードを除いた全子ノードを巡って根に戻ってくるコスト」の2つを求める感じの木DP

C問題 AC (0:48)

Standingsを見ると6完が見えて慄く

DPの式がまだまとまってなかったので軽く説明して実装してもらいながら細かい所を詰めていく

E問題 AC (1:08)

とりあえず5問早解きできたので予選突破は確定かなーと思い気が楽になる

ぱっと見FGは人間が解く問題じゃないように見えた


とりあえずFGの問題情報を共有して3人でどうするかの話し合い

@logicmachine 曰くGの方針が立ったかもしれない、とのことなのでGは任せてFを考える


@n_vip と二人でFを考える

5000*6の場合のケースを考えてみると、辞書順最小なので最初は大量のEで埋まっていくはず

どこまでEを選び続けるか、を考えると

・前:5000のまま、 後:5000のまま、 上下左右:1ずつ減っていく

と変化していく前提でゴールに到達できない条件は

・(前+後 > 上+下+左+右+1)

ということがわかる(前か後の数字を1減らす為には上下左右のどれかを毎回経由しなければいけないため)


以上から 前後の組み合わせ3通りのうちどれかに対して↑の条件が成り立つ場合はゴール不可能と考えて

1. とりあえずできるところまでEを選択

2. その後辞書順最小に貪欲に選びながらゴール不可能になったらバックトラック

という解法案を考える


PCが空いてたのでとりあえずサンプルが合うかどうかとどのくらい時間がかかるかを確かめるために↑を実装してみる

(サイコロのライブラリを印刷してなかったので一から実装するハメになってしまった)

サンプルが合ったのでinput落としてきて走らせてみる

ゆっくりだけど現実的な時間っぽいのでいけるんじゃね?と思いつつ待ったところ2分ほどで出力が得られる

F問題 AC (2:24)

出力待ち中にいろいろ考えてみたところさっきの到達可能性条件は常に必要十分条件になってるっぽい気がしたので TLE じゃなけりゃ通るんじゃね・・・?と思った

が、流石に Correct Answer! の文字が見えた時は叫んでしまった

(そして Standings 開いて2位に浮上したのを確認してさらに叫ぶ)


Fを実装してる間にGの解法が詰められたらしいのでGの実装開始

解法の説明を受けるような時間は残ってなかったので黙ってじっと実装を見守る(完全にギャラリー会と化していた)

G問題 WA (2:57)

サンプルは通ったもののあえなく撃沈

見るからにヤバいGの実装が30分で終わったことに驚愕した

コンテスト終了

終了後に E の最長路を引く解法を聞いてなるほどな~~~~って感じだった

結果は全完が増えてて一つ順位が落ちてたものの3位という文句なしの順位で満足

途中ほとんどハマることがなく、反省点はあるものの現時点でのわりと理想的な流れだったと思う

(ちなみにGは3行ほどの修正したら通ったらしい おしい)