コンテスト時間: 2024-08-03(土) 21:00 ~ 2024-08-03(土) 22:40 (100分)

A - Leap Year

Difficulty: 10

解答時間: 2:16

西暦 $Y$ 年 $(1583 \leq Y \leq 2023)$ の日数 (閏年か否か) を求める問題。
問題文の通りに条件分岐するだけ。
C++20 ~ には、chrono::yearクラスに閏年かを判定するis_leap関数があるらしい。 ABC365 関連か。

B - Second Best

Difficulty: 22

解答時間: 3:53

長さ $N$ の相異なる整数列 $A$ が与えられ、二番目に大きい要素が $A$ の何番目かを求める問題。
pair<int, int>で、1番目に $A_i$ 、2番目に $i$ を格納して1番目で降順ソートすればよい。pair型のソートを2番目で行う場合はsort関数の3つ目の引数に比較関数を取る必要があることに注意。

C - Transportation Expenses

Difficulty: 269

解答時間: 5:20

あるイベントの参加者 $N$ 人の各々の交通費は $A_i$ 円であった。ここで、交通費補助額として上限額 $x$ 円を設定し、人 $i$ については $\min(x, A_i)$ 円を支給することにした。予算 (支給額の総和の上限) が $M$ 円であるとき、 $x$ の最大値を求めよ。ただし、 $x$ を無限に大きくできる場合はinfiniteと出力せよ。
まず、 $x$ を無限に大きくできる条件は $\displaystyle \sum_{i=1}^{N} A_i \leq M$ である。
そうでない場合、求めるのは $\displaystyle \sum_{i=1}^{N} \min(x, A_i) \leq M$ を満たす $x$ の最大値である。ある $x$ について条件を満たすか否かの判定は $O(N)$ で出来るので、 $0 \leq x \leq \max A$ の範囲で二分探索することで答えを効率よく求めることができる。

D - AtCoder Janken 3

Difficulty: 730

解答時間: 74:32

* 高橋君と青木君が $N$ 回のじゃんけんを行った。青木君が出した手は各文字がR(グー)、P(パー)、S(チョキ) のいずれかである長さ $N$ の文字列 $S$ で表される。高橋君の出した手が「青木君に1回も負けなかった」「連続して同じ手を出さなかった」という2つの条件を満たすとき、高橋君が勝った回数としてあり得る最大値を求めよ。

D問題の D は DP の D。
$\mathrm{dp}[i] [j]$ を、「 $i$ 回目に高橋君が手 $j$ を出したとき、 $i$ 回目までに高橋君が条件を満たす手を出して青木君に勝った回数の最大値 $(0 \leq i \leq N - 1, \: j \in \{0, 1, 2\})$ 」と定義する ( $j = 0$ がR、 $1$ がP、 $2$ がSに対応) 。初めは全てのテーブルを $0$ で初期化しておく。
漸化式は以下のようになる (初期条件も含む) 。ただし、 $S_i$ は 0-indexed 。

$\mathrm{dp}[i+1][0] = \left\{ \begin{array}{} \max(\mathrm{dp}[i][1], \mathrm{dp}[i][2]) & (S_i = \text{R}) \\ \max(\mathrm{dp}[i][1], \mathrm{dp}[i][2]) + 1 & (\text{else}) \\ \end{array} \right. \\ * \mathrm{dp}[i+1][1], \mathrm{dp}[i+1][2] \text{についても同様.}$