競プロを頑張るブログ

問題を解いてる時の思考なりをまとめていきます

東京海上日動 プログラミングコンテスト2020 C問を解いた

atcoder c++ 競プロ 競技プログラミング 解法

はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

C - Lamps

水色diffの問題です。
本番中に沼にどハマりしました。

以下はネタバレがあるので見る際は注意してください。

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。 問題を解いている際に考えていたことをまとめておこうかなと思います。











問題概要

電球がN個並んでいる。
電球iは座標iにあってA_{i}に光ってる。

座標xに光の強さdの電球があるとき、その電球はx - d - 0.5 ~ x + d + 0.5までの区間を照らす。
(両脇d個の電球を照らす感じだね。)

以下の操作をK回繰り返す。

  • 1以上N以下の各整数iに対し、操作時に座標iを照らしている電球の個数をB_{i}とする。そして、各電球iの光の強さをB_{i}に変更する。

(操作時に、自身を照らしている電球の数B_{i}で次に光る　って感じだね。)

K回の操作後、各電球の光の強さを求めよ。

考察

まずは素直に考えてみようかな。

1回目の操作を考えたとき、各電球がどれを照らしているかを考えればいいかな？
とするとO(N^{2})かかるから、K回の操作も考慮するとO(N^{2}K)だね。

どれを照らしているかはいもす法を使って数えるのが典型かな。

それでO(NK)だね。
まだこれだと1010以上にかかっちゃうからダメそうだね。

(ここからしばらく沼にハマりました。。。)

各電気がK回の操作後にどうなってるかをO(1)で求めらると良さそうだよね。

とりあえずKが小さい時から考えてみようかな。

・・・。

もしかして、電気の明るさは今よりも暗くなることはないのかな・・・？
直感的に、自分を照らしている遥か遠くの電球が影響しそうだよね。

0, 0, 0, 0, 0, ..., 100, 101 (N = 101)

とかの場合を考えてみるよ。

次の明るさは、
2, 2, 2, 2, 2, ..., 2, 2
になるね。

最後の二つは減っちゃうね。
他は増えて、おそらく今後も増え続けていくと思う。

最初に照らされている数がどうにも怪しい感じがするね。

(まだまだ沼は続きます。。。)

x回目の操作時にそれぞれの電球はどうなるんだろう。

1つ目の電球に注目したとき、1回目の操作時には絶対に1以上になるね(自身に照らされてるから)
2回目の操作時には、隣の電球が1以上になってるはずだから絶対に2以上になるね。
2つ目の電球に注目すると、2回目操作時は両脇が1以上になってるはずだから3以上になるね。

x回目の操作時には、各電球がx以上にはなってそう。

なんとなく規則性が見えてきた・・・かな？

それでも全くわからないよおおおお。。。

この後も沼にハマり続け、いもす法で実装したO(NK)でシミュレートしていると・・・。

あれ・・？
K回も操作しないうちに全部の値がNになってる。

適当にKを大きい値で試すと、指数関数的に必要な操作回数が減ってる事を発見！

結局、全部同じ値になったら操作を打ち切って、いもすそのままでAC！

あとがき + 解法(ネタバレ全開)











いもす法を使って、各操作ごとの電球の状態をO(N)で求めました。

いもす法は、範囲加算を考えたい時に使う手法ですね。
下図のように、範囲の始点に加算したい値を加算、終点 + 1に加算したい値を減算して、一番最後に累積和を行うと求めたい答えになっているというアルゴリズムです。

f:id:hipotaf:20200614150006p:plain

一度の範囲加算で2回しか操作がないので、計算量はO(N)になりますね。

問題の話に戻りますがO(N)をK回行うので、このままだとO(NK)かかりそうです。

ですが、実は電球の状態が収束するまでにかかる操作回数は非常に少ないです。

電球がN個しかない事から、あり得る最大の明るさはNである事がわかります。
また、Nを小さい値でシミュレートしてみると全ての電球が最大値に収束する事がわかると思います。

その状態に何回でなるのかをシミュレートしてみます。

すると、Nを大きくしても収束にかかる操作回数はほとんど増えない事がわかります。

Nを104くらいにしても29回で収束したので、計算量も余裕を持って間に合うと判断しました。

ソースコード

int main() {
  ll input(n, k);
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  REP(j, k) {
    // --- いもす ここから
    vector<ll> table(n + 1, 0);

    REP(i, n) {
      // 範囲外を照らしている光を考えないようにする
      table[max(0ll, i - a[i])] += 1; // 範囲始点
      table[min(n, i + a[i] + 1)] -= 1; // 範囲終端
    }

    // 累積和
    vector<ll> cumsum(n + 1, 0);
    partial_sum(table.begin(), table.end(), cumsum.begin());
    // --- いもす　ここまで

    REP(i, n) a[i] = cumsum[i];

    // 電球が全てNの明るさになっていたらストップ
    ll sum = accumulate(a.begin(), a.end(), 0ll);
    if (sum == n * n) {
      cout << j << endl;
      break;
    }
  }
  REP(i, n - 1) {
    cout << a[i] << " ";
  }
  cout << a[n - 1] << endl;
}

マクロに関しては別の記事でまとめてあります。

テンプレート - 競プロを頑張るブログ

REPと入出力のみ使用しています。
REPは半開区間となっています。

https://atcoder.jp/contests/tokiomarine2020/submissions/14248610

いもす法の計算途中、電球の無い場所を照らしている電球が存在します。
範囲外の光は何にも影響を及ぼさないのでmaxやminで切り落としています。

終端の確認は、中身の合計がN^{2}になっていたら止めています。
N個の電球がそれぞれNに光っているかどうか、ですね。

電球達の最小値がNになっているか、などここに関しては色々方法があると思います。

それでは、またっ！