0.はじめに
停滞が続いている今日この頃望んだAtcoder。
C問題にてこずりつつなんとか解いてDにうつったら
Dの方がカンタンだったパターン。
とはいえ、久々にA~Dまでとけ、レートも+39と久々にアップしました。
1.A - Cyclic
入力を文字列として受け取り問題に合わせてスライスしてくっつけて表示。
https://atcoder.jp/contests/abc379/submissions/59568414
2.B - Strawberries
最初は今一イチゴを食べると歯がなくなるというシチュエーションが
しっくりこず、戸惑いましたが、まぁいつもの事なので・・・。
まず、回答用変数ansとOの連続数カウント用変数oを0で初期化。
文字列を先頭から見ていき、以下を繰り返し
・"O"なら、oに1加算、それ以外ならoに0をセット
・oがKに達したらansに１を加算してoに0をセット
最後にansを出力して終了
https://atcoder.jp/contests/abc379/submissions/59573922
3.C - Sowing Stones
最初は制約大きいなと思いつつ、ささっと10分くらいで回答提出
あまり見ないメモリエラーにTLEとさんざんな結果で、Cにしては
色々と工夫しないといけない気配。
【最初の考え】
・マスに1個ずつセットするという前提からすると
単純に1つ目のマスからマスに1個残して他を次のマスに
移動していくことですべてのマスを1にでき、最小移動回数となる。
1.リストPを値0×(N+1)で初期化、ansを0で初期化
2.リストA、Bを読み石の初期配置を、Pにセット
3.１～Nまで、iを回し以下処理
-1.P[i]が0なら-1を出力して終了
-2.P[i]が1以上なら以下処理
-1.P[i]-1をP[i+1]セット
-2.ansにP[i]-1を加算
4.最後にP[N]が1ならansを、それ以外なら-1出力して終了
Nが大きいと、2)でメモリーエラーとなってしまいました。
他にもREとなってましたが、まぁどちらにしてもダメなので試行錯誤。
特に、リストPを用意しないでも、次に繰り越す石を保持する方法で考えましたが
それでも、上記3）のような繰り返しをするとTLEになることが分かりました。
【最終的な考え】
＜石の配置が条件を満たすかの確認＞
・初期の石配置で1マス目に石が入っていないと満たさない
・初期位置に石が入っているマスを順にみていき、前のマスから
次のマスまでのマス数が前のマスに入っている石数より小さければ条件を満たさない。
・上記を満たしたうえで、初期配置の石数がマス数と一致すれば条件を満たす
＜石の移動数計算＞
・前のマスに入っている石数をＰ、前のマスから次のマスまでのマス数をｎとしたばあい
（Ｐ＊ｎ）-（ｎ×（ｎ+1）/2）
（前のマスから次のマスまですべての石を動かす場合の数から
1個ずつ動かす数が減る場合の減る数をマイナスする）
さらに、最後に石が入ったマスがＮマス目の場合と、そうでない場合を分けて
計算したりと、いろいろてこずりつつ、最後はＡＣとなりました。
https://atcoder.jp/contests/abc379/submissions/59612244
4.D - Home Garden
ちらっとみて時間かかりそうなので、Ｃより先にやることは避けましたが
実際やってみたら13分で終わったので、先にやっとけばもう少し順位上がったかなと
思わなくもなかったです。
【実装】
1.Qをインプット
2.デキューをインポートし、変数qをデキューで定義
qには、種を植えた日付を格納
3.変数Dを0で初期化
Dは経過日数をセット
4.以下Qの数だけ繰り返し
-1.リストAをインプット
-2.A[0]が1の場合qにDを追加
-3.A[0]が2の場合DにA[1]を加算
-4.A[0]が3の場合
-1.CにA[1]をセット、flgに1をセット、ansに0をセット
-2.以下flg＝１＆ｑに値が入っている間繰り返し
-1.Ｐにｑの左値を取り出し（一番昔に種を植えた日）
-2.D-PがC以上の時（種を植えてから規定日数経過していた場合）ansに1加算
-3.D-PがCより小さい時（種を植えてから規定日数経過していない場合）qの左側にPを追加
-4.flgを0に変更
-3.ansを出力
デキューのおかげですっきり解けました。
https://atcoder.jp/contests/abc379/submissions/59618515
以上