めっちゃ問題ある
・ Technocup 2019 - Elimination Round 1 A. In Search of an Easy Problem 500
2:00. 足して判定したけど、どうやってもよさそう。
・Codeforces Round #366 (Div. 2) A. Hulk 600
4:20+1WA こういうのにがて。WAはスペースの付け忘れでした。IQテスト感ある。
・Codeforces Round #340 (Div. 2) 617A - Elephant 700
0:55. これは基本情報ですが、n 以上の k の倍数は ( (n-1)/k+1) * k で書けます(2回目)。今回は k で割ったけど。
・Codeforces Round #143 (Div. 2) A. Team 800
3:00. 英語を読むのに時間がかかった。キューにたくさん詰まってた。おわり。
・Codeforces Beta Round #85 (Div. 2 Only) A. Petya and Strings 900
3:46.
ひとくちめも：stringは > = < で辞書式順序の比較ができるぞ！
ひとくちめも：'a'-'A'=32だぞ！
・Codeforces Round #111 (Div. 2) A. Twins 1000
8:25+1WA. 英語が難しかった(こなみ)ソートすればよい。足し方が悪くWA. あーあ。
・Codeforces Beta Round #77 (Div. 2 Only) A. Football 1100
3:25. フットボールってなんだっけ...？
・Codeforces Round #280 (Div. 2) B. Vanya and Lanterns 1200
8:15+2WA????? 1WAめは小数の誤差ミス。2WAめは差を取る範囲の取り方のミス。よくやるやつ。大反省。
・Educational Codeforces Round 61 (Rated for Div. 2) F. Clear the String 2000
【問題】英小文字からなる長さ n の文字列 s が与えられる。「sの連続する部分列で同じ文字からなるものを選び、取り除く」という操作をくりかえし、sを消すことを考える。ただし取り除いたあとの文字列はひっつけるものとする (なので [aba] -> [aa] -> [] と操作できる)。操作の最小回数を求めよ。
【制約】3sec. n <= 500
【答え】dp[l][r] で区間 [l, r) の部分列についての答えとする。遷移について、右端の r-1 番目をどう消すかだが、それまでに同じ文字が無ければ +1 回、同じ文字があればその文字と同時に消すパターンを試すとよい (長さが短いケースの和で書ける)。事前に「自分と同じ文字で左にあるindex」を計算しておき、遷移はそのindexで範囲内のものをすべて試すとよい。計算量は最悪 O(n^3) だが定数は小さく、文字がばらけているともっと早い。実際この方針で62msで通った。
【メモ】最初「左にある中で一番近いもの」だけ試していたが普通に通らず、冷静に全部試したら通った。こどふぉ特有の、意外と計算量ないパターン(？) DPの遷移が (WAは吐いたものの) 見えたのはよかった。事前にindexを持っていたが、持たなくてもできる (WAの名残で持っていたがそれはそう)。解説も同じ方針でした。
いわゆる「区間DP」というやつ。n が小さいとできる (し、n が大きくても計算量の最適化でなんとかなる場合もある)。典型ですね～
・Educational Codeforces Round 1 E. Chocolate Bar 2000
【問題】n*m のマス目がある。直線にそってうまく切って、いくつかのパーツを選んで 合計 k 個のマスを得たい。切る時には、長さの 2 乗のコストがかかる。コストの最小を求めたい。t 個のクエリに対してこの値を求めよ。
【制約】2sec. 各クエリについて、n, m<=30, k <= min(n*m, 50). t<=40910.
【解答】DPする。dp[i][j][k] を「i*j の長方形から k 個取るときのコストの最小値」とすると、各分割でどっちの長方形から何個取るかで遷移が書けて解ける。
計算量。遷移は O( (n+m) * k ) なので、全体で O(nm(n+m)k^2). でも定数は小さいので間に合う (249msでした)
【メモ】全探索でした。頭を使わずできる問題は頭を使わず解くの大事。
・Codeforces Round #352 (Div. 1) B. Robin Hood 2000
【問題】長さ n の数列 (a[i]) があり、次の操作を k 回繰り返す：
一番大きい要素を1減らし、その後に一番小さい要素を1増やす。
k 回の操作後、(項の最大値) - (項の最小値) を求めよ。
【制約】1sec. n<=5e5, 0<= k,a[i]<=1e9. a[i]>=1.
【答え】愚直シミュレーションは時間が足りないので改良する。項の最大値が a 以上になるかどうかは、max(c[i]-a, 0) の和が k 以下かどうかで判定できる。この値は要は「各項の値がaになるまで値を何回減らす必要があるか」を表している。なのでにぶたんで最大値を計算できる。最小値も同様。計算量は O(n*log(A)). A=max(a[i]).
【メモ】典型にぶたん。
cin を使ったら 998ms かかった、あぶない。scanf に変えたら 200ms くらいになった。5e5 個もcinやったらだめです。
・Educational Codeforces Round 20 C. Maximal GCD 2000
【問題】数 n, k が与えられる。長さ k の単調増加数列 a[i] であって項の総和が n のもののうち、GCD最大のものを1つ出力せよ。存在しなければ -1 を出力すること。
【制約】n, k<=1e10.
【答え】k*(k+1)/2 が n より大きかったら、そもそもないので-1.
最大公約数 g の列があるかどうかは、g*k*(k+1)/2>=n かつ g|n が必要十分。なのでそういうものの中で最大を探し、実際に構成するとよい。最後の項で調節すれば構成は容易。
【メモ】ナメとんか！と思ったら4WAした。キレそう。ナメてかかるのはやめようね！ちゃんと条件を紙に書き下すと、ミスも減るしデバッグも容易になりそう。
【どうでもいいメモ】はてなでは二重かっこで注釈になるらしい。なので体裁がぐちゃってた。気を付けようね！
