既存投稿一覧ページへのリンク
Before
Next
C問題
もう当たり前のようにC問題でDFSが出てくるのね・・・
AtCoderの問題が難化したのは分かるけど、プログラマー全体のレベルがあがったので本当に怖いわ。
ver. 2025'09-09: ac->2, ac->12, re->12, ac->1
んー？この問題は普通にACすると思っていたけど、reは何故起きるんだ？
復習するときに、原因発掘作業してみますか。
バグ探しは面倒だけど、パズルみたいに暇つぶしになるし、間違えから得るものも多いから後日試してみます。
この残暑の厳しい時期は、ストレスたまるだけなので、寒くなってから・・・ってことで。
def is_cycle_graph_recursive(grp):
n = len(grp)
# 1. 各頂点の次数が2かチェック
for g in grp:
if len(g) != 2:
return False
# 2. 連結判定（再帰DFS）
seen = [False] * n
def dfs(v):
seen[v] = True
for u in grp[v]:
if not seen[u]:
dfs(u)
dfs(0)
return all(seen)
def io_func():
# N, Mを標準入力から取得（最初の行）
n, m = map(int, input().split())
# n頂点分の隣接リストを初期化
grp = [[] for _ in range(n)]
# 各辺の入力を処理してgrpに格納
for _ in range(m):
a, b = map(int, input().split())
# 0-indexedに変換して記録
grp[a - 1].append(b - 1)
grp[b - 1].append(a - 1)
# n, m, grpを戻り値として返す
return n, m, grp
if __name__=="__main__":
n, m, grp = io_func()
ret = is_cycle_graph_recursive(grp)
if ret:
print("Yes")
else:
print("No")
input_python
def io_func():
# N, Mを標準入力から取得（最初の行）
n, m = map(int, input().split())
# n頂点分の隣接リストを初期化
grp = [[] for _ in range(n)]
# 各辺の入力を処理してgrpに格納
for _ in range(m):
a, b = map(int, input().split())
# 0-indexedに変換して記録
grp[a - 1].append(b - 1)
grp[b - 1].append(a - 1)
# n, m, grpを戻り値として返す
return n, m, grp
D問題
入力例01
AtCoder国には動物園が 4園 あり、動物園には 1から4 の番号がついています。
各動物園の入園料は次の通りです。
- 動物園1：1000円
- 動物園2：300円
- 動物園3：700円
- 動物園4：200円
鈴木さんは 3種類の動物（動物1, 動物2, 動物3） が好きです。
それぞれの動物は次の動物園で見ることができます。
- 動物1：動物園1, 動物園3, 動物園4
- 動物2：動物園1, 動物園2, 動物園4
- 動物3：動物園1, 動物園3
鈴木さんは、これら3種類すべての動物を 2回以上ずつ見る ことを目指しています。
同じ動物園を複数回訪れれば、その動物園にいる動物は訪れた回数だけ見たことになります。
例えば、動物園2を2回訪れれば「動物2を2回見た」と数えられます。
このとき、鈴木さんが目標を達成するために支払う入園料の 合計の最小値 を求めてください。
input
4 3
1000 300 700 200
3 1 3 4
3 1 2 4
2 1 3
input_python
def io_func():
# 1行目：n, m を整数として取得
n, m = map(int, input().split())
# 2行目：c（長さnの整数リスト）を取得
c = list(map(int, input().split()))
# 残りm行：各行をaに格納（1つ目の値は不要なのでスライスで除外、0-index化）
a = [
[int(x) - 1 for x in input().split()[1:]]
for _ in range(m)
]
# n, m, c, a をタプルで返す
return n, m, c, a
output
1800
E問題
入力例01
5 個の大きな茶碗が横一列に並んでおり、左から順に
茶碗 0, 茶碗 1, 茶碗 2, 茶碗 3, 茶碗 4 と番号付けされています。
- 茶碗 0 には整数は書かれておらず、初めは豆も入っていません。
- 茶碗 1 には整数 1 が書かれており、最初に 1 個の豆が入っています。
- 茶碗 2 には整数 1 が書かれており、最初は豆が入っていません。
- 茶碗 3 には整数 2 が書かれており、最初は豆が入っていません。
- 茶碗 4 には整数 1 が書かれており、最初に 1 個の豆が入っています。
操作は次のように行います。
-
茶碗 $i$ $(1 \leq i \leq 4)$ をひとつ選び、そこから 1 個以上の豆を取り出す。
-
取り出した豆を、次のいずれかの茶碗に自由に振り分けて入れる：
-
茶碗 1 の場合（書かれている数 $C_1=1$）
→ 茶碗 $1-1=0$ にだけ豆を入れることができる。 -
茶碗 2 の場合（$C_2=1$）
→ 茶碗 $2-1=1$ にだけ豆を入れることができる。 -
茶碗 3 の場合（$C_3=2$）
→ 茶碗 $3-2=1$, 茶碗 2 の2つに自由に分けて入れることができる。 -
茶碗 4 の場合（$C_4=1$）
→ 茶碗 $4-1=3$ にだけ豆を入れることができる。
-
取り出した $k$ 個の豆は、上記で指定された茶碗に合計 $k$ 個入れなければならず、どの茶碗にいくつ入れるかは自由です。
最終的にすべての豆が「茶碗 0」に集まるようにしたい。
そのために必要な最小の操作回数を求めてください。
input
5
1 1 2 1
1 0 0 1
input_python
def io_func():
# 整数 n を入力から取得
n = int(input())
# 配列 c（長さ n、先頭に 0 を追加）を取得
c = [0] + list(map(int, input().split()))
# 配列 a（長さ n、先頭に 1 を追加）を取得
a = [1] + list(map(int, input().split()))
# n, c, a を戻り値とする
return n, c, a
output
3
F問題
入力例01
3 個の押しボタンがあります。このうち 1 個が当たりで、残りの 2 個はハズレです。
青木君はどのボタンが当たりであるか知っており、高橋君は知りません。また高橋君には 3 個のボタンの区別はつきません。
このボタンを使って、青木君と高橋君がゲームを行います。ゲームは以下の一連の流れの 2 回の繰り返しからなります。
- 青木君が 3 個のボタンをランダムな順序に並べる。
- 高橋君が「ボタンを 1 つ選び、そのボタンを押す」という操作を 2 回行う。同じボタンを複数回選んでもよい。
- ゲーム開始時からこれまでに当たりのボタンが何回押されたかを、青木君が高橋君に教える。
2 回の繰り返しで、当たりのボタンを合計 3 回以上押すことができたとき、かつそのときに限り高橋君の勝ちです。
勝つ確率が最大になるように高橋君が行動したときの、高橋君の勝率を求めてください。
雑記
この問題は面白いけど、メッチャ難しいな・・・
E問題の正答率が5割を超えるようになったら挑戦し直します。
input
3 2 2 3
input_python
def io_func():
# 標準入力から1行取得し、空白区切りで整数に変換
n, t, m, k = map(int, input().split())
# 変数をまとめてタプルの形で返す
return n, t, m, k
output
0.222222222222222