katsu_y practice 017
記録: hadrori
問題セット
ACM-ICPC Regionals 2013 :: Asia - Jakarta コード
2014/11/05 15:40 - 20:40 (5h)
練習
s「Aやるだけっぽいので書きます」
p「BはDPっぽいけど更新式が少しかかるかも」
h「Jよくわからない. Iは考えればいけるかも」
10分 A AC
s「Bちょっといじってみる」
p「この英語の意味わかる? "c is neither a nor c"」
h「(She is neither a nor c...)aでもcでもないじゃないの」
p「えっだから……」
s「なになに?」
p「この文なんだど, これcじゃなくてbだよね」
h「ああ, cじゃなくてsheだと思った……」
p「Cはすぐできると思う」
24分 B RE
29分 B WA
s「なんで……」
p「C書く」
s「じゃあB印刷」
36分 C AC
s「とりあえず1つ実装ミスがあったので修正して出します」
40分 B WA
p「Dはこれパワープラントつないで最小全域木やればよさそう」
s「よくあるやつですね. なんかで解いたことある」
54分 D AC
h「Eは読みましたか」
s「DAGで始点から終点まで全ての辺をカバーするのに必要な経路の数」
h「Looking for a challengeでみたなあ」
p「双対グラフつくるやつだ」
s「OUPCでも似たようなの見た」
p「辺は2つにしか分かれないのか. それを使えばもっと楽にできるかも」
長い沈黙
h「standings見よう」
h「Fめっちゃ解かれてるしEは誰にも解かれてない……」
h「Fは端から舐めて, 一致するのがあったらすぐ置換でよさそう. より長いものを選べるとしてもそれは短いのに分割できることが示せる」
s「greedyか」
s「Gの傾きってどれくらい」
h「100まで」
s「それ100個priority queue作ってやっちゃえばよさそう」
h「確かに」
h「Iって他のコインを超えるような動きないから順序は一意だよね. コインひとつ固定すれば」
s「他がきまるからどれだけ動いたかを見てやればよさそう?」
s「I書くか」
s「あれ, Iよく考えたらそれが最適なのかよくわかんない. F書く」
127分 F WA
h「Fデバグするので印刷して. その間にG書いちゃって」
134分 G WA
s「えっ」
s「あーこれpopしまくってる」
139分 G RE
s「えっ」
h「あっrは0もある」
141分 G PE
s「Presentation error?????」
h「最後の改行とか? あっコロンの後ろのスペースいらない」
143分 G AC
s「Fなんかわかりましたか」
h「わかんない……境界が怪しい?」
s「注意して書いたので大丈夫だと思う」
h「あっこの条件が死んでる」
s「あーほんとだ」
150分 F AC
p「Eがよさ気なので投げる」
157分 E AC
s「うーん, H書いてみます」
h「ぽにょなにやってる」
p「I考えてる」
h「Iなんだけど, 順序決まるので1個固定して時計回りを正として動く最大と最小を持ってきて均せば」
p「よさそう」
h「じゃあ書いといて」
185分 H WA
188分 H AC
192分 I AC
h「8完」
p「ThanQにならんだ. Bを通せば勝ち」
ランダムケース投げてナイーブ解と比較するも完全に一致.
またジャッジが死んでたのでは〜???とか言って投げるもWA
残り1時間程度残っていたが諦めてググる.
中国人のブログを発見し覗いてみると200という数字が見える.
制約が100で幅をとるので200必要と気付き……
s「あっ, 配列サイズミスってる……」
264分 B AC
反省とか
Jakarta優勝ぐらいの成績だったのでよい(強い学校(チーム)が少なかったのもあるが).
Eを知っていたのは大きかった.
やはりいろいろな問題に触れておくのは大切.
バグバグアンドバグをどうするか.