Magicode logo
Magicode
3 min read

5完できない芸人の緑コーダーがABC263のA~Eまで

https://cdn.apollon.ai/media/notebox/blob_6Hqoquj

LINE Verda プログラミングコンテスト(AtCoder Beginner Contest 263)

ABC263のA~Eに関する解説(という名の自分用メモ書き)です。

戦績

(今回も)(いつもどおりの)4完でした!!!!!
今回、は、Eがハイパー超絶崖っぷちでした…。
Dまでは順調で割とサクサクだったので、Eの難易度がもうちょっと低ければ…夢の5完に届いたかもしれない….
次こそ!5完!したい!(N回目定期)

全体のざっくり解説

  • A : 条件分け
  • B : DP or ループ
  • C : BFS/DFS/再帰 or 裏技一発
  • D : 全探索を累積和で高速化
  • E : 確率DP

A - Full House

問題要約

55枚のカードがあります。整数A,B,C,D,EA,B,C,D,Eが書かれています。
以下の条件を満たす時、フルハウスであると呼ばれます。
  • 同じ数が書かれたカード3枚と、別の同じ数が書かれたカード2枚からなる 55枚組がフルハウスであるか判定して下さい。

制約

  • 1A,B,C,D,E131 \leq A,B,C,D,E \leq 13
  • A,B,C,D,EA,B,C,D,E全てが同じ値ではない
  • 入力は全て整数

考察

  • 5枚の手札がフルハウスかどうかを判定したい
  • フルハウスの条件を言語化して考えよう
  • 5枚を昇順に並べ替えた時に…
    • 1枚目と3枚目の数が一緒、かつ、4枚目と5枚目が一緒
    • 1枚目と2枚目の数が一緒、かつ、3枚目と5枚目が一緒
  • これが満たされるならフルハウス完成!
python
# 入力
L = list(map(int, input().split()))

# 並び替えて…
L.sort()

# 条件1 もしくは、条件2が満たされるなら、フルハウス!
if (L[0] == L[1] and L[2] == L[4]) or (L[0] == L[2] and L[3] == L[4]):
    print('Yes')
# そうじゃないなら、フルハウスじゃない…
else:
    print('No')

B - Ancestor

問題要約

NN人の人が居ます。NN人の人には、人11,人22,…,人NNと番号がついています。
i(2iN)i(2\leq i \leq N)の親は人PiP_iです。ここで、Pi<iP_i<iが保証されます。
11が、人NNの何代前か求めて下さい。

制約

  • 2N502 \leq N \leq 50
  • 1Pi<i(2iN)1 \leq P_i < i(2 \leq i \leq N)
  • 入力はすべて整数

考察

  • 公式解説で、一部揉めてたようですが今考えると色んな解き方ができそう…良いB問題な気もします。
  • 黒ココアさんは、本番ではループでカウントしていきました。
  • 折角なので、DP解法も考えてみませう
  • dp[i]:=dp[i] := 11は、人iiの何代前か
    • 言い換えると、人iiは、人11の何代後か
  • dp[0]=0,dp[1]=0dp[0] = 0, dp[1] = 0
  • Pi<iP_i < iなので、
  • dp[i]=dp[Pi]+1dp[i] = dp[P_i]+1
  • 最終的にdp[N]dp[N]を見ればOK!
python
# ループVer

# 入力
N = int(input())
# 頭に2要素つけることで、1-indexedに変換
P_L = [0, 1] + list(map(int, input().split()))

ans = 0 # さかのぼりカウント!○代前!1世代ずつ遡るよ!
now = N # 今見てる人!人Nから見ていくよ!

# 今見ている人が、人1じゃないかぎりループ!
while now != 1:
    # 今見ている人を、1つ上の世代にして…
    now = P_L[now]
    # さかのぼりカウントを1つ足すよ!
    ans += 1
    
# さかのぼりカウントを出力して終わり!
print(ans)
python
# DPver

# 入力
N = int(input())
# 頭に2要素つけることで、1-indexedに変換
P_L = [0, 1] + list(map(int, input().split()))

# dpテーブル作成!
dp = [0] * (N + 1)

# 人2から、人Nまで順番に見ていくよ!
for i in range(2, N + 1):
    # 人iの世代は、人iの親の世代 + 1
    dp[i] = dp[P_L[i]] + 1

# 人Nの世代を出して終了!
print(dp[N])
C以降:後日追記!!!!

Discussion

コメントにはログインが必要です。