naoya_t@hatenablog

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

〈ARC/AGC埋め〉600点問題 (ARC 079 E,081 E,097 E / AGC 001 C,003 C,008 C)

ARC/AGC埋め再開
600まで埋まった*1
f:id:n4_t:20180813025040p:plain:w480

ARC 079 E - Decrease (Judge ver.) (600)

ARC 079 Dの類題。(どちらも600点)
Dでは回数がK回になるaを1つ例示するのに対し、Eではaが与えられ回数を計算する。

0 \le a_i \le 10^16+1000 なので愚直にシミュレーションするのは無理。

  • 1回の操作で1つが-N、他全てが+1される、ということは、相対的に見ると1つを-(N+1)するのに等しい。(最初はベースライン=0で、ベースラインが1つ上がっていく)
  • Σfloor(a[i]/(N+1))回の操作で、全てを ベースライン + a[i] mod (N+1)、即ち [ベースライン, ベースライン+N] の範囲に収めることができる。(最小と最大の差がN以下になる)
    • この操作が1回でも発生するのは N+1 以上の項が存在する場合である
    • というか、N-1 を超える項目が存在しない(=操作が不要な)場合には何も起こらない。
    • とりあえず最小と最大の差はN以下に収めることができたが、ベースラインはかなり高いところ(最大で2e14ぐらい)にあったりする。
  • 適当な高さ(2Nぐらい)まで全体を下げよう。最小と最大の差がN以下なら、N回の操作ですべてを-1することができる。これで最小が2Nになる辺りまで下げる。
  • あとはpriority_queueでも使って愚直にシミュレーションしても余裕

→AC 40'03''
https://beta.atcoder.jp/contests/arc079/submissions/2997872 1ms

解説より
  • Σfloor(a[i]/N)回ずつ全体を下ろしていく
    • 指数的に減って行く。高々4450回とかで操作終了

→AC
https://beta.atcoder.jp/contests/arc079/submissions/2997997 3ms


ARC 081 E - Don’t Be a Subsequence (600)

最初suffix arrayを求めてて…いやこれ部分列を網羅してないじゃん…没
Aが高々200000字だから、高々4文字(26^4)で網羅できるのでは、とか思って、4文字以内の全パターンで存在しないものを探すのを書いてた
→WA

なんでって
例えば、"abcdefghijklmnopqrstuvwxyz" を10個連ねた260文字の部分文字列が来たら
10文字以内のいかなる文字列もこの中に部分列として存在してしまう
ということは、(20^5/26≒7692.3なので)最大7692文字まで封じられる可能性がある。
(逆に、答えは高々7693文字である、とも言える)

1時間経ったので解説を読むよ

解説より
  • 右から見て、"abcdefghijklmnopqrstuvwxyz" の全文字が揃う最短suffixを削っていく。
    • ある位置が何回目のsuffixブロックに含まれているかメモっておく
  • K回削れるとしたら、答えはK+1文字(そこまでは分かる)
    • 1文字目は、K回削った残りの文字列(ここにはa-zは全部揃っていないはず)に含まれない文字の中で一番若いやつとして、
    • 2文字目以降を、K回削った各suffixの最初の文字として取ることでK+1文字解が出来る
      • 1文字目を上述の通りに選んだ場合に必ず何らかのK+1文字解ができることを保証
    • 但しこれが辞書順最小とは限らない
  • K+1文字の、辞書順最小の文字列を構築していく
  • 1文字目は(上述のとおり)K回削った残りの文字列に含まれない文字の中で一番若いやつ
    • この文字は、必ず「最後に削ったsuffixブロック」にある
  • あとK文字を何にするか、a-zの中から(1文字ずつgreedyに)選べるらしい
  • 候補文字が現在位置以降で見つかるのはどこか。解説によると、決定済みの最後の文字が含まれるsuffixブロックの次のブロックならその文字は使っていいらしい
    • どゆこと?
    • どのsuffixにもa〜zのすべての文字が少なくとも1回含まれるわけだから、遅くとも次のブロックで必ず見つかる。早ければ同じブロックで見つかる。
    • 同じブロックで見つかってしまった場合(例えば2文字目として)、まだ未消化な(K−1個の)suffixブロックから任意の文字列が作れてしまうので、決定済みの2文字をprefixとする任意のK+1文字の文字列が「Aの部分列として存在」してしまい、その後に何をどうしようとアウト
    • なので同じブロックに見つからないような文字を選ぶしかない、ということか
    • こうして進んで、K文字目を選んだ時点で最後のsuffixブロックにいるはず。(最後の1文字はそれ以降に見つからない文字ということになる)

→AC
https://beta.atcoder.jp/contests/arc081/submissions/2998694

AGC 001 C - Shorten Diameter (600)

(グラフとか木とか本当苦手だなあ)

適当な頂点を選んでそこから一番遠い葉を求め、その葉から一番遠い葉までの距離がその木の直径
(すべての点について)ある点を含む直径Kの木の可能性を全列挙?
O(N^3)ではアウト。O(N^2logN)とかO(N^2)とかに抑えないと駄目だ

30分考えて解けなかったので解説を読む

解説より
  • Kが偶数のとき:ある頂点から距離K/2を超えるものを全て捨てる、を全ての頂点について試して最小を答える
  • Kが奇数のとき:ある辺の両端からそれぞれ距離(K-1)/2を超えるものを全て捨てる、を全ての辺について試して最小を答える

なるほど
(ていうかそういう解法どこかで見たことあるぞおい)
→RE
https://beta.atcoder.jp/contests/agc001/submissions/2999492

K=1のときにバグるとか?
違う
辺の数はN-1個しかないのにN回ループしててRE
直して
→AC
https://beta.atcoder.jp/contests/agc001/submissions/2999505

ARC 097 E - Sorted and Sorted (600)

(これは出場時に1WA済の問題)
左から黒i個白j個まで充填済み、みたいな状態のNxNのDPをやればいいのは分かるんだけど
(二次元テーブルの)上と左の隣接項からの更新をO(1)ないしO(logN)でどうやったらいいかが分からず
30分以上経ってたので解説を読む

解説より

"左k個にあるi以下の黒いボールの個数" などを前計算する

とある。なるほど…それなら出来そう。(でも、"左k個にあるi「以上」の黒いボールの個数" のほうが使いやすそう)
前計算はO(N^2)で可能。
あとは、
f(黒i白jまで左に充填済み) = min(
 f(黒i白j-1まで左に充填済み) +
  k=白jの位置として、(左k個にあるi+1以上の黒いボールの個数) + (左k個にあるj+1以上の白いボールの個数),
 f(黒i-1白jまで左に充填済み) +
  k=黒iの位置として、(左k個にあるi+1以上の黒いボールの個数) + (左k個にあるj+1以上の白いボールの個数)
)
みたいな要領で隣接項との関係式を作って更新していくとO(N^2)でdp[N][N]辺りに答えが出来てるはず
→AC
https://beta.atcoder.jp/contests/arc097/submissions/3000011

教訓

こういう前計算とか、lower_bound() なんかを使った二分探索でO(logN)で求めることを考えがちだし思考が一次元配列にとどまりがちだけど、二次元のテーブルを用意しておいてO(1)で使う、みたいな発想を積極的に取り入れていくべき。

AGC 003 C - BBuBBBlesort! (600)

可能な限り3連続のほうを使いたい、と

  • 各項の行くべき所が偶数番目か奇数番目かを調べる
    • ソートして座標圧縮して%2
  • 行くべき所の偶奇が間違っている箇所がいくつあるか(偶数側がk箇所なら奇数側もk箇所なはず)
  • 元の配列の偶数番目の各項内、奇数番目の各項内では3連続の反転を使って自在に移動できる
    • ので、例えば左側にそれぞれのk個ずつを固めることが可能
    • そうすると、k回の2連続区間反転で偶奇は合わせられる
    • あとは3連続区間反転で行くべき所に持って行けばいい
  • ということは答えはk

→AC (12'18'')
https://beta.atcoder.jp/contests/agc003/submissions/3000074

ちょっとあっけなかった。解説解も同様。

AGC 008 C - Tetromino Tiling (600)

  • T,S,Zは使えない
  • Oは単独で使える
  • I,J,Lはそれぞれ2つずつ組むと長方形になる
  • I+J+L各1個ずつで長方形が出来る

ってのは分かった
O + 2*(I/2) + 2*(J/2)+ 2*(L/2) + (I%2 && J%2 && L%2)?3:0
みたいな感じで
→WA
https://beta.atcoder.jp/contests/agc008/submissions/3000120
intで計算してるからか?long longにしてみる
→WA
https://beta.atcoder.jp/contests/agc008/submissions/3000126
WAの数は減ってるけど
1ポモドーロ経過したので解説を読む

解説より

I+J+L型を使う場合と使わない場合でそれぞれ求めていい方を取る
なるほど…?
例えば Ix3, Jx3, Lx2のとき。
2I, 2J, 2L で組んで終わる(I,Jを1つずつ残す)と 2x4 2x4 2x4 で2x12の長方形が出来上がる。
IJL + 2I + 2J で組む(Lを1つ残す)と 2x6 2x4 2x4 で2x14の長方形が出来上がる。
→AC
https://beta.atcoder.jp/contests/agc008/submissions/3000152

順位表を見たらみんなWA喰らいまくってた...

*1:企業コンは除く