感想とか過去問記録とかは特になく、覚えたことと勉強方法の記録です。
茶色になるまではこちら。
出力
- リストを1行ずつにして出力するには、展開して改行のセパレートをかける。空白文字なども同様。intかstrかの違いを気にせず使える（joinだと一回str()を噛ませる必要があった）ので便利。
print(*list, sep="\n") print(*list, sep=" ")
- 「何らかの処理をした結果で並べ替えたいけど、出力するのは元の配列」みたいなパターンは関数を作っておいてlamdaで処理を渡してあげると楽。
def f(s):
t = ""
for i,c in enumerate(s):
k = B.index(c)
t = t+str(k)
return int(t)
for ans in sorted(A, key = lambda x:f(x)):
print(ans)
配列
配列の要素の大小比較を繰り返し行う場合は、一度ソートして二分探索、結果を累積しておくのが定石。（ABC077/C）
繰り返し処理をする時に、先頭・末尾に0やINFを入れる、インデックスの数字を合わせるなど処理をしやすく調整しておく。条件分岐でかくのはミスの元。
for i,k in enumerate(t[1:], start=1):
- 小ワザ。文字の配列の入力がめんどくさい（"とか,とか）時にざっとスペースで文字を作ってsplitしてあげる方法。
dore = list("Do Re Mi Fa So La Si".split())
整数
- a,mが互いに素の時に「abがmで割り切れるなら、bがmで割り切れる」の性質があることを理解しておく（ABC108/C）
累積
- ある要素を除いた場合を考える場合は、先に全体を計算しておいて除くものを1つ決める考え方が定石。
mod
modの世界で計算をする時は指数計算に
powを使用する。あまり結果をさらに処理する時はカッコをつける場所に注意する。
(3*2)//2 # => 3 (3//2)*2 # => 2
匂わせワードと定石
「上下左右」→4つに分解して処理し、最後に足し合わせる
「要素を除いた場合」→先に全体を求める
「最適化」→損しないなら採択、損するなら削除する、のように考えて調べる範囲を限定していく
「制約が段階的」→制約が厳しい方から先に処理して、後から残った簡単なものを条件に合わせる。
「最大最小」→値を仮置きすることで判定問題（yes/noで答えられる問い）に持ち込めないか考える
「経由点」→真ん中の要素に注目する。始点から経由点、経由点から終点と2つに分けると見通しが良くなる事がままある。
探索
- dfsにおいて、全訪問経路をチェックしたい時は、一度訪問した時にスタンプを押して、それをdfs後にキャンセルさせれば良い。
for i in range(N):
if l[n][i] == 1 and v[i] == 0:
v[i] = 1
dfs(i)
v[i] = 0
- 探索において全部の地点を行ったかどうかのチェックは、元の配列自体をスタンプとして使用すると実装もメモリ的にも楽。同じ処理を何回も行う場合は、deepcopyをかけておく
def dfs(y, x): # B自体が探索すべき配列であり、スタンプがわりでもある
B[y][x] = "x"
for a,b in t:
if 0 <= y+a < 10 and 0 <= x+b < 10 and B[y+a][x+b] == "o":
dfs(y+a, x+b)
座標、数列
- 順位だけが問題の時は座標圧縮を行うと何かと便利なことがある。実装は簡単で、ソートしたセットを使って、何番目かを記憶しておく。
A = [i_input() for i in range(N)]
d = {}
for i,num in enumerate(sorted(list(set(A)))):
d[num] = i
for i in A:
print(d[i])
判定
- この処理は「判定をしたい」のか、「値の操作をしたい」のかを明確に分ける。判定をしたつもりが配列のデータが変わっていたり、操作していることを忘れて次の判定に入る、みたいなのがABCのA〜Cレベルまでのミス原因としては多い。
学習方法
難しい問題はだいたいどなたかが解説ブログを書いてくれているので、それで考えるプロセスをトレースする。
難度自体がヒントになったり、難度を見て尻込みしちゃうと学習が深まらないので、Difficulty表示機能をオフにする。
基本的には過去問を進める（他の方見る限り過去問解く量とパフォーマンスは基本比例する）。が、もともとアルゴリズムや数学の強いバックグラウンドがあるわけではないので、1日1コマは使ったアルゴリズムの整理をする時間をとる。
A,B問題も順番にとく。パフォーマンスが回答スピードに左右されるからというのはもちろん、アルゴリズムを活用する問題でも基本的なライブラリの使い方などでつまると思考が遅くなるので。
わからなかった問題は、納得できるまで安易に次の問題に行かない方が個人的には合っている。曖昧な理解のまま問題数だけたくさんやってもあんまり咀嚼できていない。
