早解きの練習に。
・簡単なのは時間とコメントのみ記載。
・困った / よくある議論を見た場合は問題まで出すかも。
・Codeforces Round #479 (Div. 3) A. Wrong Subtraction 500
3:30+1WA(は？). / と % を間違える典型間違いだった。やめようね。
・Codeforces Round #405 (rated, Div. 2, based on VK Cup 2017 Round 1) A. Bear and Big Brother 600
2:10. 英語を読むのがボトルネックでなのでは？
・Codeforces Round #161 (Div. 2) A. Beautiful Matrix 700
2:20. 提出のキューが詰まってるかもボトルネックっぽいな
・Codeforces Beta Round #65 (Div. 2) A. Way Too Long Words 800
5:15+1WA WAはstringの最後のindexをn-1じゃなくnにしたのが原因、典型ミスだが初心者かな？文字列の問題は長くかかる傾向にあるな、というかこういうのはpythonの方が速そう、やりませんが。
・Codeforces Round #173 (Div. 2) A. Bit++ 900
4:15. 設定を読むのがムズい。読むと解ける。
・Codeforces Beta Round #91 (Div. 2 Only) A. Lucky Division 1000
5:30. 英語の正しい意味が分からなかった (ゴミ)。「n が4と7だけの数字で割り切れるか判定せよ」という問題で、nが1000以下だったので、4と7だけの数字を自分で全部列挙しました (カス)。まあええやろ。
一応DFS (というか再帰) で列挙できるんかな？いちおうやったら実装に10分かかりました(遅) 再帰下手すぎひん？
・Codeforces Beta Round #89 (Div. 2)A. String Task 1100
8:25. 文字列は時間がかかるね()
これは基本情報ですが、'a'-'A'=32です。あとは母音の順番をググる前にコード上で引いたのはよかったとおもいました。
・Codeforces Beta Round #4 (Div. 2 Only) A. Watermelon 1200
3:15. なにこれ？一応「nを正の偶数の和で各には、nが4以上でかつ偶数なのが必要で、逆にそうなら 2, n-2 に分けたらできるので十分ですね～」という考察が必要だから1200なのかなぁ～～～
・Codeforces Beta Round #1 A. Theatre Square 1300
記念すべき1問目。
4:00+1WA まーた / と % 間違えたよこいつ... なんかごっちゃにしとるな、なにやってんだか。
地味にオーバーフロー対策が必要だった。地味に証明が非自明(aマスごとにしるしをつけよう)だが、何にも考えず通しちゃった。よくないのでは？
これは基本情報ですが、「正整数nについてn以上の最小のaの倍数」は(n-1)/a+1で書けます。なんかABCでもよく使ったような。
・Codeforces Round #277.5 (Div. 2) C. Given Length and Sum of Digits...1400
数字を文字列扱いする問題はやめろくりかえす数字を文字列扱いする問題はやめろ
16:45+2WA(吐血). 1WAめは0を1桁の数字扱いしていなかったというもの。これテストケースが見れたからよかったものの、本番だったらガチギレしてましたね... 2WAはコピペ事故。これもよくやる。
n 桁で各位の和が s の数字のうちありうる最小と最大を求める。どっちもだるいが、最大はまだまし。最小お前はゆるさん。真面目に場合分けしたけど、簡単に実装する方法あるのかな...？
・Codeforces Beta Round #2 B. The least round way 2000
【問題】n*n の行列がある。左上から右下まで、最短距離で動く。このとき、通った数の積の末尾につく 0 の個数を最小化したい。最小の個数と、それを実現する経路を出力せよ。
【制約】 2sec. n<=1e3, 各要素 a について 0<= a <= 1e9
【答え】
要素の中に 0 があるとめんどいので、いったん 0 なしの場合を考える。
末尾の 0 の個数は 2 のオーダーと 5 のオーダーの min である。そこでまず各要素について 2, 5 のオーダーを計算しておく。そして経路についての 2 のオーダーの最小個数と 5 のオーダーの最小個数をDPで計算して、そのminが答えとなる (じつは少し非自明だけど、冷静になると簡単に証明できる)。経路については、DPからの経路復元の典型でできる。
0 がある場合は、0 を通ると答えが 1 確定になる。そこで 0 を通らないケースと比較して小さい方を投げるとよい。
【メモ】
典型議論でできた。しかし、実装はデバッグを含め1時間近くかかってしまった(デバッグで半分以上かかってるけど...)。このへんぱっぱと書きたいなぁ。
なお、cin/coutを使うと1777msもかかったが、printf, scanfに変えると295msまで減った。cinが遅くて、1e6個もやるとだめなんでしょうね。気を付けよう。
・Codeforces Alpha Round #20 (Codeforces format) C. Dijkstra? 2100
【問題】重みつき無向グラフがある。頂点数はn で 1 から n まで名前がついている。1 から n までの最短経路を求め、通る頂点を順に出力せよ。
【制約】 n, m<=1e5. 1<=(各重み)<=1e6. 多重辺や自己ループもあり。
【解答】ネタバレの通り Dijkstra して、経路復元すればよい。経路復元はDFSでできる。
【メモ】典型だった。Dijkstraはライブラリ化していたのですぐだった。
