buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

yukicode No.1513 simple 門松列 problem

最近この手の記事を書いていないので書く。この問題は、多段階の考察が必要。

問題

(0...K) から構成される数列のうち、門松列列を満たすものの個数を求めよ。ついでに含まれている数の総和を求めよ。

考察

めんどくさいので、以降門松列列を🎍と呼ぶ。

0

総和の計算は難しいので一旦忘れる。まずは数え上げをする。

1

よくある動的計画法。🎍を満たす数列に整数を末尾に加えた数列が🎍を満たしているかどうかは、2つ前の値と今追加した値を見れば判定が出来る。 だから、2つ前の値をパラメータに持つ動的計画法をやる。

つまり、dp1[c][i][j] := 1つ前の値がjで2つ前の値がiであるような長さc+2の数列のうち🎍を満たす数列の個数 と定義したdp1を計算する。
長さ2(c=0)の時は、dp1[0][i][j] = i==j と定義すると、若干楽出来る。

最終的に求めたい「門松列列を満たすものの個数」は、dp1[N-2][i][j] (i=0...K, j=0...K) の総和を取れば良い。

  repeat(i, K) {
    repeat(j, K) {
      dp1[0][i][j] = i != j;
    }
  }
  
  repeat(c, N-2) {
    repeat(i, K) {
      repeat(j, K) {
        repeat(k, K) {
          if (kado(i,j,k)) {
            dp1[c+1][j][k] += dp1[c][i][j];
            dp1[c+1][j][k] %= MD;
          }
        }
      }
    }
  }
  ll total1 = 0;
  repeat(i, K) {
    repeat(j, K) {
      total1 += dp1[N-2][i][j];
    }
  }
  total1 %= MD;

時間計算量はO(NK3)。最悪ケースで10秒ぐらい掛かるので、4重ループを改善したい。

2

このような、単純なループは、ループ順序を並びかえることが出来る場合がある。 入れ替えても問題無さそうなので、並び替えてみる。

  repeat(c, N-2) {
      repeat(j, K) {
        repeat(k, K) {
    repeat(i, K) {
          if (kado(i,j,k)) {
            dp1[c+1][j][k] += dp1[c][i][j];
            dp1[c+1][j][k] %= MD;
          }
        }
      }
    }
  }

iを内側にしてみた。dp1の参照にiは使っていないので、なんかうまいこと計算すればiのループを無くせそうなお気持ちが湧いてくる。

3

iのループを無くせそうだが、🎍判定関数 kado(i,j,k) がこれを阻害している。展開しよう。

  repeat(c, N-2) {
    repeat(j, K) {
      repeat(k, K) {
        repeat(i, K) {
          if ((i!=k)&&((i<j&&j>k)||(i>j&&j<k))) {
            dp1[c+1][j][k] += dp1[c][i][j];
            dp1[c+1][j][k] %= MD;
          }
        }
      }
    }
  }

数式の式変形と同じことをしていく。🎍判定関数の、iに依存しない比較ならiのループ外に出せるはず。orは、以下のように実装を重複させれば展開出来る。

    repeat(j, K) {
      repeat(k, K) {
        if (j > k) {
          repeat(i, K) {
            if ((i!=k)&&(i<j)) {
              dp1[p2][j][k] += dp1[p1][i][j];
              dp1[p2][j][k] %= MD;
            }
          }
        }
        else if (j < k) {
          repeat(i, K) {
            if ((i!=k)&&(i>j)) {
              dp1[p2][j][k] += dp1[p1][i][j];
              dp1[p2][j][k] %= MD;
            }
          }
        }
      }
    }

repeat(i, K) の中に (i<j) があるということは、repeat(i, j) のように出来るはず。

    repeat(j, K) {
      repeat(k, K) {
        if (j > k) {
          for (int i = 0; i < j; ++i) {
            if (i != k) {
              dp1[p2][j][k] += dp1[p1][i][j];
              dp1[p2][j][k] %= MD;
            }
          }
        }
        else if (j < k) {
          for (int i = j+1; i < K; ++i) {
            if (i != k) {
              dp1[p2][j][k] += dp1[p1][i][j];
              dp1[p2][j][k] %= MD;
            }
          }
        }
      }
    }

(i != k) については、後から(i == k)の値を引けば良いです。

    repeat(j, K) {
      repeat(k, K) {
        if (j > k) {
          for (int i = 0; i < j; ++i) {
            dp1[p2][j][k] += dp1[p1][i][j];
            dp1[p2][j][k] %= MD;
          }
          dp1[p2][j][k] -= dp1[p1][k][j] + MD;
          dp1[p2][j][k] %= MD;
        }
        else if (j < k) {
          for (int i = j+1; i < K; ++i) {
            dp1[p2][j][k] += dp1[p1][i][j];
            dp1[p2][j][k] %= MD;
          }
          dp1[p2][j][k] -= dp1[p1][k][j] + MD;
          dp1[p2][j][k] %= MD;
        }
      }
    }

シンプルになった。dp1[p1][i][j] は k に依存しないので、kのループの外側で計算することが出来るはず。

    repeat(j, K) {
      ll sum1 = 0;
      for (int i = 0; i < j; ++i) {
        sum1 += dp1[p1][i][j];
        sum1 %= MD;
      }
      ll sum2 = 0;
      for (int i = j+1; i < K; ++i) {
        sum2 += dp1[p1][i][j];
        sum2 %= MD;
      }
      repeat(k, K) {
        if (j > k) {
          dp1[p2][j][k] += sum1;
          dp1[p2][j][k] %= MD;
          dp1[p2][j][k] -= dp1[p1][k][j] + MD;
          dp1[p2][j][k] %= MD;
        }
        else if (j < k) {
          dp1[p2][j][k] += sum2;
          dp1[p2][j][k] %= MD;
          dp1[p2][j][k] -= dp1[p1][k][j] + MD;
          dp1[p2][j][k] %= MD;
        }
      }
    }

k のループの下にはループが無くなり、全体の時間計算量は $O(NK2)$ になりました。

4

数列の合計も上記と同様に計算できます。先程の「🎍を満たすものの個数」の計算結果を利用することに気づけないと、ここではまると思います。

冗長になりそうなので省略。

提出

#669259 (C++14) No.1513 simple 門松列 problem - yukicoder

上の提出は使っていない変数があるので注意

AtCoderLibrary Lazy-SegmentTree 基礎実装例集

色々実装してみたので、ここに置いておく

対象読者

  • 十分な実装時間があれば簡単な機能をもった(例:範囲加算・範囲総和取得など)遅延セグメント木を実装できる
    • ATLのlazy_segtreeを使う前に、自分で抽象化されていない簡単な遅延セグメント木を作ってみることを強くおすすめします。
    • 抽象化遅延セグメント木特有の考察や、内部実装の理解を前提としたインターフェースが多い為です。
  • AtCoderLibrary をコンテスト時間内で読んで分からなかった人向き

全部説明されていなかったら、それは自分の説明力不足です。すみません。

遅延セグメント木を使う上での注意

  • 制限に注意。
    • うっかり何でも出来ると勘違いしてしまいがちだが、前提を満たさない関数を実装すると、動かない。モノイドとか
      • 適切に状態をもたせると、前提を満たす設計が出来るようになる場合がある。本記事では、その例を掲載。
    • 遅延セグメント木より汎用性の高い配列型データ構造に平方分割があります。各クエリの計算量がO(sqrt(N))なので注意
続きを読む

yukicoder No.1104 オンライン点呼

概要

yukicoder.me

  • 社員全員はスター型のリモート会議サービスに参加している。お互いの声が聞こえる。
  • 遅延があり、社員iは、情報が社員からサーバに届くのにA[i]秒、サーバから社員に届くのにB[i]秒掛かる。
  • 社員jは、j-1の数字が聞こえたら or j-2の数字が聞こえてK秒経過したら、jを発声する。
  • 社員1が発声してから全員が発声し終わるまでかかる時間

DP

次のような配列を考える。

dp[i] = 社員iが最初に発声する時間

dp[i-1], dp[i-2] の最適解が求まっていれば、dp[i]の最適解も求まる。 前から順に眺めていけば、配列全体の最適解は得られる。

  fill(dp, dp+N, inf);
  long long ans = 0;
  dp[0] = 0;
  repeat(i, N) {
    const auto d = dp[i];
    chmax(ans, d);
    chmin(dp[i + 1], d + A[i] + B[i+1]);
    chmin(dp[i + 2], d + A[i] + B[i+2] + K);
  }

社員全員の最初に発声する時間が得られたので、配列の最大値が問題の答えとなる。

計算量はO(N)

yukicoder.me

codingame Unleash the Geek に軽く参加した

とりあえず。

問題概要

  • 鉱石を集めて回収する。
  • ただし、鉱脈のある場所は分からない。
  • レーダを配置することで、距離4以内の鉱脈が分かる
  • 爆弾も設置できる。爆弾を設置した場所を掘ると爆発する。隣接して置くと誘爆する。
  • 相手のロボットが何を持っているか分からない。
  • HQから遠いほど、鉱脈は多く存在する。

成績

Gold 😫

最後の週末でガリガリ書きましたが、Legend間に合わず。

ちゃ、ちゃんと参加してたらLegendary行ってたもん!!

コードも800行とかなりコンパクト。手抜きともいいますが。

続きを読む

AtCoder Beginner Contest 108 - C Triangular Relationship

これ本当に300点ですか???

概要

N 以下の正の整数の組(a, b, c)であって、a+b, b+c, c+a が全てKの倍数であるようなものの個数を求める。

考察

1

%を剰余演算の記号とする。

制約が N <= 2*105なので、aだけを全探索するような実装が予想される。 なので、aを定数と見立てて、b,cのパターンの数を求めるような実装がしたい。

まず、b+cがKの倍数であるようなものについて考察する。 bをx軸、cをy軸に取って、b+cがKの倍数となるような点をマークしていくと、斜めの直線が複数現れると思う。

ここにaの制約を入れたい。a+bがKの倍数なので、bをKで割った余りは(K-a)%K*1でなければならない。 cも同様。

b%K=(K-a)%K となる直線たちと c%K=(K-a)%K となる直線たちを引く。3つの直線が交わる点の個数が、aを固定したときのb,cの個数となる。

実装

int main() {
    int N, K;
    scanner >> N >> K;
    ll ans = 0;
    
    iterate(a, 1, N+1) {
        const int x = K - a%K;
        if ((x + x)%K != 0) continue;
        const ll n = (N - x)/K + 1;
        ans += n*n;
    }
    
    printer << ans << '\n';
    return 0;
}

いや確かにシンプルですけど…

*1:0以上K未満とする

codevs reborn に参加しました

しました。

codevsとは

codevs.jp

ゲームAIを作って強い人が優勝。

tl;dr

結果

  • 17/112位
  • ずっとシルバー(30位以内)をキープしていたようなしていなかったような*1
  • 前回参加した、codevs for student(以下codevsFS)は社会人含めて27~30位ぐらいだったので、多少は上がったかな*2

戦略

  • ビーム風サーチ(幅20+時間ループの通称chokudaiサーチ)で探索。
  • 60点程度(ojama3行)の連鎖またはスキルをなるべく早く撃つ。
  • 長めのチェインを組もうとする相手に強いが、主にスキルを使う相手にとても弱い。

*1:今回は事前に体験版が配布されて、予選開始前からある程度骨組みを組んでいたため、始めからシルバーランクに座っていました

*2:codevsFSと似たルールなので、組み方は多少知っていました。

続きを読む