AtCoder Beginner Contest 263のA～D問題を解いたので、その解説や感想などを書いていきます！
緑コーダーなので、それ以上の方には役立たない内容だと思います。
同じ緑コーダーの人や茶、灰コーダーの人の参考になれば幸いです。
言語はPythonです！
A: Full House
5個の数字がフルハウス（5個のうち3個と2個がそれぞれ同じ数字）であるかを判定する問題。
重複がある数字の個数を数えればよいので、5個の数字を辞書に入れて「数字が2種類しか出ていない」→「数字の数が3個と2個」というように判定するようにしてみました。
（辞書についての解説はこちら）
A = list(map(int,input().split()))
cards = dict()
for a in A:
cards[a] = cards.get(a,0) + 1
keys = list(cards.keys())
if len(keys) == 2:
num = cards[keys[0]]
if num == 3 or num == 2:
print('Yes')
else:
print('No')
else:
print('No')
私は辞書を自分で作っていたのですが、つよつよコーダーの人の回答を見るとcollections.Counterを使っているコードを見つけました。
これを使うと自分で長々と書かずに同じ結果が得られるんですね…
B: Ancestor
N番目の人から1番目の人まで辿っていき、その間に何人の人がいるかを求める問題です。
PnからPi=1になるまで辿って行って、その処理を何回行ったかを出力すればよいはず。
ただし、何も考えずにP2~Pnを配列に入れてしまったので、インデックスが2こずれちゃってます…
n = int(input())
P = list(map(int,input().split()))
next = n-2
ans = 0
while True:
next = P[next] - 2
ans += 1
if next == -1:
break
print(ans)
解説を見ると、1から辿っていく方法が紹介されていました。
1から辿っていく場合は今までの結果をメモするという実装になるようですが、個人的にはNから辿る解法のほうがすぐに思いつきました。
C: Monotonically Increasing
長さがNで要素がM以下の単調増加な数列を列挙する問題です。
入力例2を使って（入力例1は小さくてイメージし辛かった）初めに考えたのは、123→124→125でその次が123…というように、いけるところまで行ってから戻ればいけそうだったので、深さ優先探索で解けるのではと思いました。
ということでこんな感じのコードを書いたら無事に動きました。
n, m = map(int, input().split())
def dfs(A):
if len(A) == n:
print(*A)
return
last = 0 if len(A) == 0 else A[-1]
for i in range(last+1, m+1):
dfs(A + [i])
dfs([])
幅優先探索はよく出てくるので使えると解ける問題が増える気がしますね！
解説を見るとPythonのitertools.combinationsを使う方法もありましたが、これはずる過ぎます…笑
D: Left Right Operation
ある数列が与えられたとき、任意の連続する左右の部分を与えられた数字に置き換えて（置き換えなくても良い）最小値を求める問題です。
時間内に解けなかったので解説を見ながら自分なりに解きました。
この問題は次のように考えてみました。
一気に左右を置き換えるというのは大変なので、まずは左側だけ置き換えたときの最小値を探します。
この最小値の探し方は解説にある通り、k番目の最小値がわかっているときに、k+1番目の最小値は『k番目の最小値+A[k+1] （途中で置き換えるのやめる）』or『L*(k+1) （全部置き換える）』の小さい方で求めることができます。
ここで、k番目の最小値を求めるときに、「途中で置き換えるのをやめる」場合が含まれているということは、残りのk+1番目以降は全部Rで置き換えても良いということになります。
ということで、こんな感じのコードを作成しました。
n, l, r = map(int, input().split())
A = list(map(int,input().split()))
dp = [0]*(n+1)
for i in range(1, n+1):
dp[i] = min(dp[i-1] + A[i-1], l*i)
ans = 1e16
for i in range(n+1):
ans = min(ans, dp[i] + r*(n-i))
print(ans)
for文を2回ループしていますが、今思うとk番目までの最小値と全体の最小値は同時に求めることができますね…
コードを実装するにあたって、最小値の初期値をとりあえずで1010にしたらWAになってしまいました。
ちゃんと制約を読まないといけませんね…
まとめ
今回、初めて競技プログラミングを解くだけでなく感想記事を作成しましたが、ただ解くだけのときと比べて非常に勉強になりますね。
collections.Counterとかちゃんと制約を読むとか、反省点がいっぱいあります。
E問題まで解けるようになるといいなーと思いつつ精進します。
おしまい！
コメント