0.はじめに
前回やっと９００台にレートが上がったので好調を維持したいとおもいつつ
臨みましたが、Dにてこずり、スコアが伸びず、レートは落ち888となりました。
まぁなんとなく縁起がいいからよしとします。
1.A - Capitalized?
なんか、文字列の大文字小文字判定の関数あったよなとググり判明。
あとは、1文字目がisupperを満たし、1文字目以降がislowerを
満たす時にYesを表示、満たさなければNoを表示してAC・・・・とはいかず
Sが1文字の時は、1文字目が大文字という条件だけ満たせばOKという
条件を追加してやっとACとなりました。
https://atcoder.jp/contests/abc338/submissions/49695916
2.B - Frequency
collections.Counterを使えば何とかなるかと思いましたが
もうひとひねりが必要でした。
【考え方】
・Sをリスト化し、collections.Counterで文字ごとのカウントをする。
・most_common関数で、文字ごとのカウントの最大値pを求める
・文字ごとのカウント数が、pと一致する文字をリストansに格納する
・ans内の最小値を出力して終了
もっとスタイリッシュな書き方あるだろうなと思って解説を見たら
pythonだとほぼ1行で書けそうでした・・。
https://atcoder.jp/contests/abc338/submissions/49704191
3.C - Leftover Recipes
まず最初に、Aを最大化した場合の残りでBを作った場合と
Bを最大化した場合の残りでAを作った場合の多い方を出力
と、簡単に行けないかと思いましたが、例１で挫折しました。
まぁ、制約ゆるめなので、素直に時間がかかる方法を試しました。
【考え方】
・変数ansに0をセット
・以下をAがARセットつくれなくなるまで、ARを1ずつ増やして繰り返す
・AをARセット作った場合の材料の残りQ2を求める
・Q2を使用して最大BRセットBを作れるか求める
・ansにAR+BRとansの大きい方をセット
・最後にansを出力して終了
これで行ける！と提出したものの1個WA発生。
落ち着いて考えたところ、ARの初期値は１ではなく、0でないと
いけないことに気づきやっとAC。
ペナルティ合わせて10分ほど無駄にしました・・・。
https://atcoder.jp/contests/abc338/submissions/49723770
4.D - Island Tour
初見であきらめたくなりましたが、まぁ40分は残ってたので取り掛かりました。
グラフ問題かと思いきや、よくみるとそこまで難しく考えなくても
よさそうでした。
【考え方】
ある橋を封鎖する＝あるルートが逆回りになる
例）N=5 1-2-3-4-5-1・・・・の時
3-4を封鎖すると
→3->4のルートを3-2-1-5-4としないといけない
→ツアーの長さが+3される
ツアールートごとに封鎖された場合の長さ増分をリスト化する
増分リストの最小値+封鎖前の最小コスト＝答えとなる。
例１でいうと、封鎖前最小コストは２
・1-2-3-1の島で
・1-3 3-1封鎖で+1
・3-2 2-3封鎖で+1
・封鎖長さ増リスト 0,1,1→最小値は0
・2+0で2が答え
※封鎖長さ増リストはルート毎に足していくと間に合わないので
いもす法で作成する。
上記考えで実装するも、今一正解にたどり着かず、そうこうしている
うちに、時間がたりなくなりコンテスト終了しました。
解説を見ながらダメな点を考えたところ、いもす法で長さ増リストの
加算スタート地点を単純にルートなり（リストA内の順番）で設定していましたが
長さ増リストに反映する場合は、島番号の小さいほうにしないと
いけないことに気づきました。
あと1歩の気づきが足りなかったのが悔やまれます。
https://atcoder.jp/contests/abc338/submissions/49742964
以上