競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

Code Thanks Festival 2015 Open Contest 参加記

こどふぇすは本選出場したので感謝祭はオープンコンテスト
Welcome to CODE THANKS FESTIVAL 2015 オープンコンテスト - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder
のはずだったのですがバイトのあとの昼寝で寝過ごしたので終了1時間後からコンテストスタートです
一応3時間計ってやりました

A-金庫

abs(A)+abs(a-b)+abs(B)でいいのかな
とりあえず投げよ
AC:1分ぐらい
Submission #587967 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

B-袋とボール

思考停止map>で各数のペア保存すればいけそう
AC:8分ぐらい,遅すぎうんこ
Submission #587989 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

C-集合写真

二分探索組むの面倒
ソートして数えてほい
=書き忘れて1WA
まあペナルティなさそうだしせーふ
AC:14分,びみょ
Submission #588010 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

D-暴露

記号多くてきれる
とりあえずp[i][j]=iが知ってるjの得点,知らなければ-1
p[i].total=iが知ってる得点の合計
知らない人の取りうる得点の最大値=min(total-p[i].total,100);
知らない人の取りうる得点の最小値=max(total-p[i].total-(N-p[i].know-1)*100,0)
AC:47分,30分以上もかけてて冷える
Submission #588052 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

E-ノイズ除去

tに含まれない文字は全て削除しておっけーです
サイズ小さいからstring.find使う
使い方知らない
ぐぐる
TLE,クエリ数のデクリメント忘れてた,atcoderのみなさんごめんなさい
AC:59分
Submission #588068 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

F-お祭りとお菓子

TL見た感じここからが本番っぽい?
すでに1時間かけてて冷えてる
1からの距離が偶数のノードが勝ちノード,奇数のノードが負けノードとなる
勝ちノードとなっている葉が奇数個ならAさんの勝ち
そうでなければBさんの勝ちとすればよさそう
コーナーケースとして1が葉ノードのときAさんの無条件勝利
WA:80分


なんか違う気がする
距離じゃなくてそのノードが葉になるまでに必要なターン数数えなきゃダメかも
BFSしなくていいじゃん
コーナーケースはそのままで,あとはN-1が奇数か偶数かで決まる
N-1が偶数ならAの勝ち,つまりNが奇数のときAの勝ち
あれ合わないなんで

ああそうか違うわ

なんやかんやでWAを量産

1にくっついてる部分木のサイズの偶奇で判定できそう
全部偶数なら勝ち
奇数二つでも勝ち,多分
多分奇数が偶数個で勝ち
AC:116分,くそ辛かった
Submission #588113 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

G-カメレオン

(頂点*体色)の拡張ダイクストラでいけそう
ここで問題があって,普通にやろうとするとメモリが足りない
ぐっとにらむととO(M)しか状態がいらないことがわかる
座圧するのめんどいから状態をmapで管理しても間に合うかな?
map,時間>
M*(logM)^2
こっわ
80000*80*80
座圧しましょうねー
隣接リストとして,各頂点からどの頂点にどのぐらいの時間がかかって何色になるかを保存しとく
終点の頂点番号は座圧後の値
怒りのstruct UNKO
サンプル通ったので勝ちを確信 submit
TLE
入力多いのにcin使ってるのが原因っぽい
他にもダイクストラ周りの無駄を省略
AC:180分ぎりぎり
Submission #588160 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder

H-穴あきケーキ

3時間を過ぎてしまったのでやる気がきれかけている
やります
愚直にやるとO(R^3C^3)
まず累積和を取ります
a,b,c,dを全部決めてたら間に合わんね
350^4から逃れられない
e,fを決めてごにょごにょするのかa,bを決めてごにょごにょするのかのどっちかだと思うんだけど
無理やろこれ
解説見ます
@camypaperさんが取り除く整数を固定するとかいってる
e,fを決めてごにょごにょするっぽい
想定解O(RC^2)なの
ケーキのコスト9までじゃん!!!
0から9までの個数カウントすれば普通に行けそう
とりあえずN^4書く
TLE
まあそりゃそうですよね
ネックなのはずっと0のところ
10*log(N)とかでどうでしょう
減らせそうではある
やる価値あり
問題文を読み飛ばしていた
各ブロックのカロリーは0からではなく1からでした
O(R*R*C*(9+logC))で解けますね
にぶたんでバグらせまくった
AC
Submission #588294 - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder



無事全完ですが一日をこれに捧げた感ある.
Gの拡張ダイクストラの状態数が最大でも辺の両端の個数にしかならないというのは面白かった
H以外は解説見ずに時間内で解けたので7完ということで