katsu_y practice 015
記録: hadrori
問題セット
ACM-ICPC Regionals 2009 :: Europe - Northwestern
コード
2014/10/10 13:40 - 19:00 (5h+20m(移動時間))
日本セットを想定してあらかじめ問題をAC数の降順に並べ替えて行う
記事内の問題番号は元の問題にあわせる
練習
0分
p「A読む」
s「C読みます」
h「Jから」
s「C一番簡単ってまじですか」
h「制約の見落としとかないですか」
s「うーん」
p「A書きます」
10分 A WA
s「あっCわかったので書きます」
p「A直します」
15分 A AC
17分 C AC
s「Iは与えられる点から単純多角形を作れ」
h「うーんどうするのがいいんだろう」
h「Bは木が文字列として与えられる. 部分木が一致するならその部分は以前登場した部分木の根の頂点番号に置き換えろ」
s「とりあえずそれですかね. 番号付は？」
h「登場順」
s「文字列の比較するだけっぽい？」
h「Hは5種類の6角形を規則のとおりに順に並べるとき, n番目の種類はなにか」
h「Fは木状の路線図があっていくつかの行きたい駅とその回数が決まってる」
h「どの駅に住むのが一番コストが小さくなるか. ただし行きたい駅に行ったら必ず家に帰るとする」
p「辺の両側の行きたい回数を比較してずらしていく感じとか？ どっちやればいい？」
h「Hやって」
p「バグってる」
s「B書きます」
p「印刷する」
h「2部」
s「これ何文字くるかわかんないな. ノード数は書いてあるけど」
h「各単語4文字までです」
p「あ, ちょっと直す」
84分 H AC
86分 B TLE
s「fgetsにかえて出してみます」
91分 B TLE
s「あっ手抜きしすぎた. これじゃだめだ」
p「多角形, ここをこうこうすればいけそうじゃない」
h「...」(聞いてなかった)
132分 I WA
139分 I WA
s「B書きなおして出します」
h「Dはフラクタル構造を深さdまでみる. 長さが全体のfになる座標を出せ」
p「？基準はこの斜めの線？」
h「？基準はこの線」
p「？？？」
h「えっ」
p「えっ」
164分 B WA
p「Dのfが0から1なのは？」
s「割合だから」
p「長さの基準ってこの斜め線？」
s「基準はこの図の形」
h「あっさっき何を聞いてたのか理解した」
s「これは簡単ですよね. 区間ごとに超えるか見ていけばいいんじゃないですか？」
p「Dの実装をします」
s「Fは簡単ですね」
h「Gはコインの両面に希望の部屋を書く. みんな順番にコイントスして部屋を決める. 被ったらやり直し. 部屋のレートが決まってて, 自分以外のコインの状況がわかってるとき決まる部屋のレートの期待値が最大になるような部屋の選び方は？ 同じのがあるなら辞書順最小」
s「出来ない場合存在しませんか？」
h「その場合はimpossible」
s「閉路含んだらそこは選べない. 木の場合がどうなるんだ」
h「とりあえず木になるか閉路が1つ以下を考えればいい感じ？」
s「閉路の場合はいいとして木の場合がなあ」
s「あっB間違え見つけた」
197分 B WA
s「えーなんだこれ」
h「デバグするから印刷して」
p「Dバグってる」
220分 計算機室から追い出される
外が工大祭の準備でお祭りって感じ.
240分 西8の8Fのリフレで再開する
h「Jは3次元空間上にワームホールがあってその中を通ると負の時間がすすむことを含めて時間短縮できる. ワームホールが開き始める時間も決まってる. 目的地までにかかる時間の最小」
s「ワームホールが開く時刻で区切ってその区間とワームホールの出入口と出発点, 目的地を頂点にしたBellman-Fordとか. 時間足りますかね」
h「ぎりぎり行けなくもない？」
s「あーでも行き先が多すぎるのか……」
h「ワームホールが50個だから100*50002ぐらいか. 厳しい」
s「区間ごとにBellman-Fordとか」
h「というと」
s「あーでもダメだ」
h「Dあれなら一回交代してF書いちゃおう」
h「Bはもうハッシュ衝突ぐらいしかWAの原因考えられないですね……」
263分 F TLE
s「えー線形なんだけど！」
p「Dを」
s「Iなんだけどさ, これx座標でソートして両端を繋ぐ線分に対して行きで上を通って帰りを下を通るようにやればよくない？」
h「確かに！それなら簡単だ」
h「Dあれなら先にI書いちゃおう」
p「すぐ終わるの？」
s「たぶん」
s「あれ, サンプル合わない」
s「あー境界上を通って帰るときか」
h「境界上と上と下で分けて上下の片方に存在しないならそっちに境界上をあげて, そうじゃないなら境界上は上のときにやればよさそう」
s「あーはい」
293分 I AC
h「Bハッシュ衝突かもしれないからmodとる素数を2つでやろう」
s「なんか括弧とかあるし264でやってもいけるんじゃないかな」
s「単純にmodが1e9ぐらいだと小さくて衝突しちゃう感じ」
297分 B AC
h「怒涛の連続AC」
s「ACRush！」
s「Fの入力大きいのでscanfにしてみます」
301分 F TLE
304分 F TLE
s「うへえなんだこれ」
p「D直す」
s「vectorを配列に直して……最近富豪プログラミングに慣れすぎていた……」
h「まあしばらくPKUで解かないとね……」
h「F, N回舐めるのが地味に多くて定数重くなってる？ 再帰まとめられないかな」
h「fillとmemsetだったらどっちが速い？」
s「memsetかなあ」
h「coutをprintfにしよう」
s「なんで」
h「列挙するときN回出すし」
s「あー」
315分 D WA
315分 D WA
s「出力がカンマじゃなくてスペースになってる」
h「あと2分！」
p「物語的に通るでしょ！」
h「主人公なら通るはず！」
318分 D AC
「「うぇーい」」
h「終盤の伸び」
s「いつもは終盤, というか後半なんもやってないからね」
320分 時間終了
Fが心残りなので通してから帰ることに
どのあたりで死んでるのかケース数でassertかけて二分探索とかいうsubmitデバグ
序盤ならなんかイージーミスしてると思ってやったが14ケース目で死んでるらしく微妙.
h「もうめんどいしテストケース落としてこよう」
s「14ケース目だけ異様に遅いですね. N=25000だけど. N=50000のケースは全て一瞬」
h「どんなケースか見てみよう」
s「1個だけ次数が高くてあとは次数1」
p「うにみたいなやつだ」
s「えっなんでこれだと落ちるの」
h「あーこの解法だと全ての頂点から入ってるから端から入って中心にいって, 中心から各頂点みるせいで辺をN2回みることになる」
s「あーなるほど」
h「根付き木になおして上る方向と下る方向でやる感じとかかな」
......(各人黙々と実装or考察)
395分 F AC
p「Fこういう解法はどう？ 始めに聞いたときに考えてたやつなんだけど」
s「うーん, それだとどう楽なんですか」
h「コストを持たなくていい分考えるのも少なくて楽そう」
s「そうかなあ」
p「結局何問解けたんだっけ」
h「Fいれないで6問」
p「順位表見よう」
h「6完だと4〜7位, 7完は2チーム」
反省
計算量がやばくなるケースを考えつけなかった
Fは実装を変えるべきだったかもしれない
全体的には悪くはない感じ
