katsu_y practice 011
記録: hadrori
問題セット
2014/09/17 15:40 - 20:40 (5h)
練習前
黒ハンバーガーの画像を眺める.
アメリカのおみやげを貰った
練習
0分
h「どれから読んでく？」
p「前と後ろから？」
s「全員前から順番にでいいと思う. A読む」
p「B読む」
h「C読む」
8分 A AC
s「やるだけ」
h「Bいけそう？」
p「ちょっとサンプルで詰まってる. Cは？」
h「題意はわかったけどよくわかんない」
h「Cの題意はこんなかんじ. とりあえずD読みます」
p「B勘違いしてた. 書く」
29分 B AC
p「C, 誤差ガバガバ解法とかできないかな. すごい後ろの方は適当に無視するとか」
h「Dはこんな感じの題意. 問題文中の変数が分かりづらい」
s「Wが決まればいいよね」
h「はい」
s「グラフの形が簡単. 3分探索でいけるのでは」
p「確かに」
s「書いてみる」
h「E読む」
p「C考えてみる」
p「Eどう？」
h「題意はこんな感じ」
p「どうせ2個しか見なくていいとかじゃない」
49分 D AC
s「D通った. F読む」
p「G読む」
p「Gはこんな感じ. 分割数っぽい」
s「Fはこんな感じ. G考えてみます」
ここからGの実装とEの考察をしばらく黙々とする.
s「G書いてみます」
s「mod_factのライブラリが必要かも」
h「はい」
s「やっぱりいらなかった」
s「投げてみる」
84分 G WA
s「えっ」
s「あっオーバーフロー」
86分 G AC
p「Eの実装をする. ペアプロよろしく」
h「はい. Hはどうせ構文解析やるだけなので読んでおいてください」
s「はい」
h「あれ, 入力直径だっけ. 」
p「半径だけど」
h「この式2倍しなくていいの？ ん, いいのかなんでもない」
p「サンプル合わない. あっ2倍してないじゃん. さっきそい(hadrori)が言ってたとこじゃん. もっと強く言ってくれ」
s「誤りを検出しているのに機能していない」
p「E投げる」
96分 E WA
s「H書く」
h「Eのコード2部印刷よろしく」
p「これ方針間違ってるやつかなあ」
h「あっ, こんな感じで連なってるケース死ぬじゃん」
p「あーあ」
118分 H AC
s「やるだけ」
s「I読みます」
h「じゃあKから読んでいきます」
p「E直します」
s「Iは彩色数やるだけに見えるけど」
h「包除でやるやつならライブラリにあるよ」
s「指数の底が1.6とかじゃないと無理なやつだから, 多分枝刈りしてやるやつ. ライブラリゲーっぽい. パス」
s「Jはなんか広告をみてポイントをゲットするらしい. やばげ. 強連結成分分解やるということはわかる」
h「Kはよく意味がわからないので読んで」
s「Kの題意は把握した. 面倒そうなやるだけ」
h「Cはどうすんだこれ. これもうセーブの位置が実は一意に決まるとか？ わけわかんない」
s「うーん, ちょっと考えてみます」
s「まだ5完しかしてない. やばい」
h「まだ2時間半だよ」
160分 E WA
p「どうすんだこれ」
p「あっlower_boundミスってた. 再提出」
p「WA. どうすんだこれ」
s「C書いてみます」
p「Fは多くても1しか増えないよね」
s「はい」
p「O(M2)でいけるかなあ」
p「Jはどう？」
h「題意はこんなかんじだけど」
p「強連結成分分解してO(NT)でいけそう？」
h「うーん, それでいけそうな気もするけど……」
p「けど？」
h「わかんない」
h「強連結成分分解して各強連結成分ごとにDPしてさらに全体でDPすれば, 始めのDPが全部合わせてO(NT), 後のDPもO(NT)で全体がO(NT)でいけそう？」
p「前者はlogつかないっけ」
h「？なんで」
p「よく覚えてないんだけど個数制限付きナップザックはlogつくじゃん？1,2,4,8…ってやるやつ」*1
h「あー個数制限か. 忘れてた」
176分 C WA
s「あっ明らかにおかしいじゃん. なんでサンプル通るんだ…… 再提出」
s「WA. うーん, 何がダメなんだ」
s「Kを書きます」
s「サンプルが合わない…… あっわかった」
195分 K AC
p「E修正する」
h「Jは解法は多分分かった. 強連結成分分解してそれぞれDPしてさらに全体でDP」
s「はじめのDPいりますか」
h「もどって来れるかもしれないので」
s「ああ……めんどくさ……詰めあわせましたって感じだ」
p「分割して書けば普通になる」
s「Donutsのコンテストに今から出ます」
224分 E WA
p「Eもう何がダメなのかわかんない」
Eがしばらく泥沼
h「standingsによるとJが6チーム, Cが5チームに解かれている. Fはいっぱい解かれてる」
p「やっぱFか. F書く」
h「Cこれどうすればいいんだ. 他と違って方針が全然見えない」
s「Donuts終わった. みんな強い」
277分 F TLE
p「えっこれダメなのか」
s「Cをちょっと直して出してみます」
294分 C WA
終了
練習後
解説スライドを見る.
C あー誤差ガバガバ解法って言ってたやつだ……
E 解法合ってるんだよなあ
F パスの有無のチェック, 言われてみればそうだよなあ
I まあ枝刈りですよねえ. よくよく考えると幾何パートも結構やばく見える
J 解法全く同じ
反省
ペアプロの時ははっきりと納得がいくまでコーダーに説明してもらったほうがよさそう.
解法自体は出ているのに実装力が足りない.
Cは他にできることがなかったし試すべきだった.
問題の割り振りをもう少しちゃんとやるべきだった.
*1:スライド最大値をやればlogが取れます
