2020-04-30

JOI難易度７テンキー

競プロ

問題原文

問題要旨

みたなテンキーを考える。
最初カーソルが 0 においてあって、上下右左へ移動 or クリックで１回の操作と考える。
$M$ で割ったあまりが $R$ になるような数を入力するまで、最低何回の操作が必要か？

$1 \leq M \leq 10000$
$1 \leq R ＜ M$

解法

「時間いっぱい探索すればええやろ！w」と思ったけどやっぱり落ちた（まぁ流石にね）
状態の同一視を意識して考えると、
$dp[n\rbrack[x\rbrack :=$ カーソルが $n$ にあって、あまりが $x$ であるような状態にするための最小操作回数
がみえる。

更新順がえいってできる感じではないので、拡張ダイクストラみたいにやる。
実際は移動コストは１なのでBFSの拡張をするみたいにする。

実装

移動 + クリックをしたところに直接遷移すると、クリックしない場合とか同じマスでクリックする場合とか考えないといけなくなって面倒。
「キューから取り出した時にクリックする」ことにすれば、4方向の移動を考えるのが楽になる。

from collections import deque
M, R = map(int, input().split())
board = [
    [0, 1],
    [1, 0, 2, 4],
    [2, 1, 3, 5],
    [3, 2, 6],
    [4, 1, 5, 7],
    [5, 2, 4, 6, 8],
    [6, 3, 5, 9],
    [7, 4, 8],
    [8, 5, 7, 9],
    [9, 6, 8]
]

dp = [[float('inf')] * M for _ in range(10)]

dp[0][0] = 0
queue = deque([[0, 0]])  # 今いる場所, これまでのあまり
while queue:

    node, remainder = queue.pop()
    next_remainder = (10 * remainder + node) % M
    if dp[node][next_remainder] == float('inf'):
        dp[node][next_remainder] = dp[node][remainder] + 1
        queue.appendleft([node, next_remainder])

    for to in board[node]:
        if dp[to][remainder] != float('inf'):
            continue
        dp[to][remainder] = dp[node][remainder] + 1
        queue.appendleft([to, remainder])

print(min([dp[i][R] for i in range(10)]))

感想

拡張ダイクストラ的なの、先に実装を頭で詰め切ってからのほうが結局時間かからない気がする。

2020-04-29

ABC158 E - Divisible Substring

競プロ

問題原文

E - Divisible Substring

問題要旨

0 ~ 9 からなる文字列 $S$ が与えられる。
$S$ の連続する区間を10進数と見立てたとき、それが素数 $P$ の倍数になっているようなものの通り数はいくつか。

$1 \leq |S| \leq 2 × 10^{5}$
$1 \leq P \leq 10000$
$P$ は素数

解法

これ（は？）
at274.hatenablog.com

まぁこっちの方が後出なんですが。。。
$P = 2, 5$ のときは 10 と互いに素んいならないので、別の方法で処理する必要があるので気をつける。（末尾だけ見ればいいね）

実装

from collections import Counter
N, P = map(int, input().split())
S = input()

if 10 % P == 0:
    ans = 0
    for i, s in enumerate(S, start=1):
        if int(s) % P != 0:
            continue
        ans += i
    print(ans)

else:
    X = [0]
    for i, s in enumerate(S[::-1]):
        X.append((X[-1] + pow(10, i, P) * int(s)) % P)

    C = Counter(X)
    ans = 0
    for v in C.values():
        ans += v * (v - 1) // 2
    print(ans)

感想

なんでこれ復習してなかったんですか。。。。？？？？？？？

2020-04-28

ABC164 E - Two Currencies

競プロ

問題原文

atcoder.jp

問題要旨

金貨めっちゃたくさんと銀貨 $S$ 枚を持って、 $N$ 頂点 $M$ 辺の無向連結グラフを頂点０から旅することを考える。
各辺には通行料が設定されており、銀貨 $A_i$ 枚を払わないと通れず、移動に $B_i$ 分かかる。
また、各頂点には両替所が設定されており、金貨１枚を銀貨 $C_i$ 枚に、 $D_i$ 分で両替することができる。
頂点０から各頂点にたどり着くまでの最短時間を求めよ。

$1 \leq N \leq 50$
$N - 1 \leq M \leq 100$
$0 \leq S \leq 10^{9}$
$1 \leq A \leq 2500$
$1 \leq B_i, C_i, D_i \leq 10^{9}$
二重辺、自己ループなし

解法

$A_i$ の制約が小さいので、銀貨は最大でも2500枚ぐらいあれば十分なことがわかる。これで $S$ のデカ制約を無視できる。
状態の同一視がカギで、
$dp[i\rbrack[silver\rbrack :=$ 頂点 $i$ にいて銀貨を $silvver$ 枚持っているような状態になるための最短時間
として拡張ダイクストラで解けばいい。

実装

頂点 $i$ に留まって両替だけする場合、を別でわけて書いたら見通しがよくなりそう。

import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    change_rate.append(rate)
    change_cost.append(cost)

# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    self_loop_silver = min(silver + change_rate[node], MAX_COST)
    self_loop_cost = time + change_cost[node]
    if self_loop_cost < dp[node][self_loop_silver]:
        dp[node][self_loop_silver] = self_loop_cost
        heapq.heappush(hq, (time + change_cost[node], node, self_loop_silver))

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")

銀貨コストを $-C_i$ にして、時間コストを $D_i$ 、移動先を自身とするような自己ループを各頂点に追加してもできる。
こっちのがダイクストラ部分の見通しがよい、けどちょっとだけ思考レベルが高そう。（しらんけど）

import heapq
N, M, init_silver = map(int, input().split())
MAX_COST = 2500
init_silver = min(init_silver, MAX_COST)

G = [[] for _ in range(N)]
for i in range(M):
    u, v, silver_cost, time_cost = map(int, input().split())
    u, v = u - 1, v - 1
    G[u].append([v, silver_cost, time_cost])
    G[v].append([u, silver_cost, time_cost])

change_rate, change_cost = [], []
for i in range(N):
    rate, cost = map(int, input().split())
    G[i].append([i, -rate, cost])  # これを追加！
    change_rate.append(rate)
    change_cost.append(cost)


# dp[i][silver] := 頂点iにいて銀貨をsilver枚持っているような状況を作るために必要な最小時間
dp = [[float('inf')] * (MAX_COST + 1) for _ in range(N)]
dp[0][init_silver] = 0

# 優先度付きキュー: (time, node, silver)
hq = [(0, 0, init_silver)]
while hq:
    time, node, silver = heapq.heappop(hq)

    for to, silver_cost, time_cost in G[node]:
        remain_silver = min(silver - silver_cost, MAX_COST)
        if remain_silver < 0:
            continue

        dp_next_value = time + time_cost
        if dp[to][remain_silver] <= dp_next_value:
            continue

        dp[to][remain_silver] = dp_next_value
        heapq.heappush(hq, (dp_next_value, to, remain_silver))

print(*[min(d) for d in dp[1:]], sep="\n")

感想

本番なんか無限にバグらせたけど、今見たらサクッと解けてやるせない気持ちになった。
落ち着こう、ね。

2020-04-27

ABC164 D - Multiple of 2019

競プロ

問題原文

atcoder.jp

問題要旨

1 ~ 9 からなる文字列 $S$ が与えられる。
$S$ の連続する区間を10進数と見立てたとき、それが2019の倍数になっているようなものの通り数はいくつか。

$1 \leq |S| \leq 2 × 10^{5}$

解法

2019と10は互いに素なので、 $10^{n}X$ ga 2019の倍数ならば、 $10^{n + 1}X$ も $10^{n - 1}X$ も2019の倍数。
これを踏まえた上でsample1の 1817181712114 をみてみる。
18171 は 2019の倍数であるが、これは 1×10¹² + 8×10¹¹ + 1×10¹⁰ + 7×10⁹ + 1×10⁸ =1817100000000 = 2019 × 9 × 10⁸ という構造になっている。

つまり、 $10^{i}X_i + 10^{i - 1}X_{i-1} + ... + 10^{j}X_j$ が2019の倍数であればいい。これは累積和的に求められるので、ある $10^{i}X_i + 10^{i - 1}X_{i-1} + ... + 10^{j}X_j$ について2019で割ったあまりは高速に求められることになる。

ここからはZero-Sum-Rangesで、下からみて $(0, r)$ を2019で割った余りと $(0, l - 1)$ を2019で割った余りが同じならば、 $(l, r)$ を2019で割った余りが0になる。ので、累積的にみた2019で割った余りのそれぞれの出現数を辞書等でカウントすれば答えが求められる。

実装

from collections import Counter
S = input()[::-1]
MOD = 2019

X = [0]
for i, s in enumerate(S):
    X.append((X[-1] + int(s) * pow(10, i, MOD)) % MOD)

C = Counter(X)
ans = 0
for v in C.values():
    ans += v * (v - 1) // 2
print(ans)

感想

ZeroSumRages族、頭ではわかってるつもりだけどなかなか身につかない。。。
今の実力だと一目ではわからなくて、とりあえず累積をとってみるステップを丁寧に踏まないと見抜けない。。。ううむ記事を書いたけどぎこちないというかなんというか、式変形苦手なんだなぁと。。。
あとそれはそうなんですが、 0 が混じっちゃダメなのなるほどなぁという感じです。
精進します。

2020-04-21

ABC155 E - Payment

競プロ

問題原文

atcoder.jp

問題要旨

$10^{0}, 10^{1}, 10^{2} ... 10^{10^{100}}$ の $10^{100} + 1$ 種類の紙幣がある国を考える。
この国で代金として $N$ を支払う時、 $N$ 以上の額を支払うことで、自分が出す紙幣の枚数とお釣りとしてもらう紙幣の合計枚数を最小化せよ。

$1 \leq N \leq 10^{100000}$

解法

ある桁の払い方を考えると、「その必要枚数ピッタリ払う」か「その桁では１枚も出さずに、上の桁のどこかで多く払う」の２種類があることがわかる。
あとはこの考え方を元に桁dpをすればよい。

ポイントは、「上の桁のどこかで１多く払っているなら、そこからはお釣りだけを考えばよい」ということと、「どこからでも１多く払う部分に遷移ができる」ということ、それと「代金以上払っていることが確定していても、どこかの桁でピッタリ追加で払ってもよい」ということ。

実装

簡素ォ！ $N$ を整数で受け取ると死ぬので気を付けようね（自戒）

N = input()
X = list(map(int, list(str(N))))

dp1 = [float('inf')] * (len(X) + 1)  # dp1[i] := ピッタリ払う
dp2 = [float('inf')] * (len(X) + 1)  # dp2[i] := その桁については払わない。上の桁のどこかで１多く払う。
dp1[0] = 0

for i, x in enumerate(X):
    dp1[i + 1] = min(dp1[i] + x, dp2[i] + x)
    dp2[i + 1] = min(dp1[i] + (10 - x) + 1, dp2[i] + (10 - x) - 1)

print(min(dp1[-1], dp2[-1]))

感想

前はdpよくわかんなくて、貪欲で詰めようとして。。。となって結果解ききらなかったのだけど、JOI難易度６をやってDP力を鍛えたら瞬殺できた。
ありがとうJOI。。。

2020-04-20

JOI難易度７ JJOOII 2

競プロ

問題原文

atcoder.jp

問題要旨

J, O, I からなる長さ $N$ の文字列 $S$ が与えられる。
また、 J, O, Iを $K$ 個ずつ並べた文字列を「レベル $K$ のJOI文字列」と呼ぶことにする。

「ある位置の文字を削除する」という操作を最低何回行えば $S$ をレベル $K$ のJOI文字列にできるか。
ただし、先頭もしくは末尾の削除は操作回数にカウントしない。またレベル $K$ のJOI文字列にできない場合には -1 とせよ。　　

$1 \leq N \leq 2×10^{5}$

解法

「ある箇所からレベル $K$ のJOI文字列の構築を始める」と決めた時、そこから貪欲的に構築していくのが最適。
すると、ある場所の J から始めるとして、そこから数えて $K$ 番目の J の場所、 $K$ 番目の J の場所の次の O の場所、その O から数えて $K$ 番目の O の場所。。。が欲しくなる。そしてこれは予め $O(N)$ でおけばよい。

実際に次にみるべきindexは二分探索とかで適当にやれば求められる。

実際のコストは（Jの始まりとJの終わりの間にある邪魔者の数） + (Jの終わりとOの始まりの間にある邪魔者の数) + (Oの始まりとOの終わりの間にある邪魔者の数) + (Oの終わりとIの始まりの間にある邪魔者の数) + (Iの始まりとIの終わりの間にある邪魔者の数) になる。

実装

ちょっと汚いので各indexだけ求めて最後に計算すればよかったね判定としてはI の終わりのindexが場外にはみ出さなければOKなので

まぁ読めるからいいか！w

from bisect import bisect_left
N, K = map(int, input().split())
S = input()

J_indexes = [i for i, s in enumerate(S) if s == 'J']
O_indexes = [i for i, s in enumerate(S) if s == 'O']
I_indexes = [i for i, s in enumerate(S) if s == 'I']


ans = float('inf')
for Js in range(len(J_indexes) - K + 1):
    tmp = J_indexes[Js + K - 1] - J_indexes[Js] - (K - 1)

    Os = bisect_left(O_indexes, J_indexes[Js + K - 1])
    if Os + K > len(O_indexes):
        continue
    tmp += O_indexes[Os] - J_indexes[Js + K - 1] - 1  # Jの終わりとOの最初の接続部分
    tmp += O_indexes[Os + K - 1] - O_indexes[Os] - (K - 1)

    Is = bisect_left(I_indexes, O_indexes[Os + K - 1])
    if Is + K > len(I_indexes):
        continue
    tmp += I_indexes[Is] - O_indexes[Os + K - 1] - 1  # Oの終わりとIの最初の接続部分
    tmp += I_indexes[Is + K - 1] - I_indexes[Is] - (K - 1)

    ans = min(ans, tmp)

print(ans if ans != float('inf') else - 1)

感想

難易度７埋めてくぞ〜

2020-04-20

ABC163 E - Active Infants

競プロ

問題原文

atcoder.jp

問題要旨

$N$ 人の幼児が横一列に並んでいる。左から $i$ 番目の幼児の活発度は $A_i$ である。
この幼児たちを１回だけ自由に並べ替える。
並び替える前左から $x$ 番目にいた幼児が左から $y$ 番目に移動した時、 $abs(x - y) * A_x$ のうれしさが生まれる。
幼児の嬉しさの合計値を最大化せよ。

$1 \leq N \leq 2000$

解法

幼児たちを手元に全部置いて、左 or 右に詰めていく。。。ようなことを考える。
まず、「活発度が大きい方から優先的に動かしてあげる」のは明らかに損しなさそう。ということで各幼児の最初の位置を覚えておきながら、降順ソートしておく。

あとは貪欲的にやればいいのかな〜ってなるけどどうやらサンプルみるにだめそう。　　考えられるのは「各幼児を左に詰めるか右に詰めるか」で、これはナップサック問題の「使う or 使わない」と似た雰囲気を感じるのでどうやらDPで解けそうという感覚になる。

あとはどうdpテーブルを持つかだけど、「何番目までみたか」「左に何回詰めたか」「右に何回詰めたか」という情報があれば良さそう。
また、「右に何回詰めたか」というのは「何番目までみたか」「左に何回詰めたか」からわかるので、結局dpテーブルは、

$dp[i\rbrack[j\rbrack :=$ $i$ 番目の幼児まで見て、左に $j$ 回詰めた場合のうれしさの合計の最大値

としてもてばいい。

あとは遷移。
$dp[i\rbrack[j\rbrack$ からは、左に詰める or 右に詰めるの２通りの遷移がある。

左に詰める場合
遷移先は $dp[i + 1\rbrack[j + 1\rbrack$ 。比較する値は、その幼児の最初の位置を $p$ として、 $dp[i\rbrack[j\rbrack + (p - j) × A_i$ となる。
右に詰める場合
遷移先は $dp[i + 1\rbrack[j\rbrack$ 。
比較する値は、その幼児の最初の位置を $p$ とすると、すでに右に $N - (i - j) - 1$ 回詰めたことになるので、 $dp[i\rbrack[j\rbrack + ((N - (i - j) - 1) - p ) × A_i$ となる。

実装

拾うdpのほうが書きやすいかな〜と思ったけど普通に配る方が書きやすかった。
$i$ 人目まで見た時に左に詰めうる最大人数は $j$ 人なのでそこまでしかループしてない。

N = int(input())
A = list(map(int, input().split()))
A = sorted([(a, p) for p, a in enumerate(A)], reverse=True)


# dp[i][j] := i番目の幼児まで見て、左に詰める選択をj回行った場合のうれしさの最大値
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i, (a, p) in enumerate(A):
    for j in range(i + 1):
        # 左に詰める場合
        dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + (p - j) * a)

        # 右に詰める場合
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + ((N - (i - j) - 1) - p) * a)

print(max(dp[-1]))

感想

本番は５分でテーブルを立てておきながら未来永劫拾う時の右詰めをバグらせ続けていた（えぇ。。。）
というか普通に配る方がデバッグも楽なんだなぁとしみじみ感じました。

とはいえJOIをやる前は手も足も出なかっただろうから、自力で黄diff近いdpを解けたのは素直に嬉しい〜〜〜！