Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】ミラティブプログラミングコンテスト2025（AtCoder Beginner Contest 414） - 参加記 | 緑コーダーが解くAtCoder

AtCoder-ABC-コンテストまとめ AtCoder-ABC AtCoder ABC コンテストまとめ競技プログラミング

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

A - Streamer Takahashi

Difficulty: 11 / NoviSteps: ???

解答時間: 1:44

高橋君は $L$ 時から $R$ 時に配信をすることにした。高橋君には $N$ 人のリスナーがおり、 $i$ 人目のリスナーは $X_i$ 時から $Y_i$ 時まで配信を見ることができる。高橋君の配信を最初から最後まで見ることができるリスナーは何人いるか求めよ。

$X_i \leq L, \, R \leq Y_i$ となる $i \: (1 \leq i \leq N)$ の個数を数えればよい。

B - String Too Long

Difficulty: 37 / NoviSteps: ???

解答時間: 3:16

文字列 $S$ を $N$ 個の文字と整数の組 $(c_i, l_i)$ にランレングス圧縮したものが与えられるので、 $S$ を復元せよ。ただし、 $S$ の長さが $100$ を超える場合にはToo Longと出力せよ。

ランレングス圧縮のライブラリを自分は持っていたので、これを貼るだけ。
ただし、 $|S| + l_i \gt 100$ となったときは即座にToo Longとして処理を打ち切る。

C - Palindromic in Both Bases

Difficulty: 709 / NoviSteps: ???

解答時間: 21:44

正の整数 $A, N$ が与えられるので、 $1$ 以上 $N$ 以下の整数のうち、十進法での表記も $A$ 進法での表記も回文であるようなものの総和を求めよ。

方針としては、以下のようになるはず。
- 十進法で回文となる数 $x$ を桁数ごとに生成
- $1 \leq x \leq N$ の範囲チェック
- $x$ を $A$ 進法での表記 $x_A$ に変換
- $x_A$ が回文なら、総和に $x$ を加算
回文生成時は、作りたい長さを $l$ としたときに、「長さ $\left\lceil \frac{l}{2} \right\rceil$ の前半部分だけ作って、後半部分は前半部分を反転してくっつける」ということをすれば簡単。
基数変換は以前紹介した自作ライブラリを貼ればラクができる。

yuulis.hatenablog.com

解法は割とすぐに思いつくのだが、実装がやや大変。
コンテスト時間中に、私の記事が結構アクセスされてたみたいで嬉しかったです。

D - Transmission Mission

Difficulty: 841 / NoviSteps: ???

解答時間: 20:54

数直線上に $N$ 棟の家があり、家 $i$ は座標 $X_i$ にある。ただし、座標に複数の家が位置していることもある。ここで、 $M$ 個の基地局を数直線上の任意の実数座標に配置し、それぞれの基地局に対して非負整数の値の電波強度を設定する。ある基地局の電波強度を $x$ にしたとき、その基地局からの電波が家に届く条件は、その基地局とその家の距離が $\displaystyle\frac{x}{2}$ 以下であることである。どの家にも少なくとも1つの基地局から電波が届くように基地局の位置と電波強度を設定するとき、電波強度の総和がとりうる最小値を求めよ。

以下、 $X_i$ は昇順にソートされているとする。
電波強度が $x$ の基地局を中心として範囲 $x$ の区間がカバーされると考えると、 $M$ 個の基地局がカバーする区間の長さの合計を最小化すればよいが、これは $N$ 棟の家を $M$ 個の連続したグループに分割し、各グループの「最大座標と最小座標の差」の合計を最小化することと同値である。
隣接する家の座標の差を $d_i = x_{i+1} - x_i$ としてこれを降順ソートすれば、 $d_i$ の大きい順に $M-1$ 個選び、各 $i$ について座標 $x_i$ と $x_{i+1}$ の間でグループ分けすればよい。
よって、求める答えは $X_N - X_1 - \displaystyle \sum_{i=1}^{M-1} d_i$ である。

結果

Performance: 1211

1086 → 1099 (+13)

D問題までは良いペースで解けたが、それ以降が続かなかった。