背景：Pythonで蟻本をやります - 競プロはじめました
テキスト：
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://m.media-amazon.com/images/I/41oruV+aJIL._SL500_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
しゃくとり法
Subsequence
3-1が二分探索だったので，問題を読んだときに，あれ？二分探索？と思いました．実際，二分探索の解法も載っていました．【入力1】
10 15 5 1 3 5 10 7 4 9 2 8
【出力1】
2
【入力2】
5 11 1 2 3 4 5
【出力2】
3
【コード】
n, s = map(int, input().split()) a = list(map(int, input().split())) res = n+1 # 解が存在するなら 1 <= res <= n st, end, tot = 0, 0, 0 while True: while end < n and tot < s: tot += a[end] end += 1 if tot < s: break res = min(res, end-st) tot -= a[st] st += 1 if res > n: res = 0 print(res)
Jessica's Reading Problem
【入力】5 1 8 8 8 1
【出力】
2
【コード】
from collections import defaultdict p = int(input()) a = list(map(int, input().split())) n = len(set(a)) # 種類の総数 st, end, num = 0, 0, 0 count = defaultdict(int) # {種類:出現数} res = p while True: while end < p and num < n: # ページが終わらない & 全種出ない =>ループ if count[a[end]] == 0: num += 1 count[a[end]] += 1 end += 1 if num < n: # ページ終わって全種出てないならstr変えてもダメ=>抜ける break # 全種出たなら更新 res = min(res, end-st) # st進める count[a[st]] -= 1 if count[a[st]]==0: num -= 1 st += 1 print(res)
反転
反転操作を，「あるマスを起点に，反転範囲のマスに1を加える操作」と考えるとわかりやすいです（各マスの初期値はゼロ）．反転したかどうかは，各マスの値の偶奇を判定すればわかります．こう考えると，
- 同じマスを起点に2回反転させる操作は，0回反転と同じ．よって，各マス起点の反転操作は0回か1回のみ．
- 反転操作の順序は関係ない．
あとは，この2つの事実から，「反転させるか否かを1マスずつ確定させる方法」を考えていくことになります．
処理においては，「各マスの表裏」を記憶するのではなく，「各マス起点の反転操作をしたか」を記憶します．これにより，反転操作のたびに影響範囲を更新する必要がなくなります．「各マスの表裏」は，[着目しているマスを反転範囲に含むマス]を起点とした反転操作の回数（の偶奇）から，その都度求められます．
Face The Right Way
①各区間の反転は0か1回，②反転順序は関係ない，③左端の牛を反転させる方法は1通りしかない，という事実から，左端の区間を反転させるか否かが確定します．よって，次の手順で実現できます．
- $K$を1つ固定し，牛$i$を$0$から$N-K+1$まで順に見ていく．
- 牛$i$が後ろを向いていれば，区間$[i, i+K-1]$の$K$頭を反転する．
- 全ての反転操作が終了後，全ての牛が前を向いていれば，操作回数を更新する．
1, 2 では，牛$i$の向きを$0\leq i \leq N-K+1$の各$i$について見ていきます．したがって，操作回数の最悪値は$N-K+1$回です．
さらに，各操作では$K$頭の牛を反転させるので，計算量は
\begin{aligned}
\sum_{K=1}^{N} (N-K+1) \cdot K
&=O(N^{3})
\end{aligned}
となります（$\sum_{K=1}^{N} K=N(N+1)/2$，$\sum_{K=1}^{N} K^{2}=N(N+1)(2N+1)/6$）．$N=5000$が最大なので，これでは間に合いません．\sum_{K=1}^{N} (N-K+1) \cdot K
&=O(N^{3})
\end{aligned}
計算量を減らせそうなところは，「$K$頭を反転させる」という部分です．そこで，各反転操作で処理する対象を$K$単位ではなく，何か1単位のものに変えることを考えます．最も素直なのは，区間$[i, i+K-1]$を反転させる処理にすることです．このとき問題となるのは，牛$i$が向いている方向を（小さい計算量で）得られるかどうかです．
上の考えで上手くいくか確かめるため，区間$[i, i+K-1]$を反転させたことを$1$，させていないことを$0$で表す配列$f[i]$を用意します．1, 2 で牛$i$を確認するとき，反転操作があるとすればこの牛より前（$j \leq i -1$）であり，牛$i$が反転操作があった区間に含まれいた（$i\in [j, j+K-1]$）場合，影響を受けています．牛$i$が反転を受けた偶奇をみれば，現在の向きがわかるわけですが，これは
\begin{aligned}
g[i]=\sum_{j=\max(0, i-K+1)}^{i-1} f[j]
\end{aligned}
の偶奇からわかります．g[i]=\sum_{j=\max(0, i-K+1)}^{i-1} f[j]
\end{aligned}
これがどれだけの計算量でできるかですが，前ステップで$g[i]$が計算されているとき，次ステップで使う$g[i+1]$は
\begin{aligned}
&g[i+1] \\
&=
\begin{cases}
\, g[i] + f[i] - f[i-K+1] & (i-K+1 \geq 0)\\
\, g[i] + f[i] & (i-K+1 < 0)
\end{cases}
\end{aligned}
で更新できます．よって，$O(1)$で済みます．&g[i+1] \\
&=
\begin{cases}
\, g[i] + f[i] - f[i-K+1] & (i-K+1 \geq 0)\\
\, g[i] + f[i] & (i-K+1 < 0)
\end{cases}
\end{aligned}
以上より，$O(N^{2})$に計算量が減り，時間内に計算できます．
3. では$N-K+1 < i \leq n$の牛$i$が前を向いているか確認する必要があります．この範囲を考えるとき，もう反転操作は行わないので，
\begin{aligned}
&g[i+1] \\
&=
\begin{cases}
\, g[i] - f[i-K+1] & (i-K+1 \geq 0)\\
\, g[i] & (i-K+1 < 0)
\end{cases}
\end{aligned}
で更新できます（つまり，$0\leq i \leq N-1$の$g[i]$の一般式は&g[i+1] \\
&=
\begin{cases}
\, g[i] - f[i-K+1] & (i-K+1 \geq 0)\\
\, g[i] & (i-K+1 < 0)
\end{cases}
\end{aligned}
\begin{aligned}
g[i]=\sum_{j=\max(0, i-K+1)}^{\min(i, N-K+1)-1} f[j]
\end{aligned}
ということです）．g[i]=\sum_{j=\max(0, i-K+1)}^{\min(i, N-K+1)-1} f[j]
\end{aligned}
【入力】
7 BBFBFBB
【出力】
3 3
【コード】
n = int(input()) dir = list(input()) dir = [0 if x=='F' else 1 for x in dir] def calc(k): res, g = 0, 0 f = [0] * n for i in range(n-k+1): # 牛を左から順に見る if (dir[i] + g) % 2 != 0: # 後ろを向いている場合 => 区間反転 res += 1 f[i] = 1 g += f[i] if i-k+1 >= 0: g -= f[i-k+1] # n-k+1までは前を向かせた => 残りが前を向いているか確認 for i in range(n-k+1, n): if (dir[i] + g) % 2 != 0: # 解無し return -1 if i-k+1 >= 0: g -= f[i-k+1] return res ans_k, ans_m = 1, n # 最悪値 for k in range(1, n+1): m = calc(k) if m >= 0 and ans_m > m: ans_k, ans_m = k, m print(ans_k, ans_m)
【メモ】
入力のところで，こんな書き方があるのか〜と感心しました．
Pythonで理解する蟻本「3-2 Face The Right Way（POJ No.3276）」(p.139) - クルトンのプログラミング教室
DIR = [c == 'B' for c in input()] # 牛の方向(0:F, 1:B)
boolになるのに大丈夫？と思いましたが，以下よりOK：
Pythonの真偽値bool型（True, False）と他の型との変換・判定 | note.nkmk.me
Fliptile
端を反転させる方法が複数あるため，上の問題とは異なり，端の反転方法が確定しません．そこで，- 1行目の各マス中心の反転操作を全て試す
- 1行目の不足分を補うように，2行目の反転操作を確定する
- 以下，繰り返す
【入力】
4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
【出力】
0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0
【コード】
from copy import deepcopy m, n = map(int, input().split()) tile = [list(map(int, input().split())) for _ in range(m)] # あるマスを起点に反転させたときの影響範囲 (x+dx, x+dy) dx = [-1, 0, 0, 0, 1] dy = [0, -1, 0, 1, 0] def get(x, y): """ x, yのマスの色を影響範囲の反転有無から計算 """ c = tile[x][y] # 初期値 for d in range(5): x2, y2 = x+dx[d], y+dy[d] if 0 <= x2 < m and 0 <= y2 < n: # 存在するマスなら影響を加算(←flipはゼロで初期化) c += flip[x2][y2] return c % 2 def calc(): """ 1行目を決めたときの最小手数を計算 (解なしなら-1) """ for i in range(1, m): # 2行目以降 for j in range(n): # 列を左から順に見て，上のマスが1なら(i,j)起点に反転操作 if get(i-1, j): flip[i][j] = 1 # 全ての反転操作終了後，最後の行が全て0かチェック for j in range(n): if get(m-1, j): # 解なし return -1 # 反転回数を出力 res = sum([flip[i][j] for i, j in zip(range(n), range(m))]) return res # --- 処理 --- ## 解を求める opt = [['']*n for _ in range(m)] # 最適解 res = -1 # 初回判定のための初期値 for i in range(1<<n): # 1行目を辞書順で全通り試す(2^N) flip = [[0]*n for _ in range(m)] # 初期化 for j in range(n): # 右からj番目のビットをセット flip[0][n-j-1] = i >> j & 1 num = calc() # 操作回数 if num >= 0 and (res < 0 or res > num): # 解あり & (初回 or もっと短い手数) の場合は更新 res = num opt = deepcopy(flip) ## 出力 if res < 0: print('IMPOSSIBLE') else: for l in opt: print(*l)
弾性衝突
Physics Experiment
【入力1】1 10 10 100
【出力1】
4.95
【入力2】
2 10 10 100
【出力2】
4.95 10.20
【コード】
$i$秒遅れること，$R$はcmで与えられていることに注意します．
n, h, r, t = map(int, input().split()) g = 10 def calc(t): """ R = 0, t=0 でボールを落下させたときの 時刻tでのボールの高さ """ if t < 0: return h t2 = (2 * h / g) ** 0.5 k = t // t2 if k % 2: d = k * t2 + t2 - t else: d = t - k * t2 return h - g * d * d / 2 y = sorted([calc(t - i) + 2 * r * i / 100 for i in range(n)]) y = [format(yi, '.2f') for yi in y] print(*y)
【ボール1個の運動】
注：書籍とは$t$と$T$が逆になっています（気持ち悪かったため．．．）．
鉛直上向きを正方向に取ると，運動方程式は
\begin{aligned}
m\ddot{x}(t)=-mg
\end{aligned}
となります．時間について積分すれば，速度m\ddot{x}(t)=-mg
\end{aligned}
\begin{aligned}
\dot{x}(t)-\dot{x}(t_{0})=-g(t-t_{0})
\end{aligned}
が得られます．①落下時と，②上昇時にわけて考えます．\dot{x}(t)-\dot{x}(t_{0})=-g(t-t_{0})
\end{aligned}
①落下の場合は初速ゼロなので
\begin{aligned}
\dot{x}(t)=-gt
\end{aligned}
です．もう一度積分すれば，$x(0)=H$から\dot{x}(t)=-gt
\end{aligned}
\begin{aligned}
x(t)=-\frac{1}{2}gt^{2} + H
\end{aligned}
となります．地面にぶつかる時刻を$T$とすれば，$x(T)=0$から$H=\frac{1}{2}gT^{2}$がわかります．x(t)=-\frac{1}{2}gt^{2} + H
\end{aligned}
②上昇するときを考えます．もし，地面にぶつかった時刻を$t_{0}=0$に取り直せば，落下運動を逆再生した運動
\begin{aligned}
x(t)=-\frac{1}{2}g(T-t)^{2} + H
\end{aligned}
をします．実際に，運動方程式から求めてみます．エネルギー保存則から，初速は地面に落下したときの速度の符号を変えた$\dot{x}(T)=gT$です．よってx(t)=-\frac{1}{2}g(T-t)^{2} + H
\end{aligned}
\begin{aligned}
\dot{x}(t)
&=-g(t-T)
\end{aligned}
です．時間について積分すれば，$x(0)=0$から\dot{x}(t)
&=-g(t-T)
\end{aligned}
\begin{aligned}
x(t)
&=-\frac{1}{2}g(t-T)^{2} + \frac{1}{2} gT^{2} \\
&=-\frac{1}{2}g(T-t)^{2} + H
\end{aligned}
なので確かめられました．x(t)
&=-\frac{1}{2}g(t-T)^{2} + \frac{1}{2} gT^{2} \\
&=-\frac{1}{2}g(T-t)^{2} + H
\end{aligned}
ここまで，1往復の運動を見てきました．周期運動なので，時間の原点をずらせば上の解が使えます（$t\to t - kT$とする）．
【すり抜けたとみなしてよい理由】
物体1, 2の衝突前の速度を$v_{1},v_{2}$，衝突後の速度を$v_{1}^{\prime},v_{2}^{\prime}$とします．
運動量保存則，エネルギー保存則は
\begin{aligned}
\begin{cases}
\, mv_{1}+m v_{2} = mv^{\prime}_{1}+m v^{\prime}_{2} \\
\, \displaystyle
\frac{1}{2}mv_{1}^{2} + \frac{1}{2}mv_{2}^{2}
=\frac{1}{2}mv_{1}^{\prime\,2} + \frac{1}{2}mv_{2}^{\prime\,2}
\end{cases}
\end{aligned}
です．\begin{cases}
\, mv_{1}+m v_{2} = mv^{\prime}_{1}+m v^{\prime}_{2} \\
\, \displaystyle
\frac{1}{2}mv_{1}^{2} + \frac{1}{2}mv_{2}^{2}
=\frac{1}{2}mv_{1}^{\prime\,2} + \frac{1}{2}mv_{2}^{\prime\,2}
\end{cases}
\end{aligned}
運動量保存則より$v_{1} + v_{2} =v^{\prime}_{1}+v^{\prime}_{2}$が得られ，エネルギー保存則より
\begin{aligned}
0
&= (v_{1}-v^{\prime}_{1})(v_{1}+v^{\prime}_{1}) + (v_{2}-v^{\prime}_{2})(v_{2}+v^{\prime}_{2}) \\
&=(v_{1}-v^{\prime}_{1}) [(v_{1}+v^{\prime}_{1}) - (v_{2}+v^{\prime}_{2})]
\end{aligned}
が得られます．したがって，①$v_{1}-v^{\prime}_{1}=0$か，②$v_{1} - v_{2} =-v^{\prime}_{1}+v^{\prime}_{2}$のいずれかが成り立ちます．0
&= (v_{1}-v^{\prime}_{1})(v_{1}+v^{\prime}_{1}) + (v_{2}-v^{\prime}_{2})(v_{2}+v^{\prime}_{2}) \\
&=(v_{1}-v^{\prime}_{1}) [(v_{1}+v^{\prime}_{1}) - (v_{2}+v^{\prime}_{2})]
\end{aligned}
①の場合は$v^{\prime}_{1}=v_{1}$，$v^{\prime}_{2}=v_{2}$です．すり抜ける場合に対応しています．
②の場合は$v^{\prime}_{1}=v_{2}$，$v^{\prime}_{2}=v_{1}$です．衝突後，逆方向に跳ね返る場合に対応しています．2つの物体の速度が入れ替わっていることがわかります．
【$R > 0$の場合の考え方】
ナイーブには理解できますが，まだ明快な説明ができません．
ボールの中心の運動は，落下距離が同じなら変わらない（位置の原点のとり方を除く）．
ボールに大きさがある分，上方から落下させれば，ボール中心の運動は$R=0$で同時に落下させたときとおなじになる（運動範囲は$R\cdot i$上方にシフトさせた領域になる （$i$は下方にあるボールの個数）．）．例えば，2つのボールが離れた分，ボールが大きくなっていることから，衝突のタイミングは変わらない．
半分全列挙
4 Values whose Sum is 0
知らないと，こういう発想はなかなかできないですねぇ．【入力】
6 -45 -41 -36 -36 26 -32 22 -27 53 30 -38 -54 42 56 -37 -75 -10 -6 -16 30 77 -46 62 45
【出力】
5
【コード】
import bisect n = int(input()) a = list(map(int, input().split())) b = list(map(int, input().split())) c = list(map(int, input().split())) d = list(map(int, input().split())) # C[i]+D[j]を全通り計算してソート cd = [''] * (n**2) for i in range(n): for j in range(n): cd[i * n + j] = c[i] + d[j] cd.sort() # A[i]+B[j]と等しくなるCDの要素数をカウント res = 0 for i in range(n): for j in range(n): cd2 = -(a[i] + b[j]) res += bisect.bisect_right(cd, cd2) - bisect.bisect_left(cd, cd2) print(res)
巨大ナップサック
個数制限なしです．【入力】
4 5 2 1 3 2 3 2 4 2
【出力】
7
【コード】
import bisect n, w = map(int, input().split()) wl = list(map(int, input().split())) vl = list(map(int, input().split())) # 前半の重さの総和・価値の総和を全列挙 n2 = n // 2 ps = [''] * (1 << n2) for i in range(1 << n2): w2, v2 = 0, 0 for j in range(n2): if i >> j & 1: # j番目のビットが立っていたら w2 += wl[j] v2 += vl[j] ps[i] = [w2, v2] # 重いのに価値が低い(or 同じ)ものを除く # w2[i] < w2[j] => v2[i] < v2[j] # ps[0]~ps[m-1]にデータを上書きしていく (p[m]以降は使わない) ps.sort() m = 1 for i in range(1, 1 << n2): if ps[m - 1][1] < ps[i][1]: ps[m] = ps[i] m += 1 # 後半の重さの総和・価値の総和を全列挙 res = 0 for i in range(1 << (n - n2)): w1, v1 = 0, 0 for j in range(n - n2): if i >> j & 1: # j番目のビットが立っていたら w1 += wl[n2 + j] v1 += vl[n2 + j] if w1 <= w: # total value # (w - w1, inf) は w2<=Wとなるものの右側にくる # いっそのことbisect_rightのほうがわかりやすいかも tvi = bisect.bisect_left(ps, [w - w1, float('inf')], hi = m) res = max(res, v1 + ps[tvi - 1][1]) print(res)
座標圧縮
次が参考になりました．座標圧縮の解説（1次元から2次元の圧縮まで） | アルゴリズムロジック
領域の個数
$i$番目の直線の始点が$(X1[i],Y1[i])$で，終点が$(X2[i],Y2[i])$です．$X$軸の圧縮は，各線分の端点が左から何番目かを表す新しい座標$X^{\prime}$を導入する，と言えます．ただし，分断された領域を考えたいので，「端点-端点」，「端点-フチ」の間に少なくとも余白を1つ確保する必要があります．ここでは，端点の前後の点も新しい$X^{\prime}$座標にマッピングすることで余白を確保します．
1つの線分につき端点が2つあり，端点・前・後の3点を保存するので，$2\times 3=6$個の記憶領域が必要です．
幅優先探索（BFS）を使います．
迷路の最短路 | Pythonで蟻本2-1 - DFS，BFS
【入力】
10 10 5 1 1 4 9 10 6 10 4 9 10 4 8 1 1 6 4 8 10 5 10
【出力】
6
【コード】
from collections import deque w, h, n = map(int, input().split()) x1 = list(map(int, input().split())) x2 = list(map(int, input().split())) y1 = list(map(int, input().split())) y2 = list(map(int, input().split())) def compress(p1, p2, w): """ p1, p2をp軸方向に座標圧縮し, 圧縮後の幅を返す """ ps = set() for i in range(n): for d in [-1, 0, 1]: # 全ての端点のある列とその前後を記憶 tp1, tp2 = p1[i] + d, p2[i] + d if 1 <= tp1 <= w: ps.add(tp1) if 1 <= tp2 <= w: ps.add(tp2) ps = sorted(list(ps)) # 「psの何番目か」という情報に変換（圧縮） p1 = [ps.index(p1[i]) for i in range(n)] p2 = [ps.index(p2[i]) for i in range(n)] return p1, p2, len(ps) # --- 処理 --- # 座標圧縮 x1, x2, w = compress(x1, x2, w) y1, y2, h = compress(y1, y2, h) # 線のある部分を塗りつぶし fld =[[False] * (n * 6) for _ in range(n * 6)] # fieldの略? for i in range(n): for y in range(y1[i], y2[i] + 1): for x in range(x1[i], x2[i] + 1): fld[y][x] = True # 領域を数える ## 4方向の移動ベクトル：(dx[i], dy[i]) dx, dy = [1, 0, -1, 0], [0, 1, 0, -1] ans = 0 for y in range(h): for x in range(w): if fld[y][x]: # 空白でないならスキップ continue # (x, y)が空白の場合， # (x, y)を起点に上下左右の空白マスを全てたどり， # 調べたマスを全て塗りつぶす ans += 1 que = deque([]) # 調べるマスを入れるキュー que.append([x, y]) # (x, y)が起点 while len(que): sx, sy = que.popleft() # 調査対象(search/second_x,yの略?) for i in range(4): # 上下左右を調べる tx, ty = sx + dx[i], sy + dy[i] # temp_x,yの略? if tx < 0 or w <= tx or ty < 0 or h <= ty: # 範囲外ならスキップ continue if fld[ty][tx]: # 空白でないならスキップ continue # (sx, sy)の隣接した空白を調査対象に追加し，(sx, sy)を塗りつぶす que.append([tx, ty]) fld[ty][tx] = True print(ans)
