LoginSignup
7
1

More than 3 years have passed since last update.

@u2dayo

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

Posted at

AtCoder Beginner Contest 184のA,B,C問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

  • シンプル：余計なことを考えずに済む
  • 実装が楽：ミスやバグが減ってうれしい
  • 時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッターまでどうぞ
Twitter: u2dayo

目次

ABC184 まとめ
A問題『Determinant』
B問題『Quizzes』
C問題『Super Ryuma』

ABC184 まとめ

全提出人数: 7822人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 AB---- 300 12分 5984(5769)位
400 AB---- 300 6分 4983(4768)位
600 AB---- 300 4分 4132(3917)位
800 ABC--- 600 88分 3271(3056)位
1000 ABC--- 600 37分 2454(2240)位
1200 ABCD-- 1000 105分 1767(1556)位
1400 ABC--F 1200 97分 1229(1026)位
1600 ABCD-F 1600 66分 832(636)位
1800 ABCDEF 2100 97分 551(367)位
2000 ABCDEF 2100 73分 352(195)位
2200 ABCDEF 2100 57分 228(96)位
2400 ABCDEF 2100 45分 130(44)位

色別の正解率

色 人数 A B C D E F
灰 3253 98.7 % 92.0 % 15.3 % 2.3 % 1.0 % 0.7 %
茶 1499 99.3 % 99.1 % 45.8 % 9.5 % 4.9 % 4.5 %
緑 1184 99.5 % 99.5 % 63.4 % 29.6 % 18.4 % 14.1 %
水 729 99.9 % 99.9 % 78.5 % 58.7 % 49.1 % 54.6 %
青 360 99.7 % 99.7 % 94.4 % 88.6 % 86.1 % 88.1 %
黄 175 96.0 % 96.0 % 93.1 % 94.3 % 91.4 % 96.6 %
橙 31 96.8 % 96.8 % 96.8 % 96.8 % 96.8 % 96.8 %
赤 11 90.9 % 90.9 % 90.9 % 90.9 % 100.0 % 100.0 %

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

簡易解説


A問題 (7738人AC)『Determinant』

行列式を知らなくても、言われたとおりにやればOKです。

B問題 (7439人AC)『Quizzes』

素直にシミュレートすればOKです。

C問題 (3137人AC)『Super Ryuma』

よくわからないので、法則性を見つけるために小さいグリッドで各マスに何回移動で到達できるか試してみるといいです。
紙に書くと面倒なうえミスが起きやすいので、愚直解を出力するプログラムを組むといいです。

D問題 (1561人AC)『increment of coins』[この記事では解説しません]

確率DPというやつです。

E問題 (1223人AC)『Third Avenue』[この記事では解説しません]

幅優先探索をします。

F問題 (1209人AC)『Programming Contest』[この記事では解説しません]

とくに工夫せずに、ただ『半分全列挙』をやるだけです。

私（うにだよ）の結果（参考）

screenshot.12.jpg

screenshot.32.jpg

A問題『Determinant』

問題ページ：A - Determinant
灰コーダー正解率：98.7 %
茶コーダー正解率：99.3 %
緑コーダー正解率：99.5 %

行列式のことを知らなくても、書いてあるとおりにやれば大丈夫です。

コード

A, B = map(int, input().split())
C, D = map(int, input().split())

print(A * D - B * C)

B問題『Quizzes』

問題ページ：B - Quizzes
灰コーダー正解率：92.0 %
茶コーダー正解率：99.1 %
緑コーダー正解率：99.5 %

実装

素直にforループを使って、問題文通りに実装すれば大丈夫です。無理にかっこよく書こうとせずに、わかりやすさを優先するとミスが減っていいです。

コード

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

score = X

for char in S:
    if char == "o":
        score += 1
    else:
        if score > 0:
            score -= 1

print(score)

C問題『Super Ryuma』

問題ページ：C - Super Ryuma
灰コーダー正解率：15.3 %
茶コーダー正解率：45.8 %
緑コーダー正解率：63.4 %

問題の意味

$1$ 手で、次のどちらかの動きをできる駒『超竜馬』があります。

- 斜め方向に好きなマス動く（将棋の角と同じです。斜め移動と呼ぶことにします）
- 上下左右に3回動く（『マンハッタン距離』が $3$ 以内のマスに動けます。超竜馬移動と呼ぶことにします）

スタートとゴールの座標が与えられるので、『超竜馬』が何手でゴールできるか出力してください。

考察

かなり意味がわからなそうです。よくわからないので、とりあえず移動回数を愚直に計算して出力するプログラムを書いて法則性を見つけたいと思います。紙に書いてもできますが、プログラムにしたほうが楽でミスも少ないです。（参考までに、私はこのコードを書くのに $5$ 分かかりました。なお、コンテスト中は紙に書いて済ませようとしたせいでとても苦労しました）

def change(a, b, p):
    for c in range(K):
        for d in range(K):
            if (a + b) == (c + d) or (a - b) == (c - d) or (abs(a - c) + abs(b - d)) <= 3:
                if grid[c][d] == -1:
                    grid[c][d] = p + 1


K = 41
grid = [[-1] * K for _ in range(K)]
grid[K // 2][K // 2] = 0

for i in range(10):
    for a in range(K):
        for b in range(K):
            if grid[a][b] == i:
                change(a, b, i)

for row in grid:
    print(*row)

すると、出力はこうなります。

1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1
2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2
2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2
2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2
2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2
3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3
2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2
3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3
2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2
3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3
2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 0 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 3 2 2 2 1 1 1 1 1 2 2 2 3 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 3 2 2 2 2 1 1 1 1 1 2 2 2 2 3 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 1 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2
3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3
2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2
3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3
2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2
3 2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2 3
2 3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3 2
3 2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2 3
2 2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2 2
2 2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2 2
2 2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2 2
2 1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1 2
1 2 2 2 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 2 2 1

どうやら、最大でも $3$ 手あれば移動できそうな気がするので、なぜこうなるか考えてみます。

白黒のチェス盤があって、黒いマスからスタートしたとします。斜め移動 $2$ 手で、チェス盤上のどんな黒いマスにでも移動できます。しかし、斜め移動だけではどうやっても白いマスに移動することはできません。ゴールが白いマスだった場合は、ゴールのすぐ横の黒いマスに $2$ 手で移動したあと、さらに超竜馬移動 $1$ 手で横移動すればいいです。こうすれば、チェス盤上のあらゆるマスに$3$ 手以内で移動ができます。こういう理由で、$2$ と $3$ がチェス盤のような並びになっています。（公式解説にも図があります）

$3$ 手まで考えればいいことがわかったので、何手になるか判定する条件式を場合分けして考えましょう。

0手になる場合

移動する必要がないのは、スタートとゴールが同じ場所のときのみです。親切なことに、サンプルに $0$ 手になるケースを置いてくれています。

1手になる場合

$1$ 手で移動できるのは、もちろん $1$ 手で移動できる場合です。（？）$1$ 手で移動できる場所の条件は問題文に書いてあるので、$3$ つのうちどれかを満たすなら $1$ 手で移動できます。

$a+b = c+d$
$a-b = c-d$
$|a-c| + |b-d| \le{3}$

2手になる場合

難しいです。まず、『超竜馬』は $2$ 種類の移動ができることを思い出します。

- 斜め移動
- 超竜馬移動

$2$ 手 の移動の仕方は、$2$ 種類の移動法を組み合わせたものになります。組み合わせ方は、 次の $3$ パターンがあります。

- 超竜馬移動 $2$ 回
- 斜め移動 $2$ 回
- 斜め移動 $1$ 回と 超竜馬移動 $1$ 回

超竜馬移動 2手

超竜馬移動 $1$ 手につき、上下左右に $1$ マス移動することを $3$ 回行えます。つまり、超竜馬移動 $2$ 手で上下左右に $6$ 回移動できます。

簡単にいうと、『マンハッタン距離』が $6$ 以下なら $2$ 手で移動できます。よって、条件は下の式になります。

$|a-c|+|b-d|\le{6}$

斜め移動 2手

先ほどのチェス盤の例でいう、『スタート地点と同じ色のマス』ならどこでも移動できます。式に落とし込むために、もう少し詳しく考えてみます。

斜め移動 $1$ 手で、座標は次のように変化します。

  • $x$ 座標が $+k$、$y$ 座標が $+k$（右上）
  • $x$ 座標が $+k$、 $y$ 座標が $-k$（右下）
  • $x$ 座標が $-k$、$y$ 座標が $+k$（左上）
  • $x$ 座標が $-k$、 $y$ 座標が $-k$（左下）

よって、$x$ 座標と $y$ 座標の変化量の和は、$+2k$, $0$, $-2k$ のどれかになります。ここで、変化量の和が必ず偶数になっていることに注目してください。ということは、何回斜め移動をしても、変化量の和が奇数のマスには絶対止まれません。（この概念をパリティ・偶奇と呼びます）

逆に、変化量の和が偶数になるマスであれば、どんなに遠いマスでも $2$ 手で到達できます。

$|a-c| + |b-d| が偶数（2で割った余りが0）$

- 斜め移動 $1$ 手と 超竜馬移動 $1$ 手

斜め移動 $1$ 手で移動できるマスは、$a+b = c+d$または$a-b = c-d$のマスです。移項すると、$(a+b) - (c+d) = 0$と$(a-b)-(c-d) = 0$になります。

この条件を満たすマスから、超竜馬移動 $1$ 手でマンハッタン距離が $3$ 以下のマスに移動できます。

$|(a+b)-(c+d)|\le{3}$
$|(a-b)-(c-d)|\le{3}$

3手になる場合

$0$ ～ $2$ 手で移動できない場合は $3$ 手です。判定する必要はありません。

実装

条件式を全部書きます。判定部分を関数に分けて、条件を満たした瞬間returnすると楽です。

手数が少ないほうから$0$ 手、$1$ 手、 $2$ 手、$3$ 手の順に判定しないと正しい答えにならないので、注意してください。

コード

def solve():
    # 0手です。サンプルをちゃんと見ていないと、このパターンを忘れると思います。
    if a == c and b == d:
        return 0

    # 1手です。問題文通りに書きましょう。
    if a + b == c + d:
        return 1
    if a - b == c - d:
        return 1
    if abs(a - c) + abs(b - d) <= 3:
        return 1

    # 2手です。考察したとおりに書きます。
    if abs(a - c) + abs(b - d) <= 6:
        return 2
    if (abs(a - c) + abs(b - d)) % 2 == 0:
    # %の優先順位は高いので、左辺の足し算を()で囲まないとWAになります（1敗）
        return 2
    if abs((a + b) - (c + d)) <= 3:
        return 2
    if abs((a - b) - (c - d)) <= 3:
        return 2

    # 2手でダメなら、必ず3手です。
    return 3


a, b = map(int, input().split())
c, d = map(int, input().split())

print(solve())
7
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
7
1