−目次

三井住友信託銀行プログラミングコンテスト2019 C～F問題メモ
- C - 100 to 105
  - 問題
  - 解法
- D - Lucky PIN
  - 問題
  - 解法
  - 解法2
- E - Colorful Hats 2
  - 問題
  - 解法
- F - Interval Running
  - 問題
  - 解法

三井住友信託銀行プログラミングコンテスト2019 C～F問題メモ

Sumitomo Mitsui Trust Bank Programming Contest 2019

解説放送: 三井住友信託銀行プログラミングコンテスト2019 - YouTube

出張先からの参加。ラップトップのコンテスト環境がまだ整えられてないのでとっとと整えるべき。

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))