AtCoder-ABC184 A - Determinant / B - Quizzes / C - Super Ryuma【Python解答例】
AtCoder Beginner Contest184に出場し、初めてC問題まで解くことができました。
atcoder.jp
最適なプログラムにはほど遠いと思いますが、
C問題まで私の解答を例として書いていきたいと思います。
AtCoder Beginner Contest184 A - Determinant
制約
・入力は全て整数
・−100≤a,b,c,d≤100
a, b = map(int,input().strip().split()) c, d = map(int,input().strip().split()) ans = a*d - b*c print(ans)
入力を受け取って問題文通りの計算を行えば行列式ansが求まります。
ansを出力してACとなりました。
AtCoder Beginner Contest184 B - Quizzes
問題文
高橋くんは、N問のクイズに答えます。高橋くんの持っている点数ははじめX点で、クイズに正解すると1点増え、不正解だと1点減ります。
ただし、持っている点数が0点のときに不正解となった場合は点数は減りません。
高橋くんのクイズの結果が文字列Sで与えられます。
Sの左からi番目の文字が o のとき、i問目が正解だったことを、x のとき、i問目が不正解だったことを表します。
高橋くんの最終的な点数はいくつでしょうか?
制約
・1≤N≤2×10^5
・0≤X≤2×10^5
・Sは o と x からなる長さNの文字列
n, x = map(int,input().strip().split()) s = input() for i in range(n): if s[i] == "o": x += 1 else: x -= 1 if x <= 0: x = 0 print(x)
高橋君の持ち点がXで与えられ、文字列Sをもとに点数を増減させます。
for分で文字列の1個目から最後まで順に確認していきます。
文字列の該当する文字が○ならxを1増加させ、バツなら1減少させます。
問題文から点数は0点より小さくしてはいけないため、xが0以下なら0を代入しています。
ループを抜けた後、xを出力するとACでした。
AtCoder Beginner Contest184 C - Super Ryuma
問題文
無限に広がる2次元グリッドがあり、マス(r1,c1)に駒「超竜馬」が置かれています。
この駒は、超竜馬がマス(a,b)にあるとき、以下のいずれかの条件を満たすマス(c,d)に動かすことができます。
・a+b=c+d
・a−b=c−d
・|a−c|+|b−d|≤3
超竜馬を(r1,c1)から(r2,c2)に動かすのに必要な最小手数を求めてください。
制約
・入力は全て整数
・1≤r1,c1,r2,c2≤10^9
r1, c1 = map(int,input().strip().split()) r2, c2 = map(int,input().strip().split()) ans = 0 if r1 == r2 and c1 == c2: ans = 0 elif r1 + c1 == r2 + c2 or r1 - c1 == r2 - c2 or abs(r1 - r2) + abs(c1 - c2) <= 3: ans = 1 elif (abs(r1 - r2) + abs(c1 - c2)) % 2 == 0 or abs(abs(r1 - r2) - abs(c1 - c2)) <= 3 or abs(r1 - r2) + abs(c1 - c2) <= 6: ans = 2 else: ans = 3 print(ans)
超竜馬は斜めにどこまでも動くことができるので、3手あればどこマスでも移動できます。(これに気付くのに時間がかかりました…)
したがって、0手・1手・2手になる条件を考えていき、どれにも該当しなければ3手とするプログラムを考えました。
0手の条件は初期マスと目的マスが一致していることですので、入力から渡されるrとcをそれぞれ比較して確認できます。
1手で動ける範囲は問題文に記載してある条件ですので、そのまま書きました。
2手の条件は3通りあると思います。
まず将棋の角のように斜めにどこまでも動けるので、移動するマスの数が偶数であれば2手で移動できます。(将棋の盤面を描いて考えるとわかりやすかったです)
また、斜めにできるだけ近くまで動いたあとで目的のマスが3マス以内ならば2手ですので、その条件をabs(abs(r1 - r2) - abs(c1 - c2)) <= 3と書きました。
最後に目的のマスが6マス以内なら2手で動けますので、その条件も足しています。目的のマスが3マス以内の場合は先に記載してあるので、自動的に3より大きく6マス以下の2手で動ける条件となります。
以上のプログラムでACできました。
今回 初めてC問題まで解くことができましたが、D問題はさっぱりわかりませんでした。
公式解説を読むとまた新しい手法が載っていましたのでそちらも勉強したいと思います。
(勉強することが多くなりすぎてアウトプットが滞りがちです…)
2020/11/25追記
D問題を解くには確率DPを理解しなければならないようですが、そもそもDP自体の難易度が高いようです。
調べていくとEducational DP ContestというDPの教育的問題集がありましたので、こちらに取り組み理解を進めたいと思います。
D問題への再挑戦には時間がかかりそうです…