AGC 028 反省
Aのみの1完. 早ときかどうか微妙なタイムでしたが青パフォがとれ, 無事水色になることができました. Bもちょっと考えたんですけど, わからずじまい....とりあえず水色になった喜びも込めて, Aのみ書きます.
A問題
解法
条件から, が
であること必要となります(
は整数).
まず, 答えの最小値であるで
,
が構成できるかを調べます. 具体的には, map
の
番目の文字を
について埋め,
で答え合わせします.
構成できなかったときは-1を出力し, 構成できたときはが答えとなることがわかります.
では, で答えとなるものを構成できなかったとき, ある
が存在して, 条件を満たす
が存在するのかどうかを考えます.
結論を言うと, 答えを構成できなかったときはこのは存在せず, -1を出力するのが答えです.
なぜなら, 答えとなるものが構成できないということはにおいて,
と
が参照するものが衝突(食い違っている)している, ということになります. この衝突が起こる文字の位置は,
を何倍しても変わりません(添字の計算式に代入してみるとわかります).
等号が成り立っている両辺に同じ数をかけても等号が成り立つのと同じです.
感想
やれることを探すと, 発想は自然に出てきます. しかし, この解法が成り立つのかどうかを考えるのに時間がかかりました. 開始15分ほどのsubmissionでしたが, 水へのパフォは十分で, なかなかAGC-Aにしては解きづらい(というより読みづらいでしょうか)問題だったような気がします.
総評
とりあえず水色やったああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
というのが第一です. Twitterでもいろいろな人に祝ってもらえてうれしかったです！
競プロのコンテストにではじめて4ヶ月, あのときはC問題もおぼつかない状態でしたが(これは罠で今もおぼつかない), なんとか水色になれました. 真っ直ぐな道ではなく, なかなかレートが伸びない時期もありましたが,
伸び悩んでいた時期に読み漁った先方erの『水色になるまでにやったこと』記事がなかなか助けになったため, ぼくも暇があれば執筆したいです. というかそれを書きたいのが精進のモチベになっていた気さえします().
次からARCじゃないとレートがつかないのかーとか思うとなかなかプレッシャーですね...
ひとまずは緑に落ちないようにがんばりたいと思います.
埃被った蟻本を再び開くときがきたようだな...って感じです.
