【AtCoder解説】PythonでABC243のA,B,C,D問題を制する！

ABC243のA,B,C,D問題を、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や拡散していただけると喜びます！

目次

ABC243 まとめ
A問題『Shampoo』
B問題『Hit and Blow』
C問題『Collision 2』
D問題『Moves on Binary Tree』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

• レート別問題正解率
• パフォーマンス目安
• 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC243 まとめ

全提出人数: 9955人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB------	300	32分	6562(6316)位
400	AB------	300	14分	5341(5095)位
600	ABC-----	600	81分	4336(4102)位
800	ABC-----	600	24分	3330(3104)位
1000	ABCD----	1000	77分	2429(2213)位
1200	ABCD----	1000	48分	1694(1483)位
1400	ABCD----	1000	31分	1174(965)位
1600	ABCDE---	1500	101分	778(593)位
1800	ABCDE---	1500	65分	513(342)位
2000	ABCD--G-	1600	49分	320(175)位
2200	ABCDE-G-	2100	101分	193(85)位
2400	ABCDE-G-	2100	64分	129(40)位

色別の正解率

色	人数	A	B	C	D	E	F	G	Ex
灰	3421	94.2 %	90.6 %	27.8 %	9.5 %	0.5 %	0.0 %	0.1 %	0.0 %
茶	1455	98.1 %	97.2 %	78.9 %	42.3 %	3.4 %	0.0 %	0.3 %	0.0 %
緑	1185	97.8 %	97.5 %	93.7 %	79.8 %	11.2 %	1.3 %	1.7 %	0.0 %
水	712	97.0 %	96.6 %	95.4 %	93.7 %	32.9 %	4.8 %	6.7 %	0.0 %
青	371	97.6 %	97.6 %	97.8 %	97.3 %	56.3 %	23.7 %	28.8 %	0.0 %
黄	200	81.0 %	81.5 %	81.5 %	82.5 %	59.5 %	46.0 %	59.0 %	0.0 %
橙	34	85.3 %	85.3 %	85.3 %	85.3 %	82.3 %	79.4 %	88.2 %	0.0 %
赤	18	88.9 %	88.9 %	94.4 %	94.4 %	94.4 %	94.4 %	88.9 %	5.6 %

※表示レート、灰に初参加者は含めず

A問題『Shampoo』

問題ページ：A - Shampoo
灰コーダー正解率：94.2 %
茶コーダー正解率：98.1 %
緑コーダー正解率：97.8 %

入力

$V$ : 最初はシャンプーが $V$ 残っている
$A,B,C$ : 父・母・高橋が使うシャンプーの量

考察

シミュレート解法

forループで父・母・高橋くんの順にシャンプーを使っていって、シャンプーが不足するのが誰か求めればいいです。

$V,A,B,C\le{10^5}$ のため、実行時間制限 $2$ 秒以内で計算することができます。

（もし $V$ の制約が大きい場合、例えば $V=10^{18}$、$A=B=C=1$ だと、$1$ 秒に $10^{10}$ 回処理できるとしても、数十分処理に時間がかかります）

算数解法

一日に消費されるシャンプーの量は、$A+B+C$ です。以後 $S=A+B+C$ とします。

その日のはじまり（父がシャンプーを使う前）に残っているシャンプーの量が $S$ 以上であれば、その日にシャンプーが不足することはありません。逆に、$S$ 未満であれば、その日にシャンプーが不足します。

シャンプーの残りが $S$ 未満になる日（誰かが使うときにシャンプーが足りなくなる日）のはじめに残っているシャンプーの量は、$V$ を $S$ で割ったあまりで求められます。

あとは、if文などで誰が使うときにシャンプーが足りなくなるか求めればいいです。

この方法であれば、$V\le{10^{18}}$ のように制約が大きくても対応できます。

補足

$q,\ r$を非負整数、$0\le{q}$、$0\le{r}\lt{S}$とすると、$V=qS+r$ と表すことができます。

数式で書くと難しそうですが、これは小学校中学年でやった『余りの出る割り算』です。つまり、$q$ は $V$ を $S$ で割った商、$r$ は 余りです。

この問題では不要ですが、$q$ 日目まではシャンプーは不足せず、$q+1$ 日目にシャンプーが不足する、という情報も得られます。

コード

シミュレート

def solve():
    pat = "FMT"  # 父、母、高橋の順に使います
    V, *L = map(int, input().split())  # L == [A, B, C] のリストです
    i = 0
    while True:
        V -= L[i % 3]  # i を 3 で割ったあまりで、父、母、高橋の誰が使うかわかります
        if V < 0:  # 残りがマイナスならば足りません（ちょうどはセーフです）
            return pat[i % 3]
        i += 1


print(solve())

算数

def solve():
    V, f, m, t = map(int, input().split())  # 変数名を工夫すると良いこともあります（変数名被りに注意）
    r = V % (f + m + t)
    if r < f:
        return "F"
    if r < f + m:
        return "M"
    return "T"


print(solve())

B問題『Hit and Blow』

問題ページ：B - Hit and Blow
灰コーダー正解率：90.6 %
茶コーダー正解率：97.2 %
緑コーダー正解率：97.5 %

入力

$N$ : 数列 $A,\ B$ の長さ
$A_i,\ B_i$ : それぞれ $A$ および $B$ の $i$ 番目の要素の値

• $N\le{1000}$
• $1\le{A_i,\ B_i}\le{10^9}$
• $A$ に重複する要素はない
• $B$ に重複する要素はない

考察

二重ループで全探索

$N=1000$ なので、$O(N^2)$ の二重ループですべての組み合わせを調べることができます。

set型で演算

こちら方法は $O(N)$ で解けるので、$N=200000$ でも対応できます。

まず、問題文の $1.$ の個数を数えます。これは単純なforループや、内包表記のsumで $O(N)$ で求められます。

次に、位置を気にせずに $A$ と $B$ で共通する要素がいくつあるか数えます。これは、$A$ と $B$ を set型に変換し、len(A & B) で $A$ と $B$ の共通する要素がいくつあるか数えればいいです。

最後に、$2.$ の個数を求めます。今求めた位置を気にせずに値が一致する要素の数から、$1.$ の位置も値も一致する要素の数を引けばいいです。

コード

二重ループで全探索

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans1 = 0
ans2 = 0

# rangeでA[i], B[j]としてもいいですが、enumerateを使ったほうが楽です
for i, a in enumerate(A):
    for j, b in enumerate(B):
        if a == b:  # a == b でなければ興味はありません
            if i == j:  # i == j かどうかで分岐します
                ans1 += 1
            else:
                ans2 += 1

print(ans1)
print(ans2)

set型を使う

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans1 = sum(a == b for a, b in zip(A, B))
ans2 = len(set(A) & set(B)) - ans1

print(ans1)
print(ans2)

C問題『Collision 2』

問題ページ：C - Collision 2
灰コーダー正解率：27.8 %
茶コーダー正解率：78.9 %
緑コーダー正解率：93.7 %

入力

$N$ : 人の数
$X_i,\ Y_i$ : 人 $i$ の初期座標
$S_i$ : 人 $i$ は $S_i$ が L ならば 左（ $x$ 軸の負の向き）に動き続け、 R ならば 右（$y$ 軸の正の向き） に動き続ける（すべての人は同じ速度で歩く）

考察

制約が大きいので、シミュレーションではTLEになります。

適当に選んだ 人 $i$ と 人 $j$ が衝突する条件を考えます。

1. 人 $i$ と 人 $j$ の $y$ 座標が同じ（すべての人は $x$ 軸方向・左右にしか歩かないので、$y$ 座標・上下の軸がズレている人同士は絶対に衝突しない）

2. 人 $i$ と 人 $j$ の歩く向きが異なる（すべての人が同じ速度で歩くため。同じ場合衝突しないことは、入力例 $2$ で説明されています）

3. 人 $i$ が右向き、人 $j$ が左向きに歩いているならば、人 $i$ は人 $j$ より左側にいる、すなわち $X_i\lt{X_j}$

3については、なんとなくイメージできると思いますが、$2$ 人の移動方向を矢印で表すと

→ ← : 衝突する（衝突するまで距離が縮まり続けるので、いつかは衝突する）
← → : 衝突しない（開始から距離が離れ続けるので、永遠に衝突しない）**

からです。

人 $i$ と 人 $j$ の組をすべて試せばよさそうですが、計算量が $O(N^2)$ です。$N\le{2\times{10^5}}$ ですから、TLEになります。

y座標ごとに一次元の小問題を解く

さきほど述べたように、$y$ 座標が違う人同士は絶対に衝突しません。ですから、同じ $y$ 座標の人をグループでまとめて、衝突する人の組があるか判定すればいいです。つまり、$y$ 座標ごとに $1$ 次元 の小問題を高速に解ければいいです。

高速に解く方法を考えます。その $y$ 座標に誰もいないか、同じ向きに歩く人しかいない場合は衝突が発生しないので、考えません。

先に結論を述べると

• 一番左にいる右向きに歩く人
• 一番右にいる左向きに歩く人

が衝突するか判定すればいいです。

ある $y$ 座標の右向きに歩く人のうち、一番衝突する回数が多い人を考えます。（衝突したあと人を通り抜けることとします）それは最初に一番左にいる人です。逆向きも成り立ちます。

一番衝突する回数が多い人の衝突回数が $0$ 回であれば、他のどの人も衝突回数は $0$ 回です。逆に、適当な人の組をとってきて衝突しなかったとしても、一番衝突する回数が多い人は衝突する可能性があります。

実装

必要な情報は、各 $y$ 座標ごとに

• 一番左にいる右向きに歩く人、 $\mathrm{min}(X_i)$（ただし $S_i$ = R を満たす）
• 一番右にいる左向きに歩く人、 $\mathrm{max}(X_i)$（ただし $S_i$ = L を満たす）

$y$ の制約が大きいので、長さ $10^{18}$ ほどのリストを作ることになりますが、これは巨大すぎて不可能です。

そのため、dictを使うといいです。さらに、defaultdictを使って絶対に衝突が起こらないような初期値を設定しておくと、dictに値が存在するかいちいち判定しなくてよくなるので楽です。

コード

from collections import defaultdict

INF = (1 << 62) - 1


def solve():
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]
    S = input()
    L_max = defaultdict(lambda: -INF)
    R_min = defaultdict(lambda: INF)

    for s, (x, y) in zip(S, XY):
        if s == "L":
            L_max[y] = max(L_max[y], x)
        else:
            R_min[y] = min(R_min[y], x)

    for y in L_max.keys():
        if R_min[y] < L_max[y]:
            return True
    return False


print("Yes" if solve() else "No")

D問題『Moves on Binary Tree』

問題ページ：D - Moves on Binary Tree
灰コーダー正解率：9.5 %
茶コーダー正解率：42.3 %
緑コーダー正解率：79.8 %

入力

$N$ : $S$ の長さ
$X$ : 高橋くんが最初にいる頂点
$S$ : $S$ の $i$ 番目の文字に応じて、$i$ 回目に移動する方法が与えられる

考察

現在いる頂点を $V$ とします。はじめは $V=X$ です。

L（左の子に移動する場合）

頂点 $i$ は頂点 $2i$ を左の子として持つと問題文に書いてあります。したがって

$V=2V$ に変更します。つまり、$2$ 倍にします。

R（右の子に移動する場合）

同様に、頂点 $i$ は頂点 $2i+1$ を右の子として持つと問題文にあるので、

$V=2V+1$ に変更します。$2$ 倍して $1$ を足します。

U（親に移動する場合）

$V=\lfloor\dfrac{V}{2}\rfloor$ に変更します。つまり、 $2$ で割って切り捨てます。

普通に値を持ってシミュレートはできない

以上の式を使って、整数値で頂点を管理すればよさそうですが、実はそれではTLEになります。

入力例 $2$ に、以下の記述があります。

移動の途中過程において、高橋君がいる頂点の番号が $10^{18}$ を超えることもあります。

最終的な答えは $10^{18}$ 以下になりますが、途中過程では制限はありません。

例えば、$N=2\times{10^5},\ X=1$ で、$10^5$ 回 L で左の子に移動したあと、$10^5$ 回 U で親頂点に移動し、答えが $X=1$ になる入力を考えてみましょう。

このとき、$10^5$ 回目の移動後にいる頂点は、$2^{10^5}$ です。$10$ 進数表記で $30$ 万桁ほどの数になります。このスケールの数値の計算を何万回も行うのは、$2$ 秒では不可能です。

解法1: 無意味な移動を取り除く

L か R のあとにUが来ると、元の頂点に戻ってくるので、LU か RU という移動は取り除いてしまっても構いません。

スタック（リストでpop()を使えばいいです）を用いて、$S$ の要素を前からスタックに追加していきます。Uが来たときに一番後ろの要素がLかRならば、それを取り除き、Uもスタックに追加しません。

最終的に残った文字を新たな操作列とみなして、操作をシミュレートすれば良いです。

補足: これで間に合う理由

新たな操作列は、U が $0$ 個以上続いたあと、LR が $0$ 個以上続いた操作列になります。LRの後ろにUは絶対に来ません。

頂点番号の変化をグラフにしてみると、U で減り続けたあと、LRで増え続ける、V字型のようなグラフになります。最初の頂点番号も答えも $10^{18}$ を超えませんから、操作途中の頂点も $10^{18}$ を超えません。

したがって、高速に計算ができます。

解法2: 頂点を二進法表記とみなす

完全二分木は、問題文の定義で頂点番号をつけ、さらに頂点番号を $2$ 進法表記とみなすと

• $(頂点\ v\ の二進法表記での桁数)-1=\ v\ の深さ$
• 頂点 $v$ の左の子は、$v$ を $1$ ビット左シフトする（$2$ 倍にするのと同義）
• 頂点 $v$ の右の子は、$v$ を $1$ ビット左シフトして $1$ を足す（$2$ 倍して $1$ を足すと同義）
• 頂点 $v$ の親は、$v$ を $1$ ビット右シフトする（$2$ で割って切り捨てと同義）

という性質があります。

そのまま整数に対してビット演算を使っても意味はありませんが、$2$ 進法表記の頂点番号をスタック（リスト）で管理することで

L : 末尾に0 を追加
R : 末尾に1 を追加
U : 末尾を取り除く（pop()）

という操作に置き換えることができます。これらの操作は $O(1)$ で行えますから、高速に操作をシミュレートできます。

最終的な答えを求めるときは、答えの $2$ 進法表記が入ったリストを適当に $10$ 進法表記に戻して出力すればいいです。

コード

無意味な移動を取り除く

def solve():
    N, X = map(int, input().split())
    S = input()
    T = ["!"]  # リストが空か判定するのが面倒なので、適当な存在しない文字を入れておきます
    for s in S:
        if s == "U" and T[-1] in "LR":
            T.pop()
        else:
            T.append(s)

    """
    T = ["!"] だけのとき、T[1]は配列外参照でエラーになりますが
    スライスの場合配列外を指定しても空のリストが返ってくるだけなので、問題ありません
    """
    ans = X
    for t in T[1:]:
        if t == "U":
            ans //= 2
        elif t == "L":
            ans *= 2
        else:
            ans *= 2
            ans += 1
    return ans


print(solve())

頂点を二進法表記とみなす

頂点番号は、"0"、"1" からなる文字列のリストで持ちます。

文字列で扱う理由は、最終的に答えを $10$ 進法表記の整数（int）に戻すときに楽だからです。これは以下の $2$ つの手順で行えます。

• Vs = ''.join(V) で連結して一つの文字列にする
• ans = int(Vs, 2) で Vs を $2$ 進法表記とみなしたときの、$10$ 進法表記での値が求められる

def solve():
    N, X = map(int, input().split())
    S = input()

    V = [*f"{X:b}"]  # ["1", "0", "1"] のようになります
    # V = [c for c in bin(X)[2:]]
    # V = [*format(X, "b")]
    # などお好みでどうぞ

    for s in S:
        if s == "U":
            V.pop()
        elif s == "L":
            V += ["0"]
        else:
            V += ["1"]
            
    concat = lambda L: ''.join(L)  # 文字列のリストを連結するこれは打つのが面倒なので、テンプレに入れてもいいと思います
    Vs = concat(V)
    return int(Vs, 2)


print(solve())