Pythonで解く蟻本（2-1: すべての基本 "全探索"）
※自分の勉強の備忘録として書くので、ちゃんとした説明はない記事です。
記事の構成としては、ざっくりとこんな感じです。
- 蟻本の答案をPython3に変換したもの
- AtCoderの例題のPython3解答
蟻本と似たような問題は、Qiitaの記事（AtCoder 版！蟻本 (初級編) - Qiita）を参考に探しました。
AtCoderの解答解説を読んでもコーディングで躓く、他の人のACコードを見ても何が起きてるか分からない、という方の助けになれば幸いです。
この記事では、ほとんど深さ優先探索と幅優先探索の話しか出てこないです。
なお、持っている蟻本は以下の第2版です。
リンク
部分和問題（蟻本 P.34）
これは、記載されている解答をそのまま Python で書けばいいので簡単ですね。
def dfs(i: int, s: int): if i == n: return s == k if dfs(i + 1, s): return True if dfs(i + 1, s + a[i]): return True return False n = int(input()) a = list(map(int, input().split())) k = int(input()) if dfs(0, 0): print("Yes") else: print("No")
ABC 045 C - たくさんの数式
これは上記の蟻本の問題と同じパターンです。ただし、コーディングに少し工夫が必要でした。
pythonの文字列操作で解決できることに気付いたら早そうです。
s = input() n = len(s) def dfs(i: int, t: str): if i == n-1: #i = n - 1に到達したら終了 # + で区切った数字をint型に変換して足し算 return sum(list(map(int, t.split('+')))) # 文字列で次の数字をそのまま連結するパターンと、+で区切るパターン return dfs(i+1, t+s[i+1]) + dfs(i+1, t + '+' + s[i+1]) # 初期値でsの一文字目を入れておく print(dfs(0, s[0]))
ABC 079 C - Train Ticket
ちょっと汚いですが、こんな感じになりました。
正直、dfsについてarrayを引数としなくても良かった気がしています。
def dfs(array: list, index: int, calc: str, result: int): if index == len(array): if result == 7: print("{}=7".format(calc)) exit(0) if index == 0: dfs(array, index + 1, array[index], int(array[index])) elif index < len(array): dfs(array, index + 1, calc + "-" + array[index], result - int(array[index])) dfs(array, index + 1, calc + "+" + array[index], result + int(array[index])) array = list(input()) dfs(array, 0, "", 0)
上記のコードでは exit で処理を完了していますが、この代わりに return を使うとprintしすぎてダメになります。
exitとreturnの違いは、以下になります。
- exitは呼び出された時点で全ての処理を即終了
- returnは呼び出されている関数の処理を終了
要は、return print(~) としてしまうと、正解パターンを全部吐き出してしまうのでWAとなるわけです。
この記事が分かりやすかったので気になる人はどうぞ。
» exitとreturnの終了処理は何が違うのか?技術ブログ
ちなみに、return を使って実装した場合の一例はこちらになります。
ちょっと複雑になりますね。
def dfs(array: list, index: int, calc: str, result: int): if index == len(array): if result == 7: return "{}=7".format(calc) else: return "" if index == 0: return dfs(array, index + 1, array[index], int(array[index])) elif index < len(array): return dfs(array, index + 1, calc + "-" + array[index], result - int(array[index])) + dfs(array, index + 1, calc + "+" + array[index], result + int(array[index])) array = list(input()) S = dfs(array, 0, "", 0) print(S[:9])
ABC 104 C - All Green
これは解答を読んでしまいました。
AtCoderの解説を読むと、以下の2点を前提とするようです。
- 中途半端に解く配点は 1 種類以下であり、それ以外の配点は完全に解くかまったく解かない。
- 中途半端に解く配点があるなら、それは完全に解く配点以外の配点の中で最も高い配点である。
直感的にはなんとなく分かる気がしつつ、「本当にそうなの？完答の配点に依らない？」と思ってしまいます。
が、完答の配点によって最小解答数が変わってくるのは事実ですが、上記のパターンの中にしか最小解答数が存在しないことはよく考えればその通りでした。
うーん、悔しいですね。
def dfs(i, sum, count, nokori): global ans if i == d: # G 点に満たなければ nokori のうち一番大きいものを解く if sum < g: use = max(nokori) # 解く問題が問題数を超えないように注意 n = min(pc[use - 1][0], -(-(g - sum) // (use * 100))) #ムダに-演算子を重ねているのは切り上げしたいから count += n sum += n * use * 100 if sum >= g: ans = min(ans, count) else: # 総合スコア、解いた問題数、まだ解いてない問題を更新 dfs(i + 1, sum, count, nokori) dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 + pc[i][1], count + pc[i][0], nokori - {i + 1}) d, g = map(int, input().split()) pc = [list(map(int, input().split())) for i in range(d)] ans = float("inf") dfs(0, 0, 0, set(range(1, d + 1))) print(ans)
コード中のコメントに記載してるのですが、Pythonで切り上げをする時のテクニック、面白いですね...！
Python で割り算をするときの切り上げと切り捨て | 民主主義に乾杯
ARC 029 A - 高橋君とお肉
これは、ここまでに出てきた中で一番素直ですね。
以下にコードを挙げます
def dfs(i: int, grill1: int, grill2: int): if i == n: return max(grill1, grill2) elif i < n: return min(dfs(i + 1, grill1 + t[i], grill2), dfs(i + 1, grill1, grill2 + t[i])) n = int(input()) t = [] for i in range(n): t.append(int(input())) print(dfs(0, 0, 0))
ABC 002 D - 派閥
複雑性が増しました。
他人のACコードを参考にしてしまったので悔しいです。
itertools.combinations() 関数で組み合わせを列挙できるのが凄く便利。
（これを使ってる解答が多かった。）
ということで、以下が解答になります。
import itertools n, m = map(int, input().split()) t = [[0]*n for _ in range(n)] def dfs(i, group): global ans if i == n: flag = True for i in itertools.combinations(group, 2): if t[i[0]][i[1]] == 0: flag = False break if flag: ans = max(ans, len(group)) else: dfs(i + 1, group) dfs(i + 1, group + [i]) for _ in range(m): x, y = map(int, input().split()) t[x-1][y-1] = 1 t[y-1][x-1] = 1 ans = 0 dfs(0, []) print(ans)
Lake Counting（蟻本 P.35）
これは蟻本の解答を素直にPythonで書けば良いだけですね。
n, m = map(int, input().split()) field = ["" for _ in range(n)] for i in range(n): field[i] = list(input()) def dfs(x, y): field[x][y] = "." for dx in range(-1, 2): for dy in range(-1, 2): nx = x + dx ny = y + dy if 0 <= nx < n and 0 <= ny < m and field[nx][ny] == "W": dfs(nx, ny) return res = 0 for i in range(n): for j in range(m): if field[i][j] == "W": dfs(i, j) res += 1 print(res)
ATC 001 A 深さ優先探索
自分で実装したのは以下のコードなのですが、一部のケースでTLEを吐いてしまいACできませんでした。
後述してますが、PyPyでコード提出していたのが原因でした。Pythonでコード提出すればACになります。
import sys sys.setrecursionlimit(10 ** 8) def dfs(i: int, j: int): global flg memo[i][j] = 1 if c[i][j] == "g": flg = True print("Yes") exit(0) for a in range(4): if 0 <= i + dy[a] < h and 0 <= j + dx[a] < w: if c[ i+dy[a] ][ j+dx[a] ] != "#" and memo[ i+dy[a] ][ j+dx[a] ] == 0: dfs(i+dy[a], j+dx[a]) return h, w = map(int, input().split()) c = [["" for _ in range(w)] for _ in range(h)] memo = [[0 for _ in range(w)] for _ in range(h)] for i in range(h): c[i] = list(input()) for j in range(w): if c[i][j] == "s": y, x = i, j flg = False dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] dfs(y, x) print("No")
どうしても分からなかったので、以下のQiitaで紹介されている解答コードをコピペして提出してみたのですが、寧ろTLEとなるケースが増える結果となりました。
なんとなくですが、どうもタッチの差でTLEになっているっぽいので少し工夫を考えてみます
理由が分かりました。
今までずっと PyPy3 (2.4.0) でコードを提出していたのですが、Python3 (3.4.3) でコードを提出するとACしました。
詳細は以下のQiitaが詳しいのですが、再帰処理と文字列操作に関してはPyPyだと結構遅くなってしまうようです。
ARC 031 B 埋め立て
これは、Python的な意味でかなり難問でした。
まず、配列を普通に = 演算子でコピーしようとすると、関数内で参照渡しになってしまうということ。
つまり、以下のコードの field[i][j] だけ書き換えたいのに A[i][j] も連動して書き換わってしまいます。
なので、copy ライブラリを使っています。
ここにも落とし穴があり、二次元配列の時は copy.copy() ではなく、copy.deepcopy() を使わないと結局参照渡しになってしまいます。
10 x 10 の地図なので、4重ループを使うというのもここまで競プロに慣れてくると抵抗があるのも結構しんどいですね。
import copy def dfs(x, y): field[x][y] = "x" for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < 10 and 0 <= ny < 10 and field[nx][ny] == "o": dfs(nx, ny) A = [list(input()) for i in range(10)] dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] for p in range(10): for q in range(10): if A[p][q] == "x": field = copy.deepcopy(A) field[p][q] = "o" count = 0 for i in range(10): for j in range(10): if field[i][j] == "o": dfs(i, j) count += 1 if count == 1: print("YES") exit(0) print("NO")
ARC 037 B バウムテスト
気付いてしまえばなんてことない問題ですが、解けませんでした。
関数dfsに前にいた値を持たせるところが思いつかなかったですね...！
def dfs(now, prev): global flag for next in g[now]: if next != prev: if memo[next]: flag = False else: memo[next] = True dfs(next, now) n, m = map(int, input().split()) g = [[] for _ in range(n)] for i in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 g[u].append(v) g[v].append(u) memo = [False for i in range(n)] ans = 0 for i in range(n): if not memo[i]: flag = True dfs(i, -1) if flag: ans += 1 print(ans)
AOJ 1160 島はいくつある？
これはほぼほぼ、蟻本と同じですね。以下になりました。
import sys sys.setrecursionlimit(10**8) ans = [] def dfs(x, y): c[x][y] = 0 for dx in range(-1, 2): for dy in range(-1, 2): nx = x + dx ny = y + dy if 0 <= nx < h and 0 <= ny < w and c[nx][ny] == 1: dfs(nx, ny) while True: w, h = map(int, input().split()) if w == 0 and h ==0: break count = 0 c = [[] for _ in range(h)] for i in range(h): if w == 1: c[i] = [int(input())] else: c[i] = list(map(int, input().split())) for x in range(h): for y in range(w): if c[x][y] == 1: dfs(x, y) count += 1 ans.append(count) for i in ans: print(i)
迷路の最短路（蟻本 P.37）
これは、Pythonのqueueライブラリを活用します。
そのまま本の通りに書けますね。
import queue INF = 10 ** 8 n, m = map(int, input().split()) maze = ["" for _ in range(n)] for i in range(n): maze[i] = list(input()) for i in range(n): for j in range(m): if maze[i][j] == "S": sx, sy = i, j elif maze[i][j] == "G": gx, gy = i, j dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] def bfs(): que = queue.Queue() d = [[INF for _ in range(m)] for _ in range(n)] que.put((sx, sy)) d[sx][sy] = 0 while que.empty() == False: p = que.get() if p[0] == gx and p[1] == gy: break for i in range(4): nx = p[0] + dx[i] ny = p[1] + dy[i] if 0 <= nx < n and 0 <= ny < m: if maze[nx][ny] != "#" and d[nx][ny] == INF: que.put((nx, ny)) d[nx][ny] = d[p[0]][p[1]] + 1 return d[gx][gy] res = bfs() print(res)
ABC 007 C 幅優先探索
これはほぼ、蟻本と同じですね。
個人的に詰まったところは、 q.qut( (sy, sx) ) の内側の括弧を記載忘れてしまってコードが上手く動かず、TypeError: 'int' object is not subscriptable が出てしまうシーンでした。
import queue INF = 10**8 def bfs(): q = queue.Queue() q.put((sy, sx)) d[sy][sx] = 0 while q.empty() == False: p = q.get() if p == (gy, gx): break for i in range(4): ny = p[0] + dy[i] nx = p[1] + dx[i] if 0 <= ny < r and 0 <= nx < w and c[ny][nx] == "." and d[ny][nx] == INF: q.put((ny, nx)) d[ny][nx] = d[p[0]][p[1]] + 1 r, w = map(int, input().split()) sy, sx = map(int, input().split()) gy, gx = map(int, input().split()) sy -= 1 sx -= 1 gy -= 1 gx -= 1 c = ["" for i in range(r)] for i in range(r): c[i] = list(input()) dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] d = [[INF for _ in range(w)] for _ in range(r)] bfs() print(d[gy][gx])
JOI 2010 予選 E チーズ
これは、上記の問題のスタート地点とゴール地点を入れ替えて繰り返す形の問題ですね。
素直にこんな感じで解けました。
（計算量を考えることがだんだん難しくなってきました。）
import queue INF = 10**8 def bfs(sx, sy, gx, gy): d = [[INF]*w for _ in range(h)] hp = 1 q = queue.Queue() q.put((sx, sy)) d[sx][sy] = 0 while q.empty() == False: now = q.get() if now[0] == gx and now[1] == gy: return d[gx][gy] for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if 0 <= nx < h and 0 <= ny < w and atlas[nx][ny] != "X" and d[nx][ny] == INF: q.put((nx, ny)) d[nx][ny] = d[now[0]][now[1]] + 1 h, w, n = map(int, input().split()) atlas = [[] for i in range(h)] cheese = [[] for i in range(n + 1)] for i in range(h): atlas[i] = list(input()) for i in range(h): for j in range(w): if atlas[i][j] == "S": cheese[0] = (i, j) for k in range(1, n + 1): if atlas[i][j] == str(k): cheese[k] = (i, j) dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] count = 0 for i in range(n): count += bfs(cheese[i][0], cheese[i][1], cheese[i + 1][0], cheese[i + 1][1]) print(count)
ABC 088 D Grid Repainting
これは、スタート地点が (0, 0) で、ゴール地点が (h-1, w-1) として上記までの迷路問題を適用すると、以下のようになります。
- ゴール地点までの最小移動回数が INF のままだったら、ゴールに辿り着けない
- ゴール地点までの最小移動回数 + 1の数のマスだけ白くしておけば、後は全部黒く塗りつぶして良い
上記のアイディア + 事前に黒く塗り潰されている点の数をさらに引き算すると以下のようなコードになりました。
import queue INF = 10**8 def bfs(): q = queue.Queue() q.put((sx, sy)) d[sx][sy] = 0 while q.empty() == False: now = q.get() if now[0] == gx and now[1] == gy: break for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if 0 <= nx < h and 0 <= ny < w and s[nx][ny] == "." and d[nx][ny] == INF: q.put((nx, ny)) d[nx][ny] = d[now[0]][now[1]] + 1 h, w = map(int, input().split()) count = 0 s = [[] for i in range(h)] for i in range(h): s[i] = list(input()) for j in range(w): if s[i][j] == "#": count += 1 sx, sy = 0, 0 gx, gy = h - 1, w - 1 dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] d = [[INF]*w for i in range(h)] bfs() if d[gx][gy] == INF: print(-1) else: ans = h * w - (d[gx][gy] + 1 + count) print(ans)
AGC 033 A - Darker and Darker
これまでの流れを踏まえて素直に解くと以下のコードになるのかなと思います。
が、TLEしてしまいました。
import queue def penetrate(x, y, count): global max_idx for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1: d[nx][ny] = count + 1 q.put((nx, ny, d[nx][ny])) max_idx = max(max_idx, d[nx][ny]) h, w = map(int, input().split()) d = [[-1] * w for _ in range(h)] A = [[] for i in range(h)] q = queue.Queue() for i in range(h): A[i] = list(input()) for j in range(w): if A[i][j] == "#": d[i][j] = 0 q.put((i, j, d[i][j])) dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] max_idx = 0 while q.empty() == False: idx = q.get() penetrate(idx[0], idx[1], idx[2]) print(max_idx)
ここまで、まともに計算量を考えてこなかったので改めて考えてみようと思います。
まず、for 文の二重ループに関しては O(H * W) なので 1.0e6 です。
うーん、結構この時点でギリギリですね。
次に、bfsを呼び出しているwhile文ですがこれは全マスについて計算しているので O(H * W) は確定です。
bfsの中で for i in range(4) としているので現時点で 4.0e6 です。
結構この時点でギリギリ感ありますが、逆に言えば queue 処理の計算量によってはなんとかなりそうなことも分かります。
ということで、調べてみたところ、queue.Queue() よりも collections.deque() を使った方が早いとのこと。
ただし、queue.Queue() は複数のスレッドを扱う場合でも安全に使うことができるのが利点のようです。
dequeに関して両端のアクセスはO(1)ということでした。
※queueに関してもたぶんそうですが。
O(1)なら、処理が早いdequeで勝てるのでは？
ということで collections.deque() を使って書き直してみました。
結果、PyPy3 で提出すれば無事ACとなりました。（Python3ではTLEする）
今後は queue じゃなくて deque を使うと誓いました。
from collections import deque def penetrate(x, y, count): global max_idx for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1: d[nx][ny] = count + 1 q.append((nx, ny, d[nx][ny])) max_idx = max(max_idx, d[nx][ny]) h, w = map(int, input().split()) d = [[-1] * w for _ in range(h)] A = [[] for i in range(h)] q = deque() for i in range(h): A[i] = list(input()) for j in range(w): if A[i][j] == "#": d[i][j] = 0 q.append((i, j, d[i][j])) dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] max_idx = 0 while len(q) > 0: idx = q.popleft() penetrate(idx[0], idx[1], idx[2]) print(max_idx)
ARC 005 C 器物損壊！高橋君
タイトルめっちゃ面白いじゃん。
これまでの迷路について、迷路の塀を二回まで破壊できるオプション付きの問題です。
普通のbfsだと、計算量は O(H * W) なので今回の問題だと 2.5e3程度 になりそうですね。
ここに更に塀を2回壊したいです。
壊す場合と壊さない場合で考えると、1回だけでも 2 ^ (H * W) でもうダメです。
他の方法を考えないといけない。。
ここで、今回求めたいのは「高橋君が魚屋に辿り着くことができるか」に着目してみます。
一番最初の蟻本でたどり着くための最小移動回数を入れていた d というリストに、高橋くんの残り体力を格納していくことにします。
これなら、G が初期値かそうじゃないかでなんとか解けそう...！ということでやってみました。
PyPy3 だとMLEとなってしまいますが、Python3 での提出なら無事ACできました。嬉しい。
from collections import deque def bfs(hp): q = deque() q.append((sx, sy, hp)) d[sx][sy] = initial_hp while len(q) > 0: now = q.popleft() if now[0] == gx and now[1] == gy: break for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if 0 <= nx < h and 0 <= ny < w: if d[nx][ny] == -1: if c[nx][ny] != "#": q.append((nx, ny, now[2])) d[nx][ny] = now[2] elif c[nx][ny] == "#": if now[2] > 0: q.append((nx, ny, now[2] - 1)) d[nx][ny] = now[2] - 1 else: if now[2] > d[nx][ny] and c[nx][ny] != "#": d[nx][ny] = now[2] q.append((nx, ny, now[2])) elif now[2] - 1 > d[nx][ny] and c[nx][ny] == "#" and now[2] > 0: d[nx][ny] = now[2] - 1 q.append((nx, ny, now[2] - 1)) h, w = map(int, input().split()) c = [[] for _ in range(h)] for i in range(h): c[i] = list(input()) for j in range(w): if c[i][j] == "s": sx, sy = i, j elif c[i][j] == "g": gx, gy = i, j dx = [1, 0, -1, 0] dy = [0, 1, 0, -1] d = [[-1]*w for _ in range(h)] initial_hp = 2 bfs(initial_hp) if d[gx][gy] > -1: print("YES") else: print("NO")
AOJ 0503 Cup
今までと比較すると毛色の違う問題です。
紙に書いてみると、各トレイをスタックと見做してカップ移動を考えられることが分かります。
そこで、トレイ3つの状態をキューとして渡すことでかなり汚いながらもコードは書けました。
が、案の定TLEしてしまったので解答を探して自分なり咀嚼して書いてみました。
アルゴリズムは自分が実装したものと同じでしたが、かなり分かりやすいコードで描かれており、かつ無駄な計算が少なかったです。
単純に自分には実装力が足りなかったのだなぁと凄く勉強になります。
特に参考になったのは以下の4点です。
- def main() を使うとそれだけで速くなる
- _, *list = [] って書き方マジで凄い（自分はこのためだけにfor文書いてました）
- 直前の操作を1桁の数字で表現してtに格納している（自分は直前のトレイの配列を入れていたので激重でした）
- q.pop()の結果は、カンマ区切りで複数の変数に格納できる
from collections import deque def main(): while True: n, m = [int(i) for i in input().split()] if n == 0 and m == 0: return _, *a = [int(i) for i in input().split()] _, *b = [int(i) for i in input().split()] _, *c = [int(i) for i in input().split()] a.insert(0, 0) b.insert(0, 0) c.insert(0, 0) q = deque() q.appendleft([a, b, c, 0, -1]) tmp = [i for i in range(0, n+1)] while q: # d はカウンタ, tは操作の種類を示す a, b, c, d, t = q.pop() """ print(a) print(b) print(c) print('=======') """ # 終了 if d > m: print(-1) break if a == tmp or c == tmp: print(d) break # a から b。 # 数字の大小比較と直前の操作が「b から a」ではないを確認。 if a[-1] > b[-1] and t != 1: q.appendleft([a[:-1], b+[a[-1]], c[:], d+1, 0]) # b から a if b[-1] > a[-1] and t != 0: q.appendleft([a+[b[-1]], b[:-1], c[:], d+1, 1]) # b から c if b[-1] > c[-1] and t != 3: q.appendleft([a[:], b[:-1], c+[b[-1]], d+1, 2]) # c から b if c[-1] > b[-1] and t != 2: q.appendleft([a[:], b+[c[-1]], c[:-1], d+1, 3]) if __name__ == '__main__': main()
特殊な状態の列挙（蟻本 P39~40）
ABC 054 C One-stroke Path
分からなかったので、解答を読んでしまいました。
答えとなりうるルートを予め全部生成して、正しいかどうかを判断するんですね...！
なるほど。。。
import itertools n, m = map(int, input().split()) path = [[False] * n for i in range(n)] for i in range(m): a, b = map(int, input().split()) a -= 1 b -= 1 path[a][b] = True path[b][a] = True ans = 0 # 頂点を並び替える順列を生成してループ for i in itertools.permutations(range(n), n): # 頂点1が始点 if i[0] == 0: # 生成した順列の中をさらにループ for j in range(n): # n - 1 まで続いたら条件を満たすパスが存在する if j == n - 1: ans += 1 break # i[j] から i[j + 1] に行くパスがなければ終了 if not path[i[j]][i[j + 1]]: break print(ans)
JOI 2009 予選 D カード並べ
非常に分かりやすい問題だった気がしています！
素直に解けますね。
import itertools ans = [] while True: n = int(input()) k = int(input()) if n == 0 and k == 0: break cards = [] ans_set = [] for i in range(n): cards.append(input()) for i in itertools.permutations(cards, k): ans_set.append(int("".join(i))) ans.append(len(set(ans_set))) for i in ans: print(i)
yukicoder No.133 カードゲーム
これも素直に解くことができますね。
import itertools n = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) a_rate_numerator = 0 count = 0 for a in itertools.permutations(A, n): for b in itertools.permutations(B, n): count += 1 a_score = 0 b_score = 0 for i in range(n): if a[i] > b[i]: a_score += 1 elif b[i] > a[i]: b_score += 1 if a_score > b_score: a_rate_numerator += 1 print(a_rate_numerator / count)
まとめ
今回、かなり長くなりましたが一旦まとめます。
（特殊な状態の列挙、に関しては別記事にします。）
- 部分和問題のような、「〇〇する or しない」の二択で条件分岐するものはdfsで解けることが多い
- dfsを再帰関数で表現する場合、PyPyを使うと死ぬ
- 直前の処理を記憶させた変数を引数にしたりキューに渡すと良いことがある。
- 3の、直前の処理の記憶は判別できればなんでもいい。（1桁の数字でも良い）
- nの取り得る範囲が小さい時、itertoolsを使うと便利なことがある
- リストの取り扱い、下手にやると参照渡しになってしまうので注意。どうしてもの場合は、copy関数を使うと良い
- queue.Queue()よりもcollections.deque()を使うべき
- 高速化のテクニックは細かく色々ある
ということで、本日は以上です。
それではまた〜。
