【競技プログラミング】AtCoder Beginner Contest 402

既存投稿一覧ページへのリンク

一覧ページ

Before

AtCoder Beginner Contest 401

Next

AtCoder Beginner Contest 403

C問題

入力例01

AtCoderレストランでは1から5までの番号がつけられている5種類の食材を扱っています。

また、AtCoderレストランでは1から4までの番号がつけられている4つの料理を提供しています。
各料理に使われている食材は以下の通りです。

• 料理1：（2種類 食材1, 2）
• 料理2：（3種類 食材3, 4, 5）
• 料理3：（3種類 食材1, 2, 5）
• 料理4：（1種類 食材3）

すぬけ君は現在5種類の食材すべてが苦手です。
すぬけ君は、苦手な食材が1種類でも使われている料理は食べられず、苦手な食材が1種類も使われていない料理は食べることができます。

これから5日間かけて苦手な食材を克服しようとしています。
すぬけ君はi日目に食材Biを克服し、それ以降はその食材が苦手ではなくなります。
今回の入力では、次の順に食材を克服します（1 3 2 5 4）：

• 1日目：食材1
• 2日目：食材3
• 3日目：食材2
• 4日目：食材5
• 5日目：食材4

i = 1, 2, ..., 5について、
「i日目にすぬけ君が食材Biを克服した直後、すぬけ君が食べることができるAtCoderレストランの料理の個数」を求めてください。

input

5 4
2 1 2
3 3 4 5
3 1 2 5
1 3
1 3 2 5 4

input_python

input.py

# 入力処理のみを担当する関数です
def io_func():
    # 1行目: n, m を整数値として取得
    n, m = map(int, input().split())
    # 食材ごとに料理番号をリストで保持する
    foods = [[] for _ in range(n + 1)]
    # 各料理が含む食材の集合リスト
    dishes = []
    for _ in range(m):
        data = list(map(int, input().split()))
        dish = set(data[1:])  # 料理が含む食材をセットで
        dishes.append(dish)
        for food in dish:
            foods[food].append(len(dishes) - 1)
    # 最後に使われる食材列
    b = list(map(int, input().split()))
    # 必要変数をまとめて返す
    return n, m, foods, dishes, b

output

0
1
2
3
4

D問題

入力例01

円周上に8個の点が等間隔に並んでおり、時計回りに1, 2, ..., 8の番号がついています。

ここに3本の相異なる直線があります。
各直線は、次のような異なる2つの点を通っています：

1. 1本目の直線：点1と点5を通る
2. 2本目の直線：点1と点8を通る
3. 3本目の直線：点2と点4を通る

このとき、次の2つの条件を両方満たすような整数の組$(i, j)$ の個数を求めてください：

• $1 \leq i < j \leq 3$
• $i$本目の直線と$j$本目の直線は交わる

上記条件と設定に従い、「どの2本の直線同士が交わるか」を調べ、両方の条件を満たす組の数を答えてください。

２本の直線の傾きを調べ、平行か否かで判定すれば解けそうだけど、TLEするだろうな・・・

input

8 3
1 5
1 8
2 4

input_python

input.py

def io_func():
    # N, M を入力から取得
    n, m = map(int, input().split())
    ab_list = []
    # M回 (a, b) の組を取得してリスト化
    for _ in range(m):
        a, b = map(int, input().split())
        ab_list.append((a, b))
    # n, m, ab_list を戻り値として返す
    return n, m, ab_list

output

2

E問題

入力例01

時は 30XX 年、あるコンテストでは提出を行うたびにお金が必要になりました。

このコンテストには 3問の問題が出題されます。
1問目の得点は100点、2問目の得点は200点、3問目の得点は1000点です。
1回提出を行うために必要なお金はそれぞれ1円（全ての問題共通）です。

高橋君は

• 1問目に提出すると 50%の確率で正解
• 2問目に提出すると20%の確率で正解
• 3問目に提出すると1%の確率で正解
  できます。各提出で正解できるかどうかはそれまでの提出とは独立に決まります。

高橋君の所持金は2円です。提出のために払った金額の総額が2円を超えるような提出はできません。

高橋君がコンテストで正解した問題の得点の総和の期待値が最大になるように提出を行った際の、
総得点の期待値を求めてください。

ただし、高橋君は提出の結果を見てから次にどの問題に提出するかを決めることができるものとします。また、同じ問題に2回以上正解しても得点は1回正解した場合と変わりません。

2025年9月1日挑戦アプローチ

# 問題数
N = 3
# 各問題の得点
score = [100, 200, 1000]
# 各問題の正解確率
prob = [0.5, 0.2, 0.01]
# 提出回数（所持金2円なので2回だけ）
MAX_TRY = 2

# dp[state][remain]: stateはbitで正解した問題, remainは残り提出数
dp = [[0.0 for remain in range(MAX_TRY + 1)] for state in range(1 << N)]

for remain in range(MAX_TRY + 1):
    # すべての状態（既に正解した問題の組み合わせ）について計算
    for state in range(1 << N):
        # すでに正解した問題の得点合計
        total_score = sum(score[i] for i in range(N) if (state >> i) & 1)
        if remain == 0:
            # もう提出できないならこれ以上得点は増えない
            dp[state][remain] = total_score
        else:
            # これから1回提出可能
            best_expectation = total_score  # 何もしない場合（提出しない選択肢は無意味だが安全のため）
            for q in range(N):
                if not (state >> q) & 1:  # まだ正解してない問題なら提出できる
                    # 正解する場合
                    next_state = state | (1 << q)
                    expect = (
                        prob[q] * dp[next_state][remain - 1] +
                        (1 - prob[q]) * dp[state][remain - 1]
                    )
                    best_expectation = max(best_expectation, expect)
            dp[state][remain] = best_expectation
print(dp)
# 初期状態: どれも正解していない (state=0), 残り提出数2
print(dp[0][MAX_TRY])

state(bit)	remain=2	remain=1	remain=0
000	95.0	50.0	0
001	174.0	140.0	100
010	280.0	250.0	200
011	319.9	310.0	300
100	1095.0	1050.0	1000
101	1172.0	1140.0	1100
110	1275.0	1250.0	1200
111	1300.0	1300.0	1300

状態の定義

• $ S = (m, s_1, s_2, s_3) $

  • $ m $：残り提出回数（= 残り所持金、0～2の整数）
  • $ s_i $：問題$i$（1〜3）が既に正解済みかどうか（0: 未正解、1: 正解）

• $ DP[m][s_1][s_2][s_3] $

  • 「残り提出回数 $ m $で、各問題の正解状況が$ (s_1, s_2, s_3) $ のときの最高期待値」

遷移式

任意の状態 $ (m, s_1, s_2, s_3) $ について（$ m > 0 $ の場合）

• まだ正解していない任意の問題 $i$（$ s_i = 0 $）を選び提出する
• 問題$i$の正解確率を $ p_i $、得点を $ t_i $ とする
• 遷移は
  • 正解した場合：$ s_i = 1 $ になり得点加算、残り提出回数が1減る
  • 不正解の場合：$ s_i $はそのままで、残り提出回数が1減る
• 期待値は
  $
  DP[m][s_1][s_2][s_3] = \max_{i: s_i = 0} { p_i \cdot (t_i + DP[m-1][s_1, ..., s_i=1, ..., s_3]) + (1-p_i) \cdot DP[m-1][s_1, s_2, s_3] }
  $
  （この$\max$は、どれを次に提出するかの最適判定）

終端状態（ベースケース）

• $ m=0 $（残り提出回数なし）または全て正解済み（$ s_1=s_2=s_3=1 $）：
  $DP[s_1][s_2][s_3] = 0$

各パラメータ値

• $ t_1 = 100, p_1 = 0.5 $
• $ t_2 = 200, p_2 = 0.2 $
• $ t_3 = 1000, p_3 = 0.01 $

bitDPの問題かな？

input

3 2
100 1 50
200 1 20
1000 1 1

input_python

input.py

def io_func():
    # n: データの個数, x: 時間または容量などの上限
    n, x = map(int, input().split())
    
    s, c, p = [], [], []  # 各リストを初期化
    
    for _ in range(n):
        # i, j, k: 各データの属性（整数値）
        i, j, k = map(int, input().split())
        s.append(i)  # 最初の属性をsリストに追加
        c.append(j)  # 2番目の属性をcリストに追加
        p.append(k)  # 3番目の属性をpリストに追加
    
    # 入力値をタプルで返す: n, x, sのリスト, cのリスト

output

95

F問題

入力例01

2行2列のグリッドがあります。各マスには下記のように数字が書かれています（上からi行目、左からj列目のマスを(i, j)とします）。

	1列目	2列目
1行目	1	2
2行目	3	1

はじめ、コマがマス(1, 1)（1行1列目）にあります。Sを空文字列とし、以下の操作を3回（2×2-1回）繰り返します。

• Sの末尾に現在コマがいるマスに書かれた数字を連結する。
• コマを現在のマスの下か右に1マス移動する。ただし、3回目（最後）の操作では移動しません（行動は最大で2回まで）。

3回の操作の後、コマはマス(2, 2)（2行2列目）にいて、Sの長さは3になります。

最終的な文字列Sを整数としてみた値をM=7で割った余りがスコアです。

達成可能なスコアの最大値を求めてください。

（例：どのような経路を通るかでSが異なり、割り算の余りも異なります。最大となる経路を考えてください。）

input

2 7
1 2
3 1

input_python

input.py

def io_func():
    # 1行目から N, M を整数として取得
    n, m = map(int, input().split())
    # 2行目以降から N行分のリストを取得
    a = []
    for _ in range(n):
        # 各行は空白区切りの整数のリストになる
        row = list(map(int, input().split()))
        a.append(row)
    # 変数 n, m, a を戻り値として返す
    return n, m, a

output

5