buyoh.hateblo.jp

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

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と似たルールなので、組み方は多少知っていました。

続きを読む

Codingame Code a la Mode に参加した

結果

Legendary到達.38/1543.Legendary到達後はコード触ってない(触ると落ちそうだったので).

問題概要

客が常に3人居て,何か料理を注文している.適切な料理を出すと,スコアを獲得する. なるべく高いスコアを獲得したい.

料理は,皿と複数の食材から構成される. 例えば,「皿+アイスクリーム+ブルーベリー」,「皿+タルト+切られたいちご+クロワッサン」など.

一部の食材は調理が必要. 例えば,「切られたいちご」は「いちご」を「まな板」に持っていくことで「切られたいちご」を得る. 「クロワッサン」は「生地」を「オーブン」に持っていき,一定時間待ち,取り出すことで「クロワッサン」を得る. 「オーブン」は,長時間放置すると焦げてしまう. タルトは特に大変.

キッチンには自分を含め2人のプレイヤーが居る.同じマスに2人居たり,すれ違ったりすることは出来ない.

続きを読む