コンテストページ： https://codeforces.com/contest/1183
A - Nearest Interesting Number(00:01:59)
N, N+1,... というふうに、順番にためしていけばよいです。
B - Equalize Prices(00:05:21)
B としてありえる範囲を保持しておきます。入力 x を見たら、区間 [x-k, x+k] との交叉を取りましょう。
C - Computer Game(00:13:26)
まず、すべて片手間にプレイしてもダメならば、ダメです。そうでないとしましょう。
主人公が楽しくプレイできる回数 は、
を満たします。また、プレイする回数よりも大きくなってはいけません。このあたりを式変形すると、
がわかります。
D - Candy Box (easy version)(00:19:02)
重複度の重複度を計算しておきましょう。 それを後ろから見て行って、袋に入れていきましょう。 袋が空っぽでなければ、各場所で 1 回だけ取り出して捨てることができます。 取り出して捨てる回数が答えです。
この袋は、中に入っている数だけが大事ですから、整数型の変数を使うと良いです。
E - Subsequences (easy version)(00:56:46)
何文字の部分列がいくつあるかを前計算です。 場所が異なるものの内容は同じである部分列を重複して数えないために、部分列の埋め込みを左貪欲マッチで固定しましょう。
部分列の埋め込み込み方を、左貪欲マッチに固定します。
dp[ 最後の添字 + 1 ][ 選んだ文字の個数 ] = 場合の数 を DP です。
初期状態は、dp[0][0]=1 です。
遷移は、基本的には dp[i][k] += p[j][k-1] for 0 <=j < i をしていくとよいのですが、s[i-1] が貪欲マッチになっている必要がありますから、s[j,i-1[ が s[i-1] を含んでいてはいけません。
毎回 j を全探索して良いですから、while 文で攻めましょう！
F - Topforces Strikes Back(01:19:49)
3 文字目 i を全探索です。決め打ちをして、2 文字目 j, 1 文字目 k を探しましょう。
これは、大きい方から順番にためしていけばよいです。 約数はあまり多くありませんから、スキップされる j の数はその分程度です。 また、各 j に対して、スキップされる k の数も、その程度です。 掛け算をすると、列挙すべき個数は Θ( (log N) ^ 2 ) であることがわかります。
j, k をそれぞれ while 文で探索をすると良いです。 組を priority queue に入れて行く謎実装に走ったのはどこのどなたですか？
G - Candy Box (hard version)(01:16:18)
先程の E で整数型を使っていたものを、priority queue に変えます。キーは f=1 なるものの個数です。
H - Subsequences (hard version)(00:58:57)
オーバーフローにさえ気をつければ、G の解法がそのまま通ります。 G の想定解はなんだったのでしょう。
成績
35 位相当です。レートより少し上と言った感じでしょうか。 ペナルティーが 3 つというのは悪くないのですが、前半に集中しているのは勿体ありません。 オーバーフロー関連など、くだらないミスをすることが、特にこどふぉだと多いです。 速解きコンテストでは命取りですから、対策を考えたいところです。
ムーブ
D まではすんなりです。G は D のハードバージョンで、決して難しくはなかったのですが、順位表を見て避けていたので遅くなってしまいました。
残るは、E, H の Easy - Hard ペアと、単独 F です。 E, H はかなり考察に時間を掛けてしまいました。 G はそこまでという感じです。
分かる問題を後に持ってくるという、Div.3 ルールではかなり損なムーブになってしまいました。AtCoder ルールならば最適な動きだったのですが…… 今はそこまで成績にこだわっていないとは言え、コンテストのルールに最適化した動きも心がけたいです。
バチャの様子
スギノキさん（ui_mtc さん）の呼びかけで開催されました。カツサンドさん（idsigma さん）も参加されようです。カツサンドさんとの接戦具合がすごいです。F 以外はすべて差が 6 分以内、解いた順番も（ほぼ同時を除けば）完全に一致、ペナルティーも同数という熱い戦いです。結局カツサンドさんは F に捕まってしまったようで、私の勝ちです！（ところで Grandmaster 以上の方々には安定して負けていて悲しいです。）
