ABC237のA,B,C,D,E,F問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！
目次
ABC237 まとめ
A問題『Not Overflow』
B問題『Matrix Transposition』
C問題『kasaka』
D問題『LR insertion』
E問題『Skiing』
F問題『|LIS| = 3』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC237 まとめ
全提出人数: 9245人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 54分 | 6146(5902)位 |
| 400 | ABC----- | 600 | 112分 | 4924(4680)位 |
| 600 | ABC----- | 600 | 41分 | 4007(3765)位 |
| 800 | ABCD---- | 1000 | 86分 | 3100(2866)位 |
| 1000 | ABCD---- | 1000 | 50分 | 2294(2060)位 |
| 1200 | ABCDE--- | 1500 | 148分 | 1635(1411)位 |
| 1400 | ABCDE--- | 1500 | 77分 | 1136(917)位 |
| 1600 | ABCDE--- | 1500 | 52分 | 779(567)位 |
| 1800 | ABCDEF-- | 2000 | 124分 | 513(322)位 |
| 2000 | ABCDEF-- | 2000 | 66分 | 338(170)位 |
| 2200 | ABCDEFG- | 2600 | 124分 | 216(83)位 |
| 2400 | ABCDEFG- | 2600 | 87分 | 144(38)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3243 | 91.0 % | 82.4 % | 42.2 % | 18.9 % | 2.2 % | 0.3 % | 0.1 % | 0.0 % |
| 茶 | 1388 | 98.3 % | 97.0 % | 85.3 % | 65.0 % | 9.6 % | 0.3 % | 0.3 % | 0.0 % |
| 緑 | 1053 | 97.4 % | 96.4 % | 93.3 % | 89.9 % | 37.9 % | 2.0 % | 1.1 % | 0.1 % |
| 水 | 665 | 98.0 % | 97.6 % | 96.2 % | 96.1 % | 72.3 % | 13.5 % | 5.3 % | 0.0 % |
| 青 | 372 | 98.9 % | 97.6 % | 97.6 % | 97.3 % | 83.1 % | 51.1 % | 22.3 % | 0.3 % |
| 黄 | 182 | 90.7 % | 89.0 % | 89.0 % | 90.1 % | 84.6 % | 72.0 % | 58.8 % | 8.8 % |
| 橙 | 41 | 97.6 % | 97.6 % | 97.6 % | 97.6 % | 97.6 % | 92.7 % | 82.9 % | 31.7 % |
| 赤 | 24 | 91.7 % | 91.7 % | 95.8 % | 87.5 % | 91.7 % | 91.7 % | 91.7 % | 54.2 % |
※表示レート、灰に初参加者は含めず
A問題『Not Overflow』
問題ページ：A - Not Overflow
灰コーダー正解率：91.0 %
茶コーダー正解率：98.3 %
緑コーダー正解率：97.4 %
入力
$N$ : 整数（$-2^{63}\le{N}\lt{2^{63}}$）
考察
$N$ が $-2^{31}$ 以上 かつ、$2^{31}$ 未満であるか判定すればいいです。境界値（以下か未満か）のミスは非常によくあるので、よく問題文を読んで間違えないように注意してください。
一般的な言語では64bit整数型を使用しないとオーバーフローしますが、Pythonは多倍長整数を使用しているため、考える必要はありません。
コード
C = 2 ** 31
N = int(input())
print("Yes" if -C <= N < C else "No") # 以上、未満です
B問題『Matrix Transposition』
問題ページ：B - Matrix Transposition
灰コーダー正解率：82.4 %
茶コーダー正解率：97.0 %
緑コーダー正解率：96.4 %
入力
$H,W$ : $H$ 行 $W$ 列の行列が与えられる
$A_{i,j}$ : $A$ の $i$ 行 $j$ 列目の要素
考察
$A$ を二次元リストで受け取ります。Pythonでは、At = list(zip(*A)) と書くと転置行列になるので、これを出力すればいいです。
コード
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
At = list(zip(*A))
for r in At:
print(*r)
NumPy
全く使う必要はありませんが、NumPyを使う場合はこうなります。（AtCoderのPyPyにはNumPyが入っていないので、Pythonで提出する必要があります）
import numpy as np
H, W = map(int, input().split())
A = np.array([list(map(int, input().split())) for _ in range(H)])
At = np.transpose(A)
for r in At:
print(*r)
C問題『kasaka』
問題ページ：C - kasaka
灰コーダー正解率：42.2 %
茶コーダー正解率：85.3 %
緑コーダー正解率：93.3 %
入力
$S$ : 英小文字からなる文字列
考察
回文とは逆から読んでも同じ文字列のことですから、自分自身を反転したものと一致すれば回文です。回文判定は S == S[::-1] で簡単にできます。
回文になるとすれば、少なくとも『$S$ を先頭から見て a 以外の文字が出るまで a が連続で出てくる文字数』『$S$ を末尾から見て a 以外の文字が出るまで a が連続で出てくる文字数』が一致している必要があります。この条件を満たしていても回文とは限りませんが、満たしていなければ回文にはなりません。
先頭・末尾の a の連続数が合うように、先頭にaを付け加えて回文判定を行えばいいです。ただし、a は先頭に付け加えることしかできないので、先頭の連続数のほうが多い場合は回文にはできません。
例1
aabaaa は、先頭から見て a が $2$ 文字、末尾から見て a が $3$ 文字連続で出てきます。先頭にaを $1$ 文字付け加えて、aaabaaa にすると回文になります。
例2
abcaa は先頭から見て a が $1$ 文字、末尾から見て a が $2$ 文字連続で出てきます。先頭にa を $1$ 文字付け加えて aabcaa にしても回文にはなりません。
例3
aaaaba は先頭から見て a が $4$ 文字、末尾から見て a が $1$ 文字連続で出てきます。a は先頭に付け加えることしかできないので、回文にはできません。
解法
この問題は以下のアルゴリズムで解けます。
-
aが先頭・末尾それぞれ何文字連続で出てくるか調べる - 先頭・末尾の
aの文字数が合うように、先頭にaを付け加えて判定する（先頭のほうが多い場合は不可能）
コード
def judge():
S = input()
l = len(S) - len(S.lstrip('a')) # 先頭の連続数
r = len(S) - len(S.rstrip('a')) # 末尾の連続数
if l > r: return False
T = "a" * (r - l) + S
return T == T[::-1]
print("Yes" if judge() else "No")
D問題『LR insertion』
問題ページ：D - LR insertion
灰コーダー正解率：18.9 %
茶コーダー正解率：65.0 %
緑コーダー正解率：89.9 %
入力
$N$ : 操作を行う回数
$s_i$ : $i$ 回目の操作では $s_i$ がLかRのどちらかに応じて、 $i$ を $i-1$ のすぐ左かすぐ右に挿入する
考察
$A={N}$ から操作を逆向きに行い、$s_i$ が L なら $i-1$ を $A$ の右端に追加し、R なら $A$ の左端に追加することで簡単に解けます。
なぜこれでうまくいくかを考えます。$s_i$ が L のとき、$i$ 以上の要素はすべて $i-1$ より左に追加されます。$i$ 以上の要素をすべて数列に追加してから、$i-1$ を $A$ の右端に追加すれば正しい位置に $i-1$ を追加できます。$s_i$ が R の場合も同じです。
先頭から見る方法や、双方向連結リストを使う解法もありますが、省略します。
実装
数列の左端と右端両方向の挿入が必要なので、両端キューのdeque を使います。
コード
from collections import deque
def main():
N = int(input())
S = input()
ans = deque((N,))
for i in reversed(range(N)):
if S[i] == "L":
ans.append(i)
else:
ans.appendleft(i)
print(*ans)
main()
E問題『Skiing』
問題ページ：E - Skiing
灰コーダー正解率：2.2 %
茶コーダー正解率：9.6 %
緑コーダー正解率：37.9 %
入力
$N,M$ : 広場の数は $N$ 個で、坂の数は $M$ 本
$H_i$ : 広場 $i$ の標高
$U_i,V_i$ : $i$ 本目の坂は 広場 $U_i$ と $V_i$ を結ぶ
どの頂点も互いに坂を使ってたどり着ける（グラフは連結）
考察
この問題をわかりやすくいうと、$X$ と $Y$ の標高差の絶対値 $|H_X-H_Y|$ を使って
- 広場 $X$ から今より標高が高い広場 $Y$ に坂を使って移動すると、楽しさが $2|H_X-H_Y|$ 減る
- 広場 $X$ から今より標高が低い広場 $Y$ に坂を使って移動すると楽しさが $|H_X-H_Y|$ 増える
- 頂点 $1$ から 楽しさの初期値 $0$ ではじめたときの、楽しさを最大化せよ
という問題です。
最短経路問題とみなす
楽しさの正負を反転して、距離として『楽しさの $-1$ 倍』を考え、辺を以下のように貼ったグラフを考えます。
- 自分より高い広場には、コスト $2|H_X-H_Y|$ の辺を貼る
- 自分より低い広場には、コスト $-|H_X-H_Y|$ の辺を貼る
このグラフ上で、頂点 $1$ からはじめた全頂点対最短経路問題を解き、距離（楽しさの $-1$ 倍）が最小の頂点の値を $-1$ 倍すると答えになります。
自分より低い広場に対してはコストが負の辺を貼ることになりますが、負閉路は絶対に出現しないことに注意してください。（同じ場所に戻ってくることはできますが、楽しさの減少量を増加量が上回るので、『楽しさの $-1$ 倍』である距離は減少しません）
負辺が邪魔
どのアルゴリズムを使えば解けるか考えてみましょう。
ダイクストラ法 : 負辺がある場合、$O(2^N)$ になるケースを作成可能なため不可（コンテスト中はACできてしまいましたが、after contestのテストケースでTLEになります）
ベルマン・フォード法 : 計算量が $O(NM)$ のため、不可
どちらのアルゴリズムも使えないので、このままのグラフで最短経路問題を解くのは難しいです。
ポテンシャルを考える
なぜ負のコストが出てきたかというと、距離として『楽しさの $-1$ 倍』を使ったからです。『楽しさの $-1$ 倍』は坂を下ると減少します。絶対に減少することがない、別の値を距離として使うことを考えます。
ここで、「楽しさが増える量は、標高が減った量と同じである」ことに着目します。言い換えると、坂を下っても『楽しさ+標高』は変化しません。そこで、距離として『楽しさ+標高』の $-1$ 倍を使った以下のグラフを考えます。
- 自分より高い広場には、コスト $|H_X-H_Y|$ の辺を貼る（楽しさが $2|H_X-H_Y|$ 減って、標高が $|H_X-H_Y|$ 増えるため、差し引き $|H_X-H_Y|$ です）
- 自分より低い広場には、コスト $0$ の辺を貼る
このグラフ上で、頂点 $1$ の距離の初期値を $-H_1$ として、頂点 $1$ からダイクストラ法を行います。求めた頂点 $1$ から 頂点 $i$ への最短距離を $dist_i$ とすると、『頂点 $i$ で終わるときの最大の楽しさ』は $- dist_{i} - H_i$ で求められるので、全頂点に対して調べて、最大の値が答えになります。
（$楽しさ = 『楽しさ+標高』-標高=-『(楽しさ+標高)の-1 倍』 - 標高$ です）
コード
from heapq import heappop, heappush
INF = 1 << 62 - 1
def main():
def dijkstra(G, start):
N = len(G)
dist = [INF] * N
dist[start] = -H[0]
pq = [(-H[0], start)]
while pq:
cost, u = heappop(pq)
if dist[u] < cost:
continue
for v, d in G[u]:
new_cost = cost + d
if dist[v] > new_cost:
dist[v] = new_cost
heappush(pq, (new_cost, v))
return dist
N, M = map(int, input().split())
H = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
a, b = a - 1, b - 1
G[a].append((b, max(0, H[b] - H[a])))
G[b].append((a, max(0, H[a] - H[b])))
dist = dijkstra(G, 0)
ans = max(-dist[i] - H[i] for i in range(N))
print(ans)
main()
F問題『|LIS| = 3』
問題ページ：F - |LIS| = 3
灰コーダー正解率：0.3 %
茶コーダー正解率：0.3 %
緑コーダー正解率：2.0 %
入力
$N$ : 数列の長さ
$M$ : 数列の各項の値は $1$ 以上 $M$ 以下
考察
長さ $3$ に制限したLISの配列を状態として、動的計画法を行います。$i$ 番目まで決めてLIS配列が $(a,b,c)$ である数列の $i+1$ 文字目を $x$ にしたとき、LIS配列がどうなるかは、$i$ によらず一意に決まり、また更新されるのは $(a,b,c)$ のいずれか一箇所のみです。
状態数は $O(NM^3)$ です。遷移は時間計算量 $O(1)$ でできるので、計算量 $O(NM^3)$ でこの問題を解くことができました。
コード
PyPyで提出してください。
MOD = 998244353
def main():
N, M = map(int, input().split())
prev = [[[0] * (M + 1) for _ in range(M + 1)] for _ in range(M + 1)]
prev[M][M][M] = 1
for _ in range(N):
dp = [[[0] * (M + 1) for _ in range(M + 1)] for _ in range(M + 1)]
for x in range(M):
for a in range(M + 1):
for b in range(M + 1):
for c in range(M + 1):
# LIS配列としてありえないものも含まれますが、問題ありません
p = prev[a][b][c]
if x <= a:
dp[x][b][c] += p
dp[x][b][c] %= MOD
elif x <= b:
dp[a][x][c] += p
dp[a][x][c] %= MOD
elif x <= c:
dp[a][b][x] += p
dp[a][b][x] %= MOD
prev = dp
ans = 0
for a in range(M):
for b in range(a + 1, M):
for c in range(b + 1, M):
ans += prev[a][b][c]
ans %= MOD
print(ans)
main()