AGC022 C - Remainder Game
問題 → C: Remainder Game - AtCoder Grand Contest 022 | AtCoder
解法概要
- 各に対して条件を満たす集合を列挙
- 貪欲で条件を満たす集合を最小化
の最大値をとおくと、全体の計算量は
解法
1. 各に対して条件を満たす集合を列挙
とおく。
とするとは
となり、コードに落とすと次のようになる。
long[] f(long x, long y) { if (x == y) return [0L]; long[] res = []; foreach(i; 1..x+1) { res ~= f(x%i, y).map!(bits => bits|1L<<i).array; } return res; }
雑に計算量を求めるとの計算にかかる。各を求めると合わせて。
2. 貪欲で条件を満たす集合を最小化
とおく。
- が最終的な答え。
- なければ
-1
を出力。
が成り立つので、この判定は愚直にでできる。
の一つをとおく。よりに対して次が成り立つ。
よって最高位ビットから順に貪欲すればが求まる。
long ans = (1L<<K)-1; foreach_reverse(i; 0..K) { long bits = ans>>(i+1)<<(i+1)|((1L<<i)-1); if (/* 集合bitsは\mathscr{A}に含まれるか? */) { ans = bits; } }
提出コード
感想
コンテスト中、大体の考察はできてたけど時間に追われて焦って考察&コーディングをしたためWA連発。AC取れず。悲しい
問題自体は、コストがであったり制約が「」であったりと誘導(?)が強い問題だったと思う。考察重視のわりと好きなタイプの問題。