目次
三井住友信託銀行プログラミングコンテスト2019 C～F問題メモ
C - 100 to 105
問題
- 商店では、$100～105$ 円の6種類の品物が売られている
- 合計金額をちょうど $X$ 円にできる買い方が存在するか判定せよ
- 品物は各種沢山あり、品切れにはならない
- $1 \le X \le 100000$
解法
100円を買えるだけ買ったとして、後から適宜101～105円に置き換えて調整する。
$X / 100 = d あまり m$ として、100円を $d$ 個買って、残り $m$ 円を調整するのに $d$ 個では足りなかったらアウト。なので、交換個数はなるべく少なくしたい。
よって調整の仕方は、105円に置き換えられるだけ置き換えて、最後の端数があったら101～104円を1個だけ置き換えればよい。
100円から105円への置き換えで5円詰められるので、$d$ 個で調整できる範囲は $5d$ まで。 $m \le 5d$ ならよい。
x = int(input()) d, m = divmod(x, 100) print(1 if 5 * d >= m else 0)
D - Lucky PIN
問題
- '0'～'9'からなる文字列 $S$ が与えられる
- 長さ3の部分列（連続でなくてもよい）は何種類あるか？
- 同じ数字の並びは重複しては数えない
- $4 \le |S| \le 30000$
解法
長さ1、長さ2、長さ3 でそれぞれ取れる部分列の集合を先頭から更新していく。
それぞれの集合をL1,L2,L3とする。 集合には、重複を許さないデータ構造を使う。
$i$ 番目の数字を $c$ として、$i-1$ 番目までの処理が終わっている L1,L2,L3 に対して、以下をすればよい。
- L2の各要素に $c$ を付け加えたものをL3に加える
- L1の各要素に $c$ を付け加えたものをL2に加える
- $c$ をL1に加える
S 123123 L1 L2 L3
i=0 1 {1}
1 2 {1,2} {12}
2 3 {1,2,3} {12,13,23} {123}
3 1 {1,2,3} {12,13,23,11,21, {123,121,131,231}
31}
4 2 {1,2,3} {12,13,23,11,21, {123,121,131,231,122,
31,22,32} 132,232,112,212,312}
5 3 {1,2,3} {12,13,23,11,21, {123,121,131,231,122,
31,22,33} 132,232,112,212,312,
133,233,113,213,313,223,323}
最終的に、L3の長さが答え。
L2からL3へ移すところが計算量的にボトルネックとなる。 文字の種類（今回は10種）を $D$ とすると、計算量は $O(D^2N)$。
n = int(input())
s = input()
d1 = set()
d2 = set()
d3 = set()
for c in s:
for t in d2:
d3.add(t + c)
for t in d1:
d2.add(t + c)
d1.add(c)
print(d1, d2, d3)
print(len(d3))
解法2
'000'～'999' それぞれについて可能か調べる。解説pdf1個目の解法。
'312' が可能か調べたければ、以下のようにする。各過程で、目標の数字が存在しなければ'312'は不可能。
- 先頭から最初に出現する'3'の位置を得る
- それ以降で次に最もはやく出現する'1'の位置を得る
- それ以降に'2'が存在したら、OK
これを高速に実装するには、各数字につき、何番目に出現するかのindexリストをまず作成しておく。
- 数字 $k$ に対してのindexリストを $loc_k$ とする
- 数字 $k$ に対して最後に出現するindexを $last_k$ とする
S 123123 ↓ loc1: [0, 3] last1: 3 loc2: [1, 4] last2: 4 loc3: [2, 5] last3: 5
- 1桁目の数字 $x$ を10通り試す
- $i=loc_x[0]$ が最初のindex
- 2桁目の数字 $y$ を10通り試す
- $i+1$ 以降で最小のindexを $loc_y$ から二分探索で得る。これを $j$ とする
- 3桁目の数字 $z$ を10通り試す
- $j \lt last_z$ なら、部分列 'xyz' は作れる
計算量は、$O(N+D^2(D+\log{N}))$ となる。$N$ が大きければ、だいたい最初の $O(N)$ のindexリストの作成が一番時間のかかる処理となる。
from bisect import bisect
n = int(input())
s = input()
location = [[] for _ in range(10)]
for i, c in enumerate(map(int, s)):
location[c].append(i)
last_indices = [loc[-1] if loc else -1 for loc in location]
ans = 0
for loc_x in location:
if not loc_x:
continue
i = loc_x[0]
for loc_y in location:
ji = bisect(loc_y, i)
if ji >= len(loc_y):
continue
j = loc_y[ji]
ans += sum(j < li for li in last_indices)
print(ans)
あと、Pythonでは文字列検索が十分速いため、下手にindexを前計算するより、1文字ずつ検索する方が、この制約下では速かったりする。
E - Colorful Hats 2
問題
- $N$ 人の人が一列に並び、前から順に $1,2,3,...,N$ と番号が付けられている
- それぞれの人は、赤・青・緑のいずれかの帽子を被っている
- 番号 $i$ の人は「自分より前に、自分と同色の帽子を被っている人は $A_i$ 人いる」と発言した
- 全ての人の発言が正しくなるような $N$ 人の帽子の色の並びとして考えられるパターン数を求めよ
- $1 \le N \le 10^5$
解法
DP。
「$i$ 人目まで見て、$k$ 人が被っている色はいくつあるか？」を更新していく。最初は $k=0$ が3つ。
$i$ 番目の人の発言が $A_i$ 人とすると、$i-1$ 人までで被っている人数がちょうど $A_i$ 人の色がないと達成不可能。 さらに $i$ 番目の人が同じ色なので、その色の帽子は $i$ 人目を加えると $A_i+1$ 個となる。
$A_i$ 個ある帽子が複数ある場合はどれを選んでもよいので、その数だけパターン数は乗算される。
k= 0 1 2 3 Ans Ai 3 1 0 2 1 3 0 1 2 6 1 1 1 1 12 0 2 1 12 1 1 2 24 2 1 1 1 48
n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [0] * (n + 1)
dp[0] = 3
ans = 1
for a in aaa:
ans = ans * dp[a] % MOD
dp[a] -= 1
dp[a + 1] += 1
print(ans)
F - Interval Running
問題
- 一直線の無限に続くランニングコースをAさんとBさんが同じ位置からスタートする
- Aさんは最初の $T_1$ 分間、分速 $A_1$ [m]で走り、次の $T_2$ 分間、分速 $A_2$ [m]で走り、これを交互に繰り返す
- Bさんは最初の $T_1$ 分間、分速 $B_1$ [m]で走り、次の $T_2$ 分間、分速 $B_2$ [m]で走り、これを交互に繰り返す
- AさんとBさんが出会う（同じ位置に来る）回数は何回か求めよ
- スタート地点は除く
- 無限回出会う場合は'infinity'と出力する
- $1 \le T_i \le 10^5$
- $1 \le A_i,B_i \le 10^{10}$
- $A_1 \neq B_1$
- $A_2 \neq B_2$
解法
変な読み違いをして時間をかけてしまった。速度だけでなく、時間周期 $T_1,T_2$ も、AさんとBさんで別々だと思い込んでしまった。（まぁそれでも変曲点ごとに分解すれば解ける。実装がやたら面倒くさいが）
場合分け。F問題にしては簡単？ 速度と距離のグラフを書くと理解の整理になる。
周期が $T_1+T_2$ で共通（これを $\lambda$ とする）なので、$\lambda$ で進む距離が等しければ、$\lambda$ ごとに必ず出会い続けるので、infinity。
そうでない場合、より多くの距離を進む方をBさんとする。（逆の場合、適当にひっくり返す）
Aさんが $\lambda$ で進む距離（$=A_1T_1 + A_2T_2$）を $A_t$、Bさんを $B_t$ とする。1周期でつく距離差を $D_d$ とする。
A1<B1の場合
Aさんは $T_1$ で出遅れ、その差は $A_t \lt B_t$ なので挽回できることはない。よって0回。
A1>B1の場合
Aさんが先行するが、$T_2$ の領域で抜かされる。
$T_1,T_2$ の各領域で「何周期先まで、この領域で交わり続けるか？」を考える。
2周期目では、Bさんは $D_d$ だけ進んだ位置からスタートしていると見なせる。3周期目では $2D_d$、4周期目では $3D_d$。。。
距離 | / | | | /| | / | | | / | | __-/~~ | | __ |_-/~~| | A ／ / | A ／| ↑d | / | | ／ / B | ／ B| ↓ |/ | |／_--~~ |／_--~| ~~ | | |------|------|時間 |------| |-----| T1 T2 T1 T2
ここで $T_1$ 終了時点の両者の差を $d$ とすると、
- 領域 $T_1$ では $\frac{d}{D_d}$（切り捨て）周期先まで交わることができる
- 領域 $T_2$ でも $\frac{d}{D_d}$（切り捨て）周期先まで交わることができる
ただし、$T_2$ 領域では1周期目でも交わっているので、$+1$ される。
また、$d$ がちょうど $D_d$ で割り切れる場合、最後の1回の接触が領域1と2で重複して数えられてしまうので、注意する。
def solve(t1, t2, a1, a2, b1, b2):
at = a1 * t1 + a2 * t2
bt = b1 * t1 + b2 * t2
if at == bt:
return 'infinity'
if at > bt:
a1, a2, b1, b2 = b1, b2, a1, a2
at, bt = bt, at
ans = 0
if a1 > b1:
dd = bt - at
ans += ((a1 - b1) * t1 - 1) // dd
ans += (a1 - b1) * t1 // dd + 1
return ans
t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())
print(solve(t1, t2, a1, a2, b1, b2))
