【AtCoder】ABC006を解いたのでメモ【Python3】
結果と最終提出コード
解答中の心境
【A】
これは肩慣らし。
【B】
素直に下のコードを走らせた結果...TLEとWA。
（自分で10^6を実行すると数十秒かかるレベルの速度だった...。）
# N の値によってぐるぐる回す a_3 = a_0 + a_1 + a_2 a_0 = a_1 a_1 = a_2 a_2 = a_3
速度の改善がわかないが、WAについては桁が大きくなりすぎてオーバフローしたと思い、
a_3 = (a_0 + a_1 + a_2) % 10007
に変更。すると、WAだけでなくLTEも解消！
「計算の桁を減らすコトはこれほどの速度向上になるのか！」とびっくり。（10^6の場合だと10倍近く速くなった）
【C】
"老人2人=大人1人+子供1人"に気づいたので、足の本数が奇数が偶数かで老人の人数を固定。残りはつるかめ算を使って解いた。
【D】
「ただの挿入ソートか？」と思ったが、
"10, 1, 2, 3, .., 9"
のような場合には対応できないので却下。
結局、やり方が思いつかずに断念。
解説やコメント
【A】
なし
【B】
「参考になる書き方ないかなー」と他の方々の回答を漁っていると...しのみーさんの代入方法が今後役立つと感じたのでリンクとともに紹介を
# こんな感じで一つずつ入れるのではなく... a_3 = (a_0 + a_1 + a_2) % 10007 a_0 = a_1 a_1 = a_2 a_2 = a_3 # 一気に処理してしまう！ a_0, a_1, a_2 = a_1, a_2, (a_0 + a_1 + a_2) % 10007
内部でどう処理されているか分かりませんが、人間が一時的な変数を用意することなく処理が可能でとてもスマートです！！
【C】
- つるかめ算
- 老人の数の固定
を使う方法が紹介されていた。
自分の解答は2つを組み合わせているのでこれは自画自賛OK。
【D】
下の図のように、
- 位置を変更するカードを一斉に引き抜く
- 残ったカードがソートされていれば後は差し込むだけ
- つまり、残ったカードの枚数が多い引き抜きかたを探す
というのが思いつかず、スタートに立てていなかった。
さらに、このままでは速度面に不安が残るので
- 動的計画法
- データの持ち方
に着目することで速度の向上を行えば満点解法になる。
得たもの
- 複数の変数に1行で代入してしまう発想
