ABC244のA,B,C,D,E問題を、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や拡散していただけると喜びます！
目次
ABC244 まとめ
A問題『Last Letter』
B問題『Go Straight and Turn Right』
C問題『Yamanote Line Game』
D問題『Swap Hats』
E問題『King Bombee』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC244 まとめ
全提出人数: 8010人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 11分 | 5187(5071)位 |
| 400 | ABCD---- | 1000 | 104分 | 4033(3918)位 |
| 600 | ABCD---- | 1000 | 60分 | 3205(3090)位 |
| 800 | ABCD---- | 1000 | 41分 | 2432(2317)位 |
| 1000 | ABCD---- | 1000 | 28分 | 1769(1654)位 |
| 1200 | ABCDE--- | 1500 | 94分 | 1226(1116)位 |
| 1400 | ABCDE--- | 1500 | 54分 | 828(721)位 |
| 1600 | ABCDE--- | 1500 | 27分 | 537(438)位 |
| 1800 | ABCDEF-- | 2000 | 76分 | 324(246)位 |
| 2000 | ABCDEF-- | 2000 | 48分 | 193(125)位 |
| 2200 | ABCDEFG- | 2600 | 97分 | 116(60)位 |
| 2400 | ABCDEFG- | 2600 | 74分 | 66(25)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 2863 | 98.2 % | 87.2 % | 55.4 % | 54.5 % | 1.0 % | 0.2 % | 0.0 % | 0.0 % |
| 茶 | 1216 | 99.1 % | 97.9 % | 91.0 % | 92.3 % | 8.6 % | 0.6 % | 0.1 % | 0.0 % |
| 緑 | 874 | 97.8 % | 97.2 % | 95.4 % | 96.3 % | 43.2 % | 2.4 % | 0.1 % | 0.0 % |
| 水 | 560 | 98.9 % | 98.4 % | 97.5 % | 97.7 % | 83.8 % | 31.8 % | 2.0 % | 0.2 % |
| 青 | 279 | 98.2 % | 97.8 % | 98.2 % | 98.2 % | 96.4 % | 69.9 % | 29.0 % | 1.4 % |
| 黄 | 99 | 93.9 % | 91.9 % | 92.9 % | 93.9 % | 93.9 % | 78.8 % | 48.5 % | 3.0 % |
| 橙 | 16 | 87.5 % | 87.5 % | 87.5 % | 87.5 % | 87.5 % | 81.2 % | 75.0 % | 12.5 % |
| 赤 | 5 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 40.0 % |
※表示レート、灰に初参加者は含めず
A問題『Last Letter』
問題ページ：A - Last Letter
灰コーダー正解率：98.2 %
茶コーダー正解率：99.1 %
緑コーダー正解率：97.8 %
入力
$N$ : 文字列 $S$ の長さ
$S$ : 英小文字からなる長さ $N$ の文字列
考察
本当にただ $S$ の末尾の文字を出力するだけです。S[N-1] でもいいですが、Pythonでは S[-1] と書くほうが一般的で楽です。
コード
N = int(input())
S = input()
print(S[-1])
B問題『Go Straight and Turn Right』
問題ページ：B - Go Straight and Turn Right
灰コーダー正解率：87.2 %
茶コーダー正解率：97.9 %
緑コーダー正解率：97.2 %
入力
$N$ : 文字列 $T$ の長さ
$T$ : S と R のみからなる長さ $N$ の文字列
考察
書かれているとおりにシミュレーションする問題です。
実装次第でコードの長さが大きく変わるので、スマートな書き方を心がけましょう。
実装
必要な変数・定数
x : 現在の $x$ 座標（初期値 $0$）
y : 現在の $y$ 座標（初期値 $0$）
d : 現在向いている向き表す整数（東→南→西→北がそれぞれ $0,1,2,3$に対応する 初期値 $0$）
DX = [1, 0, -1, 0] : 今の向きが $d$ のとき、Sが来たときに $x$ 座標が変化する量（東は $+1$、西は $-1$、南・北は $0$）
DY = [0, -1, 0, 1] : 今の向きが $d$ のとき、Sが来たときに $y$ 座標が変化する量（南は $-1$、北は $+1$、東・西は $0$）
R の場合
$d$ に $1$ を足します。ただし、$d=4$ は東のことですから、$d=4$ ならば $d=0$ に変更します。$4$ で割った余りを取ればこの変更ができます。
まとめると、$d$ を $(d+1)\ \%\ 4$ に変更します。この式は、$(d+1)$ を $4$ で割った余り、という意味です。
S の場合
$x$ に $\mathrm{DX}[d]$、$y$ に $\mathrm{DY}[d]$ を足します。
あらかじめ向きごとに $x,y$ 座標が変化する量をリストにしているので、場合分けは不要です。
コード
N = int(input())
T = input()
"""d=0,1,2,3 が 東・南・西・北に対応"""
DX = [1, 0, -1, 0]
DY = [0, -1, 0, 1]
x, y = 0, 0
d = 0 # 現在の向き
for t in T:
if t == "S":
x += DX[d]
y += DY[d]
if t == "R":
d = (d + 1) % 4 # 北:3の次は東:0ですから、4で割った余りをとります
print(x, y)
おまけ: -90度回転とみなす
R は、移動方向を $-90$ 度回転させる、と考えることができます。
Sが来たときの $x,y$ 座標の変化量をそれぞれ $dx, dy$とし、$dx=1, dy=0$ で初期化します。回転行列に $-90$ 度を代入することで、$dx:=dy,\ \ dy:={-dx}$ とすれば、移動方向を $-90$ 度回転させたことになるとわかります。
これをコードにすると、もう少し短く書くことができます。
N = int(input())
T = input()
x, y = 0, 0
dx, dy = 1, 0
for t in T:
if t == "S":
x += dx
y += dy
if t == "R":
dx, dy = dy, -dx # 回転行列に-90度を代入して計算するとこうなります
print(x, y)
C問題『Yamanote Line Game』
問題ページ：C - Yamanote Line Game
灰コーダー正解率：55.4 %
茶コーダー正解率：91.0 %
緑コーダー正解率：95.4 %
入力
$N$ : $2$ 人は交互に $1$ 以上 $2N+1$ 以下の整数を $1$ つずつ宣言する
- インタラクティブ問題（出力を行うたびにflushをしてください、flushについては後述します）
- 青木君が宣言できる整数が残っていない場合は、入力に $0$ が与えられ、高橋君の勝ちでゲームが終了する
考察
インタラクティブ問題です。はじめて解いた方は困惑したかもしれません。問題自体は難しくありません。
問題の考察
『まだ使っていない数字』を管理します。最初は $1$ ～ $2N+1$ の整数すべてが使えます。
高橋君の手番
『まだ使っていない数字』を、どれでもいいのでひとつ出力します。そして、『まだ使っていない数字』から削除します。
青木君の手番
青木君が『まだ使っていない数字』のうち $1$ つを標準入力に与えるので、『まだ使っていない数字』からそれを削除します。
ただし、青木君が $0$ を宣言してきた場合、ここでゲームは終了なので、プログラムを終了します。
使える数字の管理はset型が良い
制約が小さいので、『まだ使っていない数字』の管理・取り出しはだいたい何を使っても大丈夫です。
おすすめは、set型で管理する方法です。
要素 $x$ の削除 discard(x) または remove(x): $O(1)$
setに入っている任意の要素を $1$ つ 取り出して、削除する pop() : $O(1)$ （何が出てくるかはわかりません）
『まだ使われていない数字であれば、何を宣言しても良い』ので、set型の pop() で何が出てきても問題ありません。 値の削除も非常に高速です。
無限ループを使おう
$1$ ターンを『高橋君が数字を宣言してから、青木君が数字を宣言し終わるまで』と定義すると、ゲームは $N+1$ ターン目の青木君の手番で終了します。
forループで実装するならば、以下のようなイメージになります。
for _ in range(N+1):
# 高橋君の処理
# 青木君の処理
これでも良さそうですが、次のデメリットがあるので、おすすめしません。
- ループ回数を正確に計算するために無駄な時間がかかる
- ループ回数を間違えるとWAやTLEになる
代わりに、while True: の無限ループを使い、終了条件（入力が $0$）を満たしたらbreakでループを抜ける方法をおすすめします。
flushは必ずしよう
問題文に以下の注意点が赤字で書かれています。
- 出力を行うたびに標準出力をflushしてください。そうしなかった場合、ジャッジ結果が *TLE* となる可能性があります。
flushとは
コンピュータ的には、print() で標準出力に内容を表示するといった出力処理は、かなり重い処理です。そのため、できるだけ出力処理の回数を減らしたいです。
そこで、『print()で出力する内容を指示されても、それをすぐに出力せずに、一旦専用の領域（書き込みバッファ）に貯めておく。バッファに一定以上のデータが貯まるか、出力指示がされたら、貯まっている内容を一気に出力する』ということを行っています。
この出力指示のことを、flushといいます。（英語で流すという意味です。トイレの水を流すときもflushを使います）
もしflushしないとどうなるか
インタラクティブ問題では、こちらが出力した内容をジャッジが実際に受け取ってはじめて、新しい入力が返ってきます。
flushをしないと、出力内容がバッファに貯まるだけで、実際には出力されません。 出力していないのですから、ジャッジ側がこちらの出力を待つ状態から永久に進まなくなり、入力は返ってきません。 つまり、TLEになります。
flushの方法
print() のキーワード引数flush=Trueとする
デフォルトではflush=Falseです。これをTrueにします。
print(x, flush=True)
sys.stdout.flush()を呼ぶ
print()関数以外の方法で出力を行っている人は、この方法を使うことになります。
import sys
print(x)
sys.stdout.flush()
input()を呼ぶ
実は、input()は入力を受け取る前にflushを行います。この問題の場合、input()を使っていれば、気にしなくても勝手にflushされています。
print(x)
y = input()
それでも、上のいずれかの方法で明示的にflushを行ったほうが確実です。また、input()より高速な入力の sys.stdin.readline() などはflushを行わないので、自分でflushしなければいけません。
コード
def main():
N = int(input())
rem = set(range(1, 2 * N + 2)) # 使える数字のset
while True:
print(rem.pop(), flush=True) # rem から なにか1つ取り出して出力、flushはしましょう
a = int(input())
if a == 0: break # 青木君の負けなので、breakして終了します
rem.discard(a) # 青木君がaを宣言したので、rem から aを削除します
if __name__ == '__main__':
main()
D問題『Swap Hats』
問題ページ：D - Swap Hats
灰コーダー正解率：54.5 %
茶コーダー正解率：92.3 %
緑コーダー正解率：96.3 %
入力
$S_1,\ S_2,\ S_3$ : $S_i$ は高橋くん $i$ が被っている帽子の色（R,G,Bの並び替え）
$T_1,\ T_2,\ T_3$ : ちょうど $10^{18}$ 回帽子の交換を行って、 高橋くんの帽子の色を $T_1,\ T_2,\ T_3$ の並びにできるか判定する
考察
明らかに、$10^{18}$ 回操作をシミュレーションするのは不可能です。なんらかのパターンがあるものと予想されるので、とりあえず実験してみましょう。
以下、帽子の色を $1,2,3$ に置き換えて、 初期状態を $(1,2,3)$ とします。
適当にコードを書いて、$k$ 回まで交換したときにありえる帽子の並びを列挙しています。
from itertools import combinations
P = set()
P.add((1, 2, 3))
for i in range(11):
print(f"{i:>2}:", *sorted(P))
NP = set()
for p in P:
for tr0, tr1 in combinations(range(3), 2):
pl = list(p)
pl[tr0], pl[tr1] = pl[tr1], pl[tr0]
NP.add(tuple(pl))
P = NP
すると、以下の出力が得られます。
0: (1, 2, 3)
1: (1, 3, 2) (2, 1, 3) (3, 2, 1)
2: (1, 2, 3) (2, 3, 1) (3, 1, 2)
3: (1, 3, 2) (2, 1, 3) (3, 2, 1)
4: (1, 2, 3) (2, 3, 1) (3, 1, 2)
5: (1, 3, 2) (2, 1, 3) (3, 2, 1)
6: (1, 2, 3) (2, 3, 1) (3, 1, 2)
7: (1, 3, 2) (2, 1, 3) (3, 2, 1)
8: (1, 2, 3) (2, 3, 1) (3, 1, 2)
9: (1, 3, 2) (2, 1, 3) (3, 2, 1)
10: (1, 2, 3) (2, 3, 1) (3, 1, 2)
$0$ 回のときを除き、奇数回と偶数回で全く同じ並びの集合であることがわかります。
解き方
$10^{18}$ は偶数です。ということは、偶数である $2$ 回の交換でできる並びは、$10^{18}$ 回でもできます。反対に、奇数である $1$ 回 の交換でできる並びは、$10^{18}$ 回ではできません。
『$2$ 回でできるならYes』、『$1$ 回でできるならNo』、のどちらでも正解できますが、楽なのは『 $1$ 回でできるならNo』です。
初期状態で、$S_i\ne{T_i}$、つまり$S_i$ と $T_i$ が異なる高橋くんの人数は、$0$ 人、$2$ 人、$3$ 人のいずれかです。
このうち、不一致が $2$ 人の場合のみ、その $2$ 人を選んで帽子を交換することで、$S$ と $T$ の並びを完全に一致させることができます。
つまり、『$S_i\ne{T_i}$ の数を数えて、$2$ 以外なら Yes、$2$ なら No』 で正解になります。
備考
$S$ を RGB としたとき、不一致の人数が $0,\ 2\ ,3$ 人になる $T$ をそれぞれ列挙すると
$0$ : RGB
$2$ : GRB, BGR, RBG
$3$ : GBR, BRG
になります。
$0,\ 3$ 人の RGB, GBR, BRG なら Yes で、$2$ 人の GRB, BGR, RBG なら No ということです。
コード
def solve():
S = input()
T = input()
x = sum(s != t for s, t in zip(S, T))
return x != 2
print("Yes" if solve() else "No")
参考情報
（筆者が数学に弱く、また簡単に説明するため、不正確な可能性もありますが、ご了承ください）
順列のいくつかの要素を選んで、別の位置に入れ替える操作のことを、『置換』といいます。置換のうちとくに、$2$ つの要素を選んで互いに入れ替える操作のことを『互換』と言います。
そして、「偶数回の互換の繰り返しで表すことができる置換」のことを『偶置換』といい、「奇数回の互換の繰り返しで表すことができる置換」のことを『奇置換』と言います。
各置換は、『偶置換』か『奇置換』のいずれか一方のみに属します。 また、全ての置換のうち、ちょうど半分が『偶置換』、残り半分が『奇置換』です。
$2$ 人を選んで帽子を入れ替える操作は『互換』そのものですから、この問題は「$T$ が $S$ の偶置換であるかを判定する問題」といえます。
なお、順列の置換は、転倒数が偶数ならば『偶置換』であり、奇数ならば『奇置換』であることが知られています。
転倒数はBinary Indexed Treeを使って$O(N\log{N})$ で計算できますから、人数が $3$ 人ではなく、$10$ 万人 だとしても判定できます。
詳しく知りたい方は、線形代数や、群論の最初の方を勉強すると良いです。というか私も勉強中です。
E問題『King Bombee』
問題ページ：E - King Bombee
灰コーダー正解率：1.0 %
茶コーダー正解率：8.6 %
緑コーダー正解率：43.2 %
入力
$N,M$ : $N$ 頂点 $M$ 辺の単純無向グラフが与えられる
$U_i,V_i$ : $i$ 番目の辺は $U_i$ と $V_i$ を互いにつなぐ
$K$: 後述の条件を満たす、長さ$K+1$の数列 $A=(A_0,A_1,\dots,A_K)$ の数を数える
$S$ : $A_0=S$
$T$ : $A_K=T$
$X$ : 数列 $A$ に、$X$ は偶数回出現する（$X\ne{S},\ X\ne{T}$）
- 答えは $998244353$ で割った余りを答える
考察
問題文を要約すると
頂点 $S$ からはじめて、グラフの辺をちょうど $K$ 回 使って移動したとき、頂点 $T$ にいて、しかも $X$ を訪れた回数が偶数回であるような移動方法は何通りか？
です。
動的計画法で解きます。添字の情報として必要になるのは
- 現在の移動回数
- 現在いる頂点
- 今までXを通った回数が偶数回か奇数回か
です。
dp配列の定義
$\mathrm{dp0}[i][j]$ : 現在 $i$ 回移動して頂点 $j$ にいて、$X$ を訪れた回数が偶数回である移動経路の数（を $998244353$ で割った余り）
$\mathrm{dp1}[i][j]$ : 現在 $i$ 回移動して頂点 $j$ にいて、$X$ を訪れた回数が奇数回である移動経路の数（を $998244353$ で割った余り）
dp配列の初期値と答え
初期値 : $\mathrm{dp0}[0][S]=1$, それ以外は $0$
答え : $\mathrm{dp0}[K][T]$
遷移
（たぶんコードを見たほうがはやいです）
$K$ 回移動をします。$i$ 回目の移動では、各頂点 $j$ について、$j$ からいける頂点すべてに対して、$X$ を訪れた回数の偶奇が同じdp配列に足します。
ただし、頂点 $X$ に移動する場合だけ、遇奇を入れ替えることに注意してください。
計算量は $O(K(N+M))$ です。辺の数は $2M$ 本しかないので、$O(KN^2)$ ではありません。
コード
PyPyで出してください。（たぶんdp配列を1次元にして使い回せば通ります）
MOD = 998244353
def main():
N, M, K, S, T, X = map(int, input().split())
G = [[] for _ in range(N + 1)]
for _ in range(M):
a, b = map(int, input().split())
G[a].append(b) # a <-> b
G[b].append(a)
dp0 = [[0] * (N + 1) for _ in range(K + 1)]
dp1 = [[0] * (N + 1) for _ in range(K + 1)]
dp0[0][S] = 1 # 0回移動して今S
for i in range(K):
for u in range(1, N + 1):
for v in G[u]:
if v == X: # X を通ると、Xを通った回数の遇奇が入れ替わります
dp0[i + 1][v] += dp1[i][u]
dp1[i + 1][v] += dp0[i][u]
else:
dp0[i + 1][v] += dp0[i][u]
dp1[i + 1][v] += dp1[i][u]
dp0[i + 1][v] %= MOD
dp1[i + 1][v] %= MOD
print(dp0[K][T])
if __name__ == '__main__':
main()