0.はじめに
昨日はレートを落としたので挽回できるといいなと参戦。
A・Bが順調に解けたので、気持ちよく週末を終えられました。
気になるレート変動は・・・
+68と大幅アップで803に。
ついに緑コーダーとなりました。来週には落ちてそうだけど・・・。
1.A - Divide String
問題を一読して、2個以上と言ってるが、3個以上に分割する意味はないな。
と気づき、以下のいずれかを満たす文字列が作れるかどうかで判定可能と判断。
条件1)
先頭の文字より、辞書順で大きいアルファベットが使われているか?
→使われていれば、その前で区切れば、辞書順昇順を満たす文字列が2つ作れる。
条件2)
先頭の文字と同じアルファベットが使われている場合、先頭からその文字の直前までの
文字列①と、その文字以降の文字列②を比較し、①の方が、辞書順で小さいか?
→小さければ、その前で区切れば、辞書順昇順を満たす文字列が2つ作れる。
文字列を、先頭から見ていき、条件1・2いずれかを満たす文字があればYes
なければNoを出力して終了としました。
考慮漏れの条件等無いか心配でしたが、特に無く、AC頂けました。
https://atcoder.jp/contests/arc163/submissions/43186855
2.B - Favorite Game
問題を一読して、A[0]とA[1]を操作してよいなら、この二つを操作する一択だなと思いました。
問題文では、Aの一つ目の要素はA1としてますが以下では、0始まりインデックス表記にします。
考え方
・リストAのA[2]~A[N-1]から、M個を選んだ時、その数字達をA[0]とA[1]の間に挟むために
A[0]からマイナス1とA[1]へプラス1をそれぞれ何回すればいいかを求める。
実装
【変数】
・変数S :頻繁に使うためA[0]をセットして保持
・変数L :頻繁に使うためA[1]をセットして保持
・リストL2 :リストAから、A[2]~A[N-1]をセットし、昇順ソートしたリスト
・リストL3 :L3[0]には、L2[0]~L2[M-1]が、S~Lの間に収まるための
操作数をセットする(このリストを埋めるのがメインロジック)
【ロジック】
1)変数S・L・リストL2に上記説明に従い値をセット
2)以下を0~N-M-2まで繰り返し(インデックス変数i)
(L2リストを読み、iからM個抽出した場合のSとLの操作数を求める)
2-1)L2iをSと比較
2-1-1)L2[i]がS以上の時、SS(Sを操作する回数の変数)に0をセット
(操作する必要が無いため)
2-1-2)L2[i]がSより小さい時、SSにS-L2[i]をセット
2-2)L2i+M-1をLと比較
2-1-1)L2[i+M-1]がL以下の時、LL(Lを操作する回数の変数)に0をセット
(操作する必要が無いため)
2-1-2)L2[i+M-1]がLより大きい時、LLにL2[i+M-1]-Lをセット
2-3)L3にSS+LLを追加
3)min(L3)を出力して終了
思いのほかすっきりと実装できました。
https://atcoder.jp/contests/arc163/submissions/43192931
以上