FCCPC

FCCPCについてお伝えするブログ

katsu_y practice 013

記録: hadrori

問題セット

ACM-ICPC Regionals 2013 :: Asia - Phuket
コード

2014/09/29 13:30 - 18:30 (5h)

練習

0分

s「A読む」
p「じゃあBから」 h「後ろからよむか」

1分

s「Aは行列木定理やるだけでは」 そのまま実装開始.

s「精度が足りなくて厳しい」

h「Iが本当の意味でやるだけ」
p「じゃあ書く」

h「Jは連続する部分列の和がXを超える最小の長さ」
s「しゃくとり?」
h「たぶん」

h「Kは点がどの三角形に含まれるか答えるやつ. 数が大きい. 三角形のいち関係について謎の制約がある」
s「うーん」

24分 I AC

s「J書きます」

31分 J WA
40分 J WA
42分 J WA

s「だめ. 」

h「Hは有向グラフでどの辺を選ぶか等確率のとき辺のラベルが回文か, 目的地に到達できる確率」
s「目的地に到達できるかつ回文じゃないですか?」
h「そうだ」

h「Gは簡単. 謎の制約の小ささで実はなんかあるんじゃないかと思ってしまう」
h「Fは幅Wの箱に小さい箱を詰めて入れるときの入れ方の場合の数」
s「G書きます」

h「ぽにょは今何やってる?」
p「Cの式を立ててる」

51分 G AC

s「Jはhadさんが書き直したほうが速いかもしれないです」
h「じゃあちょっと書いてみます」

p「ちょっとC書いてみたい」
h「どれくらいで書けそう?」
p「そんなにかかんないと思う」
h「じゃあ先書いて」

p「あ, 制約無視してた. だめだ」

h「あ, これ負の場合あってしゃくとり無理なやつだ」

h「長さにぶたん?」
s「負があるから縮めたほうが大きくなる場合あるじゃん」
h「あー. というかそれでしゃくとり無理じゃんって言ってたんだった」

h「Eは毎秒1組スワップして列を直すのと, みんな一気に正しい位置に向かって動いたときのかかる時間の差」
h「Dは7セグメントの数字の各角を頂点, 棒を辺とするグラフとみて, 辺上にそれぞれk個の頂点が追加されたものを考える. グラフが与えられるので考えられる数とkの組を求めよ」

p「CはProject Eulerになった」
s「???」
p「この式をO(1)で求められればいい」

s「D書きます. あ, Eの方が速いか」
p「じゃあE書きます」

116分 E AC

この辺りからかなり詰まって混沌としてくる.

s「Dのkって正だっけ」
h「負ってなんだ」
s「いや0はないかってこと. あ, 書いてあった. k>0って書いてある」

152分 D WA

p「印刷して. デバグする」
s「何部?」
h「僕はCの式を直します」
p「じゃあ2部」

p「D, k=0の場合あるよね」
s「えっk>0って書いてなかったっけ」
p「それ漸化式を書く関係で書いてあるだけでは」
s「あっ」

159分 D WA

h「(やばい3乗和どころか2乗和の式が思い出せない)」
h「(導出どうやるんだっけ……)」
h「3乗和の式忘れたので教えてください」
ps「1次の2乗」
h「あっ, ちなみに2乗和は……」
ps「1/6n(n+1)(2n+1)」
h「ありがとう. 導出しようとしてたけどできなかった……」

h「それっぽい式に直したけどサンプルあわねえ」

h「たぶん直った」
h「手でサンプル試すよりコードに直してサンプル試したほうが速いので書きます」

192分 C WA

h「えっまじか」

p「vectorでstack書けばいけそう」
s「RMQ書けばいけそう」

p「書きます」
s「そのファイルJだよ」
p「あれ, これJじゃないっけ」
s「?」
p「え, この問題Jだよね. 数列のやつ」
s「あ, Jの話だったのか」

205分 J AC

h「Cはこれなにが違うんだ」
s「オーバーフロー大丈夫ですか」
h「llでやってるしたぶん. 計算途中もここが2乗で……あっここ4乗になってるじゃん死んだ」
s「tでくくれそう. というかt(t+1)でくくれば大丈夫じゃない」

230分 C WA

h「あ, t+1でくくると最後の項の引き算がくくれなくて, そこが結構でかくなるから死ぬのか」

233分 C WA

h「死んだ」
s「unsignedにしよう. というか最大ケース自明だし試せば……」

p「Eの一番最後の改行を抜いてみよう」

236分 D WA

s「だめだ」

h「C投げる」

241分 C AC

h「CはJavaでやっちゃったほうが良かったかもなあ」

その後Eをいろいろ試すもダメ

s「Aは全域木の数を求める. 求め方は問題文に書いてある」
h「Nが6までで埋め込めってことなのか」
s「でも精度が足りないんだよなあ」

s「とりあえず出してみるか」

260分 A AC

s「えっまじ? これジャッジがdoubleで比較しているのでは……」

p「B書いてみる」

289分 B TLE

終わり

練習後

ICPC アジア地区予選のチーム紹介のスライドをつくろうってなるが面倒になりやめる.
チーム紹介文も適当に済ませる

反省

サンプルだけでなくちゃんといろんなケース試すべきだった.
特に最大ケースを簡単に作れる場合はやっておくべき.