【AtCoder】Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）コンテストまとめ

2025-10-302025-11-7

コンテスト時間: 2025-10-25(土) 21:00 ~ 2025-10-25(土) 22:40 (100 分)

A 問題

正整数 $N,M$ が与えられる。 $i = 1, 2, \ldots, N$ について、 $i\leq M$ のときOKを、そうでないときToo Many Requestsを出力せよ。

長さ $N$ の整数列 $A$ と整数 $M$ が与えられる。 $A$ の $N$ 個の要素から $1$ 個を取り除くことで、残りの $N-1$ 個の要素の和をちょうど $M$ にできるか判定せよ。

$A_j$ を取り除いたとすると、残り $N-1$ 個の要素の和は $M = \sum_{i=1}^{N} A_i - A_j$ となる。
これを変形すると $A_j = \sum_{i=1}^{N} A_i - M$ であるから、 $A$ の総和を求めたうえで、各要素が $\sum_{i=1}^{N} A_i - M$ と等しいかを調べればよい。

長さ $N$ の整数列 $A$ が与えられる。 $1\leq i < j < k \leq N$ をみたす整数の組 $(i,j,k)$ であって、次の条件をみたすものの個数を求めよ。

$A$ の中に 2 回出現する値 $v$ を固定して考える。
$A$ に出現する要素の個数を連想配列などで数えておき、値 $v$ の出現回数を $c_v$ とする。
ある値 $v$ $v$ に注目したとき、
- $A$ から $v$ を 2 個選ぶ選び方は $\binom{c_v}{2}$ 通り
- $A$ の中で $v$ 以外の値を 1 個選ぶ選び方は $N - c_v$ 通り
したがって、求める答えは $\sum_{v=1}^N \binom{c_v}{2} \times (N - c_v)$ である。

最初、 $A_j$ を固定して数え上げる方針を取ったのだが、考察している途中で上述の「2 回出現する値を固定する」方針の方が楽なことに気づき、そちらに切り替えたので時間がかかってしまった。
最初の方針でも解けなくはなさそうだが、場合分けが面倒臭い。

$1$ 周の長さが $M$ である池があり、その周上に $1$ つの小屋と $N$ 人の人が立っている。実数 $x$ $(0\leq x <M)$ について、小屋から時計回りに $x$ だけ進んだところを地点 $x$ と定義する。 $i$ 番目の人は、地点 $A_i$ にいる。

また、 $N$ 以下の整数 $C$ が与えられ、 $i=0,1,\ldots,M-1$ について $X_i$ を次のように定義する。

このとき、 $\sum_{i=0}^{M-1} X_i$ を求めよ。

$X_i$ は人がいる地点を通過するときにしか変化しないので、人がいる地点を人数と共にまとめておく。
人数に関して池の 2 周分の累積和を取り、「 $(スタート地点から始めに人と出会う地点の人数) + C$ を超える一番小さい人数」を二分探索によって求めればよい。
ただし、「スタート地点から始めに人と出会う地点」は、小屋を跨ぐときとそうでないときで場合分けが必要。