ゴリラからの逃走

意識が高いだけで何もできなかった頃(=ゴリラ)から変わるために日々行なっていることを書いています。

AtCoder初歩的な書き方、考え方(〜水色になるまで)

感想とか過去問記録とかは特になく、覚えたことと勉強方法の記録です。

茶、緑になるまではこちらから。

aoki-shiraki21.hatenablog.com

aoki-shiraki21.hatenablog.com

入力

  • 複数行入力は下にコピペしていくのではなく、リストとしてもらってアンパックが楽。
 a,b,c,x = [i_input() for i in range(4)]
  • 使わない情報がはっきりしている場合は、入力の段階で消しておけると実装上シンプルになる。
# 文字列を斜めに抽出する
c = [input()[i] for i in range(3)]

配列

  • チェックしたい値の管理は、値自体を配列に入れるのではなく、値がインデクスとなる位置にフラグをつけて管理した方が見通しがよくなる場合がある。

配列に値が入っていると、a in list やbisect(list, a)を使って検索をかけることになる。これを毎回やるのは遅いし、特に二分探索は左右どちらを入れる入れないみたいなミスの元(それも正確に書けるようにならないといけないのも事実だが)。
例えばT/Fを活用してlist[a]のような形で値が入っているかをチェックする方が楽だったりする。

条件分岐

  • すぐに全探索+ifの条件分岐に逃げない。遅い(実装的にも計算時間的にも)し、階層が深くなってミスの元。与えられた条件で最初から限定できないかを考える。(ABC107/C)

    • k個選ぶなら、k個の範囲内でループを回せないか
    • 行列の周囲にダミーの値を入れておくことでコーナーケースを防げないか

匂わせワードとアプローチ

  • 「操作」:操作をした後の結果を日本語で表現してみると、それが最適解であることが多い
  • 「最大何回」:貪欲なパターンを作っておいてそれを回数制限まで行うと最適化されることが多い

  • まずは可能性の全探索を試みる、計算量を落とす必要がある場合に時点の方針を考える

  • 3,400点の問題でコードがゴチャつきそうになったらその時点でアプローチが間違っているんじゃないかと考え直す

計算処理

  • 各桁の値の和は文字列として受け取ったものをmapで展開して総和がかんたん。
n = input()
S = sum(map(int , n))

学習方法

  • パッと思いついたアプローチで愚直に書こうとして簡単な問題の実装に時間がかかる傾向にあるので、過去問を解く時に強制的にアプローチを考える時間をとる練習方法を採用してみよう。