AtCoder Beginner Contest 135の思考ログ

この記事の目的

90%自分用に、AtCoder Beginner Contest 135に挑んだ思考ログを書いています。

まだまだ初級者ですが、ゆくゆくは中級者になって初級者コーダーの参考になればよいなと思っています。

参考リンク

問題
https://atcoder.jp/contests/abc135

解説動画
https://youtu.be/brfeRxmzuKw

A問題

KはA,Bどちらか小さい数字より小さい値になることはない。
つまりより小さい数＋1から大きい数字までのループで解ける。
...がこれ普通にTLEになるんでは？　と考えて条件を探したが上手く行かず、時間無いので上記の条件だけで書いて提出したらやっぱりTLE。

どうしても悩んでしまい答えが出ないので次の問題へ。C問題まで解いて戻ってきても、時間内に考えがまとまらず時間切れ。

A問題解説動画視聴後

|A-K| = |K-A| であり、|B-K| = |K-B| なので、|K-A| = |B-K| になるK、即ちAとBの中間地点を求めれば良い事が分かりました...

うーん、頭固い。切り替え、次。

B問題

・1箇所を除いて昇順であること
・1箇所は互いに入れ替える事で昇順になること

普通にセレクトソートして、2回以上操作したらNOにを返す、としたらいけるのでは？　と考えてAC。

つい最近セレクトソートの存在知ったばかりの所にこれを使えて嬉しい。

VisuAlgo - アニメーションを介してデータ構造とアルゴリズムを可視化する (Japanese)

空白区切りの数字を配列にする構文思い出せずに時間食ってしまったのは反省。

P = [int(i) for i in input().split()]

B問題解説動画視聴後

解けたのでいいにしても、一文まるっと読み飛ばしていました...

・pは{1,2, ..., N}を並び替えた数列である。

この条件であればソートすら必要なく、p[i] の位置に i がいるかどうか？ で順列かどうか判定できます。

問題文熟読して、適切な解法を選べるようにしたい。

C問題

0番目の街に対処できるのは0番目の勇者だけと考えれば、単純に左から自分の街を処理→余力があれば隣の街に応援...を繰り返すだけでは？

C問題解説動画視聴後

貪欲法という言葉を始めて知りましたが、解説でも同じソースでした。

そのアルゴリズム、貪欲につき——貪欲法のススメ (1/3)

アルゴリズムのパターンとしてどこかで見たことがあったかもしれません。

D問題以降

AtCoder Beginner Contest 135ではD問題以降は考えられませんでした。

D問題の解説は見たのですが、十分に理解できていない所があるので記事化はしません。興味がある方は冒頭のリンクから動画を参照してください。