AtCoder初歩的な書き方、考え方（〜茶色になるまで）

Python プログラミング 数学

AtCoder入門者です。 AtCoder Problemsを解いていて便利だなと思った表現方法やアプローチをまとめています。（Pythonです）

色変する頃には気をつけるポイントも変わっていると思うので記事分けます。

基本全ての処理にどの問題でその操作を使用したか書いているので、同じく入門者の方は問題を解くときに参照していただければ。

アルゴリズムの勉強はこちらです。

aoki-shiraki21.hatenablog.com

Input/Output

  • 事前処理

使いたい情報は先に辞書を作っておくと楽。（ABC173/B）

  • 入力、出力処理の基本 複数の値を一気に受け取って下処理するときはmapで対応させると楽。（ABC173/C）
h, w, k = map(int, input().split())

出力するときにjoinなどの操作をしたいときはstringに変換しておく。

print(" ".join(map(str,num_list)))

基本演算

  • 四則演算系

累乗は^じゃなくて**だから注意。（ABC172/A）
また、**は優先順位が強いため、累乗根の計算をするときは**(1/2)のようにカッコをつけておく。

  • マイナスへの整数除算

あまりが正の数になるように考える。ので、-5//2は-2ではなく-3になる。（ABC173/D）

-5 // 2  #=> -3
  • ある桁までの数字の抽出

10で割ったあまりが1桁目、100で割ったあまりが1~2桁目みたいな操作ができる。str型にしてスライスとかでもいいけど。（ABC168/A）

  • 変数定義

あとで元の変数を使用する可能性がある場合は、変数名を変える。（ABC168/C）
基本的に初期値として与えられるものはそのまま保持しておいた方が良いことが多いので、加工するときに別の変数名を与える。

  • n列目までの総和

単純に毎回sumをやるとO(n2)になり時間がかかりすぎる。階差数列として捉えればO(n)でいける。（ABC172/C）

A = [1,2,3,4,5]

a = [0]
for i in range(len(A)):
    a.append(sum(A[:i+1]))
print(a)

b = [0]
for i in range(len(A)):
    b.append(b[i]+A[i])
print(b)
  • 誤差

少数の計算は誤差を生むので、計算したい桁に修正して、後から戻す。（ABC169/C）

x = int(x)
y = int(y.replace(".","")) # 少数第二位まで与えられる想定。 0.01 => 1
print(x*y//100) # 計算した後に100でわることで元の少数第二位の計算に戻す
  • stringで表現された式の評価

evalを使用すればstring型で書かれた式を計算してくれる。（ARC61/C）

https://qiita.com/kyoshidajp/items/57ae371b3f5d8a84fb13

基本関数、メソッド

  • リストへの要素の追加

メソッドを使用するときに、処理と返り値に注意。insertは返り値はNoneになる。trial_num.insert(1,i)

繰り返し処理

  • 適切な深さで処理をすることで無駄に繰り返さない

繰り返しを行うときは、それがforの何番目で行う必要があるのかを確認する。一番奥で処理をすると、forのたびに毎度処理を行うことになる。（ABC162/C）

  • 奇数/偶数判定など定数倍にはステップ幅を使う

forの後にif n%2==0などで書くと遅いので、ステップでrange(0,n,2)のようにそもそも繰り返しを減らす。ifもなくなってスッキリする。

平方根とったのに、その後を繰り返したら計算量があまり変わらない。どこまでを繰り返す必要があるのかを確認する。（ABC144/C）

配列の操作

  • 配列の簡単な操作

for,if文で書くと長くなるので、メソッドで処理する。maxやmin、'sum'が使えないか検討する。（ABC172/C, ABC95/C）

# aがbより大きければ差を、それ以外は0をみたいなパターン
if a>b:
   n = a-b
else:
    n = 0

# 差と0との最大値をとれば良い
n = max(a-b,0)

list.count(要素)を活用してコンパクトにかく。==0で有無の判定も可能。(ABC170/C)

ある要素の場所を特定するにはlist.index(要素)を使う。（ABC170/A）

  • 要素の有無判定

a in listの形で探索すると毎回丁寧に全部を見にくので低速。要素の重複なく保持したい、有無判定を高速にしたいみたいなケースはset型が便利。（ABC164/C）

【Python】set型の基本と、死ぬほど遅い「hoge in list」からの脱却 | ゆとって生きたい。

Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由 - Qiita

5. データ構造 — Python 3.8.5 ドキュメント

  • 列ごとに分割する表記

*を使うと、配列のその他の部分を表現できて便利（ABC167/C）

c, *a = book[j]
  • 転置行列の作成

*で展開したリストをzipでまとめて処理する。行列を扱う時に、行ごとの方が繰り返しの操作がしやすいので。

l_2 = [list(x) for x in zip(*l)]
  • 配列の要素の判定

要素全てにチェックをしたいとき（よくある）、allを使って内包表記のように表すと簡単（ABC167/C）

all(lj >= x for lj in l)
  • あるインデックス以下に共通の足し算

一番上のインデックスに処理をメモっておいて、最後に累積和をとると楽。結局全部足せば良いので（ABC138/D）

  • n乗のfor文の形。

①行列の中の処理する,しない（yes,no）をそれぞれブール値の0,1と対応させる。 （ABC173/C） n行であれば、range(1 << n)
そうしておけば、あとは調査したいだけ右シフトして、1かどうかによって処理を決める。

②再帰関数を用いて、n-1コの状態とnコ目に分割する。

[row][three:two+three]

  • ある値からの等距離の判定

-1,+1を両方の要素に試してみる操作が絶対値を求めるときなどに相当する。for s in [-1, +1]:（ABC170/C）

  • 逆順配列の設計

これはもう定型表現のように覚える。

l = s.copy()
l.reverse()

s[::-1]

辞書型

  • バリューが最大（最小）のキーを得たい時は結構ある。その場合はキーを指定して、getでバリューを取得してあげる。
max(dic) # 最大のキー
max(dic.values()) # 最大のバリュー
max(dic, key = dic.get) # バリュー最大のキー

Pythonで辞書の値の最大値・最小値とそのキーを取得 | note.nkmk.me

整数の処理

漸化式

  • 漸化式を求めることで入力も処理も見通しが良くなる（ABC174/C）

倍数、あまり、割り算

  • ある数kで割った時のあまりは0~k-1の範囲。k回の処理で割り切れない場合は割り切れないことを疑う（ABC174/C）

  • 誤差を避けるために整数化して比較する場合、処理が逆に辿れるのかを確認する。つまりA2 < B2だから必ずA < Bとは言えない。Bが負の場合があるため。B>0の条件があれば逆に辿れる。

  • mod10は要は1桁目を取り出す操作。（ABC161/D）

  • 半分にした数字をあつかいたい、偶数の時はそのまま半分、奇数の時はあまり分も入れて、みたいな操作をしたい時がある。（あまりなしなら//で問題なし）。その場合一旦普通に/2をして少数を繰り上げておくと偶奇どちらでも思っている処理になる。

math.ceil(a / 2)

累積和

  • 便利な性質として、1+2+3+..t =x ならば1~tの部分和によって0~xのどの整数でも作れるというものがある。大小判定系で活用できる。（ABC056/C）

よく使うモジュール、ライブラリ

itertools

イテレータの操作に使う（そのまま）

  • itertools.combinations_with_replacement(p, r)

p配列からr個の重複組み合わせを全列挙する。

  • itertools.product(list, repeat=N)

1つのイテラブルから直積を生成する。要は重複順列を作る時に使える。

itertools --- 効率的なループ実行のためのイテレータ生成関数 — Python 3.8.5 ドキュメント

bisect

  • bisect.bisect(l,a)

ソートされたlに対してaが何番目に入るかを高速で検出する。リストの中である範囲の数を知りたい時に便利。

図形

  • 三角形の成立条件は以下が直感的にわかりやすく書きやすい。
a+b>c and b+c>a and a+c>b

その他考え方、アプローチ

  • ややこしくなりそうなら先に擬似コード、docstringで流れを書く。結果その方が早い。

  • 本当に毎回全可能性を探るのではなく、結果を格納する配列を作っておいて、そこに結果を更新していくみたいなアプローチが有効な場合がある。明らかに全探索な問題以外でO(n2)以上になったら疑う（ABC166/C, ABC166/B）

  • 点ではなく点によって区切られる線で考えると？最小値を求めたい時に補集合の最大値を考えると？みたいな視点を切り替えると求めるべきことがシンプルだったりする（ABC160/C）

  • 105（10万）通りくらいなら全列挙しても時間的に問題ない。（ABC95/C）

  • 解答パターンが結局そんなに大きなければ、解答を仮に設定しちゃって条件と矛盾がないかを確認する決め打ちの方が計算量が少なく済む。（三井住友信託銀行プロコン2019/D）

  • ちょっとややこしくなってきたら紙に書いて周期性を確認する。（ABC133/C）

  • sumなどのリストを全部確認するのは毎回O(n)かかるので、前後での変化感を知るだけで良い可能性はないかを検討する（ABC171/D）

  • 倍数や約数系の問題は、先に答えのリストを有効な制約分設けておいて、そこに条件に当てはまるものだけをTrueで残していくような操作がシンプル（ABC170/D）

  • 順番のパスを考える時は、あるn番目のパスに至る方法がどう表されるかを考えると漸化式として一般化できる。だいたいn=1とかの時は求められるので、組み合わせで一般解を出せると。ポイントは「ある地点からどこに行けるか」ではなく「ある地点に到着する方法はどう説明できるか」（ABC129/C）

  • lognはほぼ無視できる。O(n)とO(nlogn)は105程度であれば定数倍くらいで考えておけば問題ない（ABC126/C）

  • 与えられた条件で全探索が難しい時に、本当にその条件なのか、別の条件を組み合わせると範囲を絞り込むことができないかを検討する。複数の全探索が走る場合は、大概最後の探索が他の探索の結果によって規定されるので1回分ループを少なくできる。(ABC166/D, ABC165/D)

  • 累積の計算、かつ条件がある場合に、条件を無視して累積の計算設計をしておいて、その中に条件分岐を入れる方が楽な場合がある。（ABC163/D）

  • 答えの桁が大きくなる時は、途中で小さくできる処理があるなら噛ませた方が良い。あまりを提出する時は特に。（ABC006/B）

  • 「ランダムに選んだ操作を繰り返す時の対象物の最終的な地点」→水を入れたり戻したりする操作としてイメージする（AGC002/B）

  • 難しい状況から簡単な状況に分解していくよりも、最初から作っていく方が簡単（ABC120/D）