お疲れ様でした〜
ABCD4完 30min(Aで1WA？？)でした。パフォ4桁出たので嬉しいですね。
A-Leap Year
問題要約
閏年を判定しなさい。
方針
そのままやるだけです。例えば2つ目の条件である4の倍数で〜の部分は、4の倍数でない年を先に判定していればY%4==0などは記述する必要がないです。よってO(1)でこの問題を解くことができました。言うまでもなく、十分高速です。
着想
特になし。
B-Second Best
問題要約
そのまんま。
方針
2番目に大きい値を取得して、探索してあげればOKです。よってソートがボトルネックなので、O(NlogN)でこの問題を解くことができました。Nがとても小さいので十分高速です。
着想
特になし。
C-Transportation Expenses
問題要約
数列A={a1,a2…an}があり、∑min(ai,x)≦Mを達成できるような最大のxを求めよ。
方針
二分探索を使います。xにおいて、達成可能な値(初期値はたとえば0)と達成不可能な値(初期値はたとえばM+1)を設定して、狭めていけばOKてす。よってO(NlogN)でこの問題を解くことができました。NlogN≦およそ3.5×10^6なので十分高速です。
着想
スコアxを達成可能かどうかをO(N)で判定できる場合は、二分探索！
D-AtCoder Janken 3
問題要約
PRSいずれかの文字のみで構成された文字列Sが与えられるので、以下のルールに沿った文字列Tにおいて、スコアを最大化せよ。
ルール
•連続で同じ文字は存在しない
•Siに対応して、Tiで使えない文字がある
スコア
•Siに対応して、Tiが特定の文字のときスコアを+1
方針
DP！dp[i][i回目に出した手]=スコアにすればOK。
ぱっと思いつくのは貪欲法、つまり勝てるときに勝っておく戦略が思いつきますが、2つの制約により、最適化戦略ではありません。
着想
状態が有限で、状態遷移およびそれにともなうスコアの変化が明確な場合はDPが有効です。
余談
Dの割にはかなり簡単……？
