katsu_y practice 012
記録: hadrori
問題セット
2014/09/22 13:15 - 18:15 (5h)
計算機室が17時までしか空いてなかったので途中で移動を挟む.
練習
0分
s「A読む」
p「B読む」
h「C読む」
2分 A AC
s「やるだけ」
h「Cは3次元上の線分と球の交差やるだけ」
s「地味に面倒じゃないですか?」
h「そうですか?」
s「あ, できるか」
s「Dは自炊パワー. よく分からないからとりあえずCやります」
s「難易度順とは限らないからとりあえず問題読んでいって」
h「後ろから読んでいきます」
p「Eから読んでいく」
h「EFGどんなかんじ?」
p「Eはたぶん書かれたプログラムを実行するだけ」
p「Fはクエリごとに文字列Sに含まれる位置の左端と右端をみる. サンプル見るとすぐわかる」
p「Gは鉄鉱石から道具が作れるらしくて, 道具と鉄鉱石を合わせてつくる道具もある. 最初に
持ってる鉄鉱石から目的の道具が作れるか」
h「なるほど. Hは読んだ?」
p「少しだけ」
h「トーナメント表があって, 順位表をもらったけどそれが同じ順位が連続しまくってバグってるらしい. 最小何回の変更で矛盾のないものに変更できるか」
27分 C WA
s「えっまじで. 何が違うんだ」
p「とりあえずEの実装を始めます」
h「Cのデバグします. 先にFからの題意説明しときます」
F~Hは省略
h「IはDAGがあって, ある頂点について他全ての頂点に移動できるようにするために逆向きに変える辺の本数が決まります. その本数が最小になる頂点を列挙しろ」
h「Jは凸多角形があってその内部をm個にそれぞれ決められた面積に分割, その領域が最も近くなるような点をそれぞれ求めよ. ちょっと言葉にしづらいから図を見て」
s「あーボロノイ図」
h「あっそっか」
s「とりあえずFはSAやるだけ?」
h「たぶん. あとやるとしたらHかなあ」
s「だなあ. 区間でみていけばsegtreeっぽいかんじ?」
s「Gは不穏な感じのコメントがあるしスルー安定か」
h「C, コストdoubleで持ってるのって大丈夫?」
s「あ, ギリギリやばいかも. というかなんでdoubleで書いてたんだ」
s「でもそれだけじゃこんだけのケース落ちるとは思えないなあ. 内積間違えてたりしてるかも」
s「あーこれ間違ってるじゃん」
51分 C AC
h「Eはどうなってる?」
p「ちょっとバグってる. 他に出来そうなのある?」
h「うーんびみょい」
s「Hあの方針だとダメだ. 他の山で勝つやつのことを考えてなかった」
s「F紙コーディングします」
74分 E WA
77分 E WA
p「あーあ. 印刷しよう」
s「3部で」
87分 E WA
s「問題のプログラム内のwhile文で無限ループってありえますよね」
p「あー確かに. 直す」
99分 E WA
p「微妙にWA残る. あとTLEもある」
h「Eじゃないんだけど, B問題って右手法やるだけでルートが一意だし最小のマスの数とか関係なくないですか」
ps「確かに」
p「やるだけか」
p「ダメそうだから先にBやる」
128分 B AC
129分 E WA
h「Eちょっともうここからバグ見つけるのきつそうだから実装しなおした方がよさそう」
s「F書きます」
p「Eの再実装よろしく」
h「紙コーディングする」
172分 F WA
s「smallケースだけ落ちまくってる. うーん」
176分 F WA
182分 F RE
s「RE. 繰り返してるやつで死んでる」
185分 F RE
196分 F RE
s「何がダメなんだ」
h「E紙コーディング終わってるのでとりあえずそっち書きます」
202分 F RE
208分 F RE
210分 F RE
s「Fだめだ」
p「Dがいけそう」
h「すぐ書ける?」
p「式書き写すだけだからすぐ終わる」
p「あれ, サンプル合わない. 手でやったのと違っちゃってるなあ」
h「Eバグっちゃったなあ」
225分 計算機室が閉まり中断
s「西7の演習室行ってみましょう」
開いてない
s「西8の10Fリフレでやりますか」
240分 再開(移動時間分無視)
p「Dは凡ミスしてた」
247分 D WA
p「あっlong long」
248分 D AC
p「やったぜ」
254分 E TLE
h「1つだけTLE」
p「一応進歩してる」
h「これ気づいてないケースかなあ」
277分 F WA
s「前よりひどくなってる」
p「E, while文でループしてるときif文とか何回もパーサ行ったり来たりしまくるとTLEしそう」
h 「なるほど確かに. メモ化してfalseのときは一気に飛ばすか」
291分 E TLE
h「だめかあ. 何がダメなんだ」
s「これ普通に長さ足りなくてREになってたやつだ」
300分 終了
5時間経過. まだFがなんとかなりそうな感じだったので続ける
p「H, 2時間ぐらいあれば実装いけそう」
s「Fこれ普通に長さ足りてなかったやつでは」
318分 F MLE
s「MLEまじかよ. 全部固定長で取ってるのに」
s「厳しすぎる. 削れるところ削っていくか……」
h「Eちょっと直してみます. 直すというよりは実装を少し変える程度ですが」
352分 E AC
h「えっ通るの. doneのチェックをprogramでやってたのからwhileでやるように変えただけなんだけど」
p「なにが違うんだ」
h「もう飽きた」
p「腹減った」
s「......(Fを直している)」
367分 F WA
372分 F AC
s「やっと通った. 2秒かかってるしRMQをsegtreeでやってたらTLEしてそう」
練習後
s「人々segtreeで通してるなあ. segtreeだと最悪ケースを取り得ないのか」
s「sparse tableはn log nがっつり使っちゃう」
反省
実は実装開始時刻を全部メモしておいて, 実装に時間をかけすぎてたら打ち切ったりしようとしてたけどメモするのははじめから完全に忘れていた.