naoya_t@hatenablog

いわゆるチラシノウラであります

Dwango Programming Contest V / 第5回 ドワンゴからの挑戦状 予選

レーティング変動ありという言葉につられて参加。

11/24 20:00-22:00
AB-d-

問題はドワンゴの中の人が作ったらしい。制限時間がすべて2.525秒になっているのが特徴的。

Cを飛ばしてDの部分点(500)を取りに行った。
レーティング微増:1749→1754(+5)

A - Thumbnail (200)

平均とるとintじゃなくなるのでintで演算できるようにN倍したもので処理
→AC 3:10
https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3652918

B - Sum AND Subarrays (400)

  • N(N+1)/2≦500500通りの部分和をまず全て求める
  • 上のビットから決めていく。(あるビットがK個以上あれば採用。採用する場合、そのビットが立っていない数をすべて捨てる。採用しない場合は何もしない)
    • 10^9\cdot 1000=10^{12}\le2^{40} というわけで高々40ビット。
    • 40×N(N+1)/2≦40×500500=20020000だし余裕では

vector二本で交代させながらやろうとしてたんだけどうまく更新されていかなくて焦る
(結局使わないやつを0にして進んだ)
それで時間かかっちゃったけど
→AC 32:45
https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3655395

C - k-DMC (600)

  • Mに注目して左のDと右のCの数を距離 d,(k-1)-d の範囲内で → O(N^2)無理〜
  • 左からdequeにDの位置入れていって、DMが出来たらどこからのDMがいくつあるかを別のdequeに入れていって →これもO(N^2)
  • DPでどこからのD/DMかを記録しながら→O(N^2)無理

結構悩んだけど光が見えなくて
飛ばす

コンテスト終了後

クエリのたびに1回1回普通にDPしてみる?
D,DM,DMCの状態の数を普通に足しこんでいくのだけれど
賞味期限の切れたD,DMの数を引いていくことが出来れば…

出来るじゃん
(k経過したDをdp[D]から引く、その位置から現在地点の手前までのMの個数をdp[DM]から引く。dequeに消去予約タスクを積んだ。Mの個数についてはあらかじめ累積和を取っておいた)
→TLE
https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3660491
ほよ
最悪ケース作って試してみたらローカルで10秒とかかかってるし
dp, dp2 を入れ替えながら回すの遅いから dp でインデックスだけ入れ替えるようにして
→AC
https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3660538

解説読んだ

deque使うまでもなく、S[i-k]=='D'を調べれば済むこと。
Mの個数も尺取り式に数えることができる。

D - Square Rotation (800/500)

  • x座標 y座標をそれぞれmod Dして、D^2 のレイヤーに分ける
    • それぞれのレイヤー上でしか動けない
    • 好きな形に持っていくことができる(これが言えるか暫くノートの上で試してた)
    • レイヤー毎に、可能なら正方形に収めるのがベスト。割り切れずに短辺長辺が出来てしまうのは良い
  • 囲む正方形の原点をD^2箇所試す(↑→な座標系とする)
    • 各レイヤーの正方形を第1象限に置くのだけれど、原点に最も近い可能な場所に置く。
    • 短辺長辺の長さが違う場合、囲む正方形が小さくなるほうを選ぶ
    • 全レイヤーを囲める正方形の大きさを調べる。で、その最小値が答え
    • O(D^4)だけどD=30なら81000だし余裕っしょ
      • D=1000だと10^{12}で無理ー

→AC(部分点500) 111:51:22
https://beta.atcoder.jp/contests/dwacon5th-prelims/submissions/3658974

残り9分弱で部分点が取れて良かった。

E - Cyclic GCDs ()

開いてない