ABC335回答メモ

Posted at 2024-01-06

0.はじめに

新年一発目のABC。去年から引き続き緑を維持したいなと思いつつ挑戦。
年末年始にいろいろあり、あまりトレーニングもできませんでしたが
A~Dを解くことができたので、まぁ自分的には及第点でした。

　しょっぱなのお題として肩慣らし的な問題。
　インプットをリストにすると、いろいろ面倒だったので
　リストに格納して、最後の文字を３から４に上書きし
　リストを結合して出力して終了としました。

　Bもまだ、正月気分な問題。
　回答例をみると、もう答えが出せそうな感じでした。
　制約もゆるいので、単純に3重ループで条件を満たす
　値を表示して終了しました。

　3問目から、急に難易度が上がりました。
　制約的にもTLEを意識しないといけなそうな感じ。

　【考え方】
　　・竜の頭がどこにあるかのリストを作る
　　・2の出力指示の時は、
　　例えば、2番めの胴体の場合は頭が2個前に
　あった場所を出力する。

　と、したところなんとかなりました。
　前準備として、実際は頭は通っていませんが
　胴体の初期位置も頭が通ったように
　セットしておくところがコツと言えばコツかなと思いました。

　Cより簡単かも。と思える問題でした。
　点数も350と、若干Cよりでした。
　条件を満たすためにはいろいろな
　方法はありますが、奇数固定で真ん中はTと決まっているので
　外から内にとぐろを巻くように数字を配置していく方法を取りました。

　【考え方】
　　・右下左上に進むための増減値をリストに保持
　　・左上からスタートし、枠外に出るか、進路が数字で
　　　埋まっていたら方向転換
　　・真ん中についたら終了

　最大Ｎ＝４５なので、あまり時間を気にせず作れました。

　dfsでなんとか解けるかと提出してみましたがWAが出る始末。
　dp等もう少し考えないといけなさそうなので、解説を見ながら
　解いて置こうと思います。

以上