buyoh.hateblo.jp

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

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人居たり,すれ違ったりすることは出来ない.

続きを読む

LeetCode - Subarrays with K Different Integers

解けなかった

問題

leetcode.com

K種類の整数から構成される連続部分配列をgoodと呼ぶ.

入力から与えられる配列の連続部分配列のうち,goodな配列はいくつ存在するか?

続きを読む

NIKKEI Programming Contest 2019 - E Weights on Vertices and Edges

問題文

atcoder.jp

頂点重みX 辺重みY の無向グラフが与えられる. 次の条件を満たすように,なるべく少ない辺を削除したい.

削除されていない任意の辺について、その辺を含む連結成分の頂点の重みの総和が、その辺の重み以上である。

続きを読む

Code Festival Team Relay (Parallel) - D 数直線

雑でごめんなさい

問題

cf18-relay-open.contest.atcoder.jp

数直線上に N 個の点があり、i 番目の点の座標は x_i です。また、N 個の整数 w_i が与えられます。

次の条件を満たす点 p の座標を求めてください。条件を満たす点が複数ある場合は、最も座標が小さいものを求めてください。

条件: 「1≤i≤N を満たす整数 i に対する (p から点 i までの距離) × w_i の最大値が最小になる。」

続きを読む

COLOCON -Colopl programming contest 2018- D すぬけそだて――トレーニング――

この程度の愚直DPが間違ってたのダメ

問題文

beta.atcoder.jp

  • スタミナとよばれる概念があり,0で空,Xで満タンである.時刻1単位でスタミナは1回復する
  • 時刻0にてスタミナはXである
  • T_1..T_NからK個のタイミングを選んで,スタミナを0にして,スタミナを減らした分だけ経験値がたまる
  • 全てのK∈1..Nについて,獲得できる経験値の最大値を計算する.
続きを読む