最近土日夜に予定があることが多く、なかなかコンテストに参加できておらず、昨日久々に参加したので記録を書いていきます。
ABC135 A – Harmony
相違なる整数 \(A, B\) があります。
https://atcoder.jp/contests/abc135/tasks/abc135_a
\(|A−K| = |B−K|\) となるような整数 \(K\) を出力してください。
そのような整数が存在しなければ、代わりに"IMPOSSIBLE"を出力してください。
\(|A – K| = |B – K|\) を変形すると、 \(A – K = B – K\) or \(A – K = K – B\) となり、 \(A = B\) or \(K = \frac{A + B}{2} \) といえます。
今回は、問題文に 相異なる整数 と書いてあるので、 \(K = \frac{A + B}{2}\) であり、これが整数かどうかで "IMPOSSIBLE" かどうかを判定すれば OK ですね。
回答案
Python3 で 22 ms で AC。
A, B = map(int, input().split())
if (A + B) % 2 == 0:
print((A + B) // 2)
else:
print("IMPOSSIBLE")ABC135 B – 0 or 1 Swap
\(\{1, 2, …, N\}\) を並び替えた数列 \(p = \{p_1, p_2, …, p_N\}\) があります。
https://atcoder.jp/contests/abc135/tasks/abc135_b
あなたは一度だけ、整数 \(i, j (1 \leq i < j \leq N)\) を選んで \(p_i\) と \(p_j\) を入れ替える操作を行うことができます。操作を行わないことも可能です。
\(p\) を昇順にすることができるなら"YES"を、できないならば"NO"を出力してください。
\(p\) の index と \(p\) の値を比較して、異なるものをカウントしたときの個数が 2 以下になるときに昇順に出来ます。
回答案
Python3 で 17 ms で AC。
N = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(N):
if i + 1 == p[i]:
cnt += 1
if cnt >= N - 2:
print("YES")
else:
print("NO")ABC135 C – City Savers
\(N + 1\) 個の街があり、 \(i\) 番目の街は \(A_i\) 体のモンスターに襲われています。
https://atcoder.jp/contests/abc135/tasks/abc135_c
\(N\) 人の勇者が居て、\(i\) 番目の勇者は \(i\) 番目または \(i + 1\) 番目の街を襲っているモンスターを合計で \(B_i\) 体まで倒すことができます。
\(N\) 人の勇者がうまく協力することで、合計して最大で何体のモンスターを倒せるでしょうか。
A[0] から順番に見ていきましょう。 B[0] が A[0] を上回っている場合、余剰分が A[1] だけに作用します。つまり、 A[2] 以降には作用しないことに注意する必要があります。
そこで、回答では余剰分 surplus を設定し毎回更新していくことにしています。無駄のないようにモンスターを倒していく必要があるので、 A[i] に先に作用するのは B[i] でなく surplus にする必要があります。
回答案
Python3 で 147 ms で AC。
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans, surplus = 0, 0
for i in range(N):
tmp = min(A[i], surplus)
ans += tmp
A[i] -= tmp
if B[i] > A[i]:
ans += A[i]
surplus = B[i] - A[i]
else:
ans += B[i]
surplus = 0
tmp = min(A[N], surplus)
ans += tmp
print(ans)ABC135 D – Digits Parade
文字列 \(S\) が与えられます。\(S\) の各文字は、数字 (
https://atcoder.jp/contests/abc135/tasks/abc135_d"0"～"9") か"?"です。"?"を数字に置き換えてできる整数のうち、\(13\) で割って \(5\) あまる数は何通りあるでしょうか？ただし、頭文字が \(0\) である場合も整数とみなすものとします。
答えは非常に大きくなる可能性があるため、\(10^9 + 7\) で割ったあまりを答えてください。
\(S\) の長さが \(10^5\) なので、全探索しようとすると \(O(10^{10^5})\) となって出来ません。ということで他の方法を考えることになります。。。
剰余の計算を以下のように桁ごとに分割して考えることができることに着目すると、 DP で行けそう。
"??2??5" を 13 で割った余り
= "?"*10^5 + "?"*10^4 + 2*10^3 + "?"*10^2 + "?"*10 + 5 を 13 で割った余り
= ("?"*10^5 を 13 で割った余り) + ("?"*10^4 を 13 で割った余り) + (2*10^3 を 13 で割った余り) + ("?"*10^2 を 13 で割った余り) + ("?"*10 を 13 で割った余り) + (5 を 13 で割った余り)すなわち次のように DP テーブルを設定することでうまくいくことが分かります。
dp[i][j]: $S$ の後ろから $i$ 桁を 13 で割ったあまりが $j$ となるようなものの個数- 求めるもの:
dp[len(S)][S]($S$ を 13 で割ったあまりが $5$ となるようなものの個数)
あとは状態間の遷移を考えてあげれば良いですね。参考までに "??2??5" の場合の遷移を表として書いておきます。
参考: ある数 X = “??2??5” を下から見ていったときの 13 で割った余りの遷移
| X | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| ?5 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| ??5 | 8 | 7 | 8 | 8 | 7 | 8 | 8 | 8 | 7 | 8 | 8 | 7 | 8 |
| 2??5 | 8 | 8 | 7 | 8 | 8 | 8 | 7 | 8 | 8 | 7 | 8 | 8 | 7 |
| ?2??5 | 78 | 76 | 76 | 79 | 76 | 76 | 79 | 76 | 76 | 78 | 77 | 76 | 77 |
| ??2??5 | 771 | 768 | 768 | 772 | 768 | 768 | 771 | 769 | 768 | 770 | 770 | 768 | 769 |
回答案
PyPy3 で 721 ms で AC。（Python3 では通せませんでした…）
INF = 10 ** 9 + 7
S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1
for i in range(len(S)):
x = S[-(i + 1)]
if x == "?":
for k in range(10):
for j in range(13):
dp[i + 1][(mul * k + j) % 13] += dp[i][j]
dp[i + 1][(mul * k + j) % 13] %= INF
else:
k = int(x)
for j in range(13):
dp[i + 1][(mul * k + j) % 13] += dp[i][j]
dp[i + 1][(mul * k + j) % 13] %= INF
mul = mul * 10 % 13 # 計算量削減のためここで13で割っている
print(dp[len(S)][5])