今回、CODE FESTIVAL 2015に参加してきたので、このことについて書いておこうと思います。
去年のTHANKSと同じ調子でコードと参加記をまとめて書いていたら長くなったので解法編と参加記編で分割しました。
こちらは二日間のコンテストの問題についての私の解法を書いています。
＝＝＝＝＝＝ 1日目 ＝＝＝＝＝
――――― 本戦 ―――――
code-festival-2015-final-open.contest.atcoder.jp
3時間10問で、解けたのはA問題~E問題の5問でした。
A : コード川柳
文字列575するだけ
cf-final-a.py
B : ダイスゲーム
Combinationとかで確率求めて最大の数出力すればいいかなーとか思っていろいろやってたけど、思考停止して [期待値*サイコロの数] を計算
一回N=1の時を考え忘れてWA食らったけど、そのケースも含めたらいけた
cf-final-b.py
C : 寿司タワー
分解が必要になったら分解しながら貪欲したら通った
スタックを使って分離して余ってるものを管理
N文字分までしか考えないなどのちょっとした実装ミスで2WAしたけどその後修正して通した
cf-final-c.py
D : 足ゲームII
priority_queue２つ用意して、うまく人を割り当てることで通した
- 一つのpriority_queueで押している人の管理(押し終わる時間で昇順)、もう一つのpriority_queueで手が開いている人の管理(点で降順)をする
- 押す時間を早い順にソートしておき、点をたくさんとっている人から割り当てるようにする. 空いている人がいなければ人を追加する
- 割り当て終わった後に1点しかとってない人がいれば1人少なくでき、いなければ減らせない
cf-final-d.cpp
E : ショートコーディング
出力の状態が6通りになるので、状態遷移させまくってそれぞれの状態に応じた出力をする
| idx | 状態 (N!=0) |
次の状態 | 最後の出力 | |
|---|---|---|---|---|
| 入力"-" | 入力"!" | |||
| 0 | [N,0] | [-N,0] | [0,1] | "" |
| 1 | [-N,0] | [N,0] | [0,1] | "-" |
| 2 | [0,1] | [0,-1] | [1,0] | "!" |
| 3 | [0,-1] | [0,1] | [1,0] | "-!" |
| 4 | [1,0] | [-1,0] | [0,1] | "!!" |
| 5 | [-1,0] | [1,0] | [0,1] | "-!!" |
cf-final-e.py
G : スタンプラリー
A~Eを解いた時点で順位表を見たところ、FよりGの方が解いている人が多かったのでFは飛ばした。
問題分を読んだらDPっぽい匂いがしたのでどう落とせばいけるのか考えて
dp[i][j]=(Ci~Cjが一直線に並んでいる通り数)
みたいな感じで考える
この考えで計算したら頂点をつなげるときの通り数の計算が複雑で詰んだ
＝＝＝＝＝＝ 2日目 ＝＝＝＝＝
――――― あさプロ(Middle) ―――――
1時間半で4問(Easy,Middle,Hardそれぞれ, EasyとMiddleの3,4問目はひとつ上の1,2問目にあたる)
私はMiddleを選択して、解けたのはA,B,C問題の3問でした。
A : ヘイホー君と最終試験
最初は上k個持ってきて、平均がR以上であれば0を出力
下回れば上(k-1)個を持ってきて、それにどのくらいの値を持ってきたら平均がR以上になるかを計算しM以下であればそれを出力、それより大きければ-1を出力
cf-mm-a.py
B : ヘイホー君と削除
LCSが頭によぎったけど、ライブラリとして持ってなかったし実装方法すぐに思い浮かばなかったので直感的に考える
その結果、最初に同じ文字を選んで、そこから文字が一致するかを深さ優先探索した
最初は適当にDFSしたのでTLEくらったけど、メモ化してO(N^4)にしたら通った
cf-mm-b.py
C : 一次元オセロ
Nは奇数という条件が与えられているので必ず両側が白いコマになり、片側に黒を置いた後は白は同じ側に置くしかなく、再び両側が白いコマになる
これを踏まえ、黒->白と置いていく時にひっくり返すコマの数が少なくなる側に貪欲に置いておけばできそうな気がしたのでdequeで処理していったら通った
cf-mm-c.py
D : 立方体とペンキ
いろいろ考えて、セグメント木とか使って上から立方体を削っていけばいいかもという考えに落ち着いたが、この方針は根本的に間違っていたのでだめだめだった
――――― 短縮王 ―――――
C言語のコードゴルフに自信がなかったのでPythonで解いてみました。
Pythonもコードゴルフの経験がなかったので、ある程度以上は短くすることができませんでした。
A : もし解けなかったら木の下に埋めて貰っても構わないよ
問題はやるだけ. mapの中にinputを突っ込めることに気がついた
cf-sc-a.py
B : Union Find
問題名どおりUnionFindする。実装手を抜けるかなと思ったけどそうでもなかった
もうちょっと削れそうな気がしたけど削れなかった...
cf-sc-b.py
C : 割り算と足し算
再帰してNの時を求めた。
f[x]=(xの各桁の数字の和)+(x>yとなるxの約数yについてf[y]の最大値)
という感じで計算
この問題を解いている時に"`x`"という書き方でxの値の文字列が取れる(正確には"repr(x)"と同じ)ことや、"~-x"でデクリメント、"-~x"でインクリメントできることを知った(計算の優先順位的に括弧を省くことが可能)
cf-sc-c.py
D : 数列圧縮
端から足していきながら数字が合うかを確認していく
深さ優先探索
cf-sc-d.py
――――― チーム対抗速解きリレー ―――――
一人１問、1チーム10人で合計10問(A~J)
私はG問題担当でした。
G : 主菜と副菜
主菜は1個、副菜は0個以上だったので、副菜に対してナップサックして、その結果に主菜を組み合わせて最大になるものを出力すればO(N+ML)でおｋ
M*L<=10^7で、計算量的に多そうだったのでC++で書いた
急いで書いた所、見事にバグらせてしまったが、チームメンバーの指摘のおかげで最終的にはACできた
↓がACできたコードcf-relay-g.cpp
自分で書こうとしていたコードを後で見なおしたところ "j-vb[i]<0" のときに代入し損ねてた...（＝＿＝；）
他にもいろいろミスがちらほらあった
cf-relay-g2.cpp
もうちょっと落ち着きながら早くコーディングできる人になりたいです(-_-)
