Ccmmutty logo
Commutty IT
・3 min read

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

アルゴリズム競技プログラミングABCAtCoderPython
https://cdn.magicode.io/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枚組がフルハウスであるか判定して下さい。

制約

  • 1≤A,B,C,D,E≤131 \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(2≤i≤N)i(2\leq i \leq N)の親は人PiP_iです。ここで、Pi<iP_i<iが保証されます。
人11が、人NNの何代前か求めて下さい。

制約

  • 2≤N≤502 \leq N \leq 50
  • 1≤Pi<i(2≤i≤N)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

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