naoya_t@hatenablog

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

Codeforces Round #553 (Div.2)

https://codeforces.com/contest/1151

4/18(木) 24:35-26:35
多分寝るだろうと思ったけど出た
残り4秒で提出したEが通って
5完240位(rated内167位)
f:id:n4_t:20190419032935p:plain:w500
rating 1834→ 1913 (+79) Became Candidate Master
f:id:n4_t:20190419034040p:plain:w500
Div.1昇格!紫になった!
f:id:n4_t:20190419034057p:plain:w500

f:id:n4_t:20190419043237p:plain:w500

A. Maxim and Biology

全ての位置で4文字比較
Pretests passed / AC 06:30

B. Dima and a Bad XOR

dp[n][0..1023] = j なら最後に使ったのが a[n-1][j]、みたいな
dp[N][1..1023] > 0 な項があればそこから経路復元
Pretests passed / AC 21:01

C. Problem for Nazar

  • f(x)=(最初から)x番目まで見たときの合計(の剰余値)
    • 奇数がいくつ偶数がいくつあるかに帰結。先頭の奇数n個の和はn^2、偶数n個の和はn(n+1)
    • 簡単な2冪区間のループで(O(\log N)で)求まる
  • 欲しい答えはf(l) - f(r-1)

Wrong answer on pretest 6 45:30

  • f(l)-f(r-1)した結果をMODしてない
  • f(x)の中もMODちゃんとしてない箇所がある

直して
Pretests passed / AC 47:16

D. Stas and the Queue at the Buffet

w = N-1として
$$ \sum_{i=0}^{N-1} a_i\cdot k_i + b_i(w - k_i) = \sum_{i=0}^{N-1} (a_i - b_i)k_i + w\sum_{i=0}^{N-1} b_i $$

    • b_i\cdot wの部分は定数なので外に出せて
    • k_i[0..N)が来る
  • a_i-b_i をソートして大きいやつから使う

Pretests passed / AC 55:03

E. Number of Components

方針は割とすぐに立った

  • (+)それぞれの数が何回ずつ出てくるか集計。それが何回ずつ使われるか
    • kは [0..k]から[k..N)までの区間で使われる。
  • (-)隣接する項目は島を減らす。それぞれ何回ずつ使われるか
    • aとbが隣接するとき、a<bなら [0..a]から[b..N)までの区間で使われる

あれ?…サンプル3で数が合わない(出力は102、正答は104)

原因がわからない
先にFを見る

戻って
まだ20分弱ある

ナイーブなシミュレーションを書いて
どこで数がずれてるか探る
最初のkの使われる回数のところでkの集計値を使ってなかった…(サンプル1,2が合ってたのは偶然)

残り数十秒で提出→接続に失敗(混んでる?)
焦らずリロードして残り4秒で提出に成功
Pretests passed / AC 1:59:56

F. Sonya and Informatics

問題読んだ

  • 0と1だけでソートされると左に0、右に1が固まる
  • 0はどの0でも一緒 / 1はどの1でも一緒
  • 0-1の交換 (+1) / 1-0の交換 (-1) / 0-0の交換 (±0), 1-1の交換 (±0)
    • (±n)は転倒数の変化
  • ... 隣り合う0/1の個数を追尾しないとわからなくない?

この辺りまで考えてEに戻る

f:id:n4_t:20190419034305p:plain:w1