naoya_t@hatenablog

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

〈AGC埋め〉700点問題(AGC 014 C, 015 C, 016 B/C, 020 C, 022 C, 025 C, 027 B, 028 C)

師走ですが埋めていきましょう

今月はAGCが2本あるし、年明けにはDDCC本選とか、あと日経×AtCoderのコンテスト(全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019)が開催されるそうなので力をつけておきたいところ。
nikkei2019-qual.contest.atcoder.jp

追記(12/10)

埋まった!これでAtCoderの700点までの問題(企業コンの問題を除く)を制覇した!
f:id:n4_t:20181210211520p:plain

12/5(水)

AGC 014 C - Closed Rooms (700)

  • 最大K個進んで、壁を最大K箇所崩す
  • 最大K個進んで、壁を最大K箇所崩す
  • ・・・

10分ぐらい考えてひらめいた。これは

  • 最大K個進む
  • 壁を最大K箇所崩して、最大K個進む
  • 壁を最大K箇所崩して、最大K個進む
  • ・・・

のように考えたほうが良いのでは?

  • 壁を最大K箇所崩して、最大K個進む

のセットは進めるのも崩せるのもK個だから、進みたい方向に前もってK個崩せばK個進める。とすると、

  • 最初に(壁を崩す前に)行けるだけ行ける範囲のどこかから(ここまでで1手)
  • そこからK個ずつ進んで最も早く外側に出られる場所を探せばいい

壁を崩しながら外側まで何手で行けるかは一番外側かのマンハッタン距離dに対しceil(d/K)で求まるので求めておいて、最初に行ける範囲の中で一番手数の小さいのが答え、では

→WA(#1)
https://beta.atcoder.jp/contests/agc014/submissions/3722326
あ、
スタート地点から壁を壊さずに行ける範囲じゃないと駄目だよ
UnionFindしてSと地続きか見て
→WA(#2)
https://beta.atcoder.jp/contests/agc014/submissions/3722374
あ、SからK以内じゃないと駄目じゃん
別にUnionFindいらなかった。BFSして
→AC
https://beta.atcoder.jp/contests/agc014/submissions/3722476
わーい(46分 + 2ペナルティ。700点問題の自力ACタイムとしては悪くない)

解説読んだ

同様

12/7(金)

AGC 015 C - Nuske vs Phantom Thnook (700)

  • UnionFindで連結成分を調べておく (O(NM))
  • それぞれの島がどのクエリに入るか… O(NMQ)かかるじゃんそれ
  • クエリの時に行ごとにO(1)で求まる何かがあって、それを使って合計することでO(NQ)でギリ行けるみたいなのが出来る?
    • 同じ連結成分に属していても、ある行で複数回(バラバラに分かれて)出現しているかもしれない。1行に含まれる島の数は高々M/2種、とはいえお手軽なテーブルとして用意しておく計算量も必要メモリ量もコンパクトにできない

スタバで40分弱考えてたけど計算量が減らない…

そのあと家でそろそろ諦めて解説読むかとか思いながら問題読み返したら

もとのグリッドで同じ成分に属するマスが、異なる成分に属するかもしれないことに注意してください。

はぁ… 全体で同じ連結成分に属しているものは二重に数えてはいけない、みたいに問題を難しくしてた><

でもそれなら簡単じゃない?

  • 青マスの個数を二次元いもす
  • 水平方向に隣接する箇所をチェックしてそれを二次元いもす
    • 具体的には、あるマスが青マスだったときに、その右も青マスなら1
  • 垂直方向に(〃)
    • 同様に、あるマスが青マスだったときに、その下も青マスなら1


そこまで準備するのはO(NM)でいける

クエリ範囲の青マス数・水平隣接数、垂直隣接数がそれぞれO(1)で求まる(二次元いもすの(左上) - (左下+) - (右+上) + (右+下+) ってやつね)のでクエリ全体でO(Q)

→AC
https://beta.atcoder.jp/contests/agc015/submissions/3733469

解説読んだ

同様

教訓

問題よく読め

12/8(土)

AGC 016 B - Colorful Hats (700)

全部でc種類の帽子があるとする

  • 全員cと言う:どの種類も少なくとも2つある。ということは1≦c≦floor(N/2)
  • 全員c-1と言う:すべての帽子が1つずつしかない。ということはc=N
  • cと言う猫とc-1と言う猫に割れる:c-1と言った猫が被っている帽子は1つしかない種類のもの。cと言った猫が被っている帽子は2つ以上ある種類のもの。ということは... num(c-1)+1≦c≦num(c-1)+floor(num(c)
  • それ以外:あり得ない

それだけのこと?

とりあえずサンプルケースは全部通ったし投げてみた

→AC 42:15
https://beta.atcoder.jp/contests/agc016/submissions/3733815
自力で取れた

解説読んだ

同じ

AGC 016 C - +/- Rectangle

h×wの部分行列の1箇所を-hwに、それ以外を+1にすればそのブロックは合計-1で、
Hがhで、Wがwで割り切れてしまったら駄目だけどそれ以外ならカバーできる?
(埋めてみて全体の合計が正かどうかで答えればよいかな)
→WA(1)

どうしたらいいか思いつかない
1ポモドーロは経ってるし解説読むか?
とりあえず、テストケースを1つ覗いてみた
1 500 1 499 で落ちてる。自分のだとNoだけどこれはYesにできる。
なぜ?両端を+2にして、両端を覗いた498個の合計を-3にすれば良さそう。
(+1, -hw)じゃなくて (+2,-1-2(hw-1)) にする感じ。
→WA(2)

部分行列が横に1個ならそれで行けるかもしれないけど
(+2 -3) (+2 -3) ... が 249個並んだ後に+2では足りない。
正の数としては250以上が必要なのでは。

面倒くさいから(+501 -1-501(hw-1)) で組んでみた
→AC
https://beta.atcoder.jp/contests/agc016/submissions/3734064

解説読んだ

大体同じなんだけど
h×wのブロックじゃなくて1×wが負になるブロックをh個積んでも同じ。(なるほど!!)

累積和(s_0,...s_W)を構築して、そこから(a_0,..a_W-1)を復元する形で解いてる
その累積和の満たすべき条件は

  • s_W > 0
  • s_i > s_i+w

Wがwの倍数ではないのでこれは常に構成できる、とあるけどそうなの?

  • {s_i} からwおきに要素を取ってきた部分列が単調減少
  • だけど最後は正

例えば

  • s_0 = 0, s_kw = -k
  • s_1 = c, s_2 = 2c, ... s_w-1 = (w-1)c

みたいな感じで、s_Wが正になるようなc,kを選べばいいのか。

  • W=aw+b のとき s_W = -ak+bc > 0
    • k=1とすると -a+bc > 0
    • なので c > \frac{a}{b} になるように選べばよい

なるほど…

AGC 020 C - Median Sum (700)

2^{2000}-1通りある中の中央値とかどう取り出すんだ

  • 一番大きいa_iを抜いたもの、抜いてないもの、に分けてみる。
    • 一番大きいa_i抜きの最大 < 一番大きいa_i入りの最小、なら一番大きいa_i入りの最小がmedian
    • こんな感じで大きい順に上から1つ2つ抜いて何かが見つかる?(3つは無理だけど2つで決まるなら行ける)
      • a_iが全部1だったら?無理でしょ
  • 部分集合の値の合計は高々N\max a_i\le 4\cdot10^6
    • 二分探索的な方法で見つかったりする?
    • いや何を探索しろと
  • 合計いくつになるものがいくつあるか、DPで求まったりする?
    • O(N^2\max a_i)で行ける?
    • 値は2^{2000}とかのスケールになるし多倍長計算でないと無理

40分ぐらい考えた末に寝落ち

解説読んだ

読んだだけでは何言ってるか分からん…
ノート開いて実例を挙げながら再読。

部分列を、a_iが含まれる場合i桁目を1、含まれない場合0として表したN桁の二進数で表現したとすると

  • (01010, 10101)
  • (10011, 01100)

のようにビットを反転した(1の補数をとった)表現にお互いがなるような2つの部分列同士でペアを作ると言っているわけね。(「自分自身と相補的な部分列」ってそういうことか)

で、空集合を含み、こういう部分列ペアが2^{N-1}個できる、と。
1の補数で余すことなくペアを組めるというのがなるほどポイント。

小さいほうをP_i, 大きい方をQ_iとする(等しい場合もありうるのでP_i\le Q_i)と
P_i + Q_iは必ず(11111)なので、{a_i}の全N要素の和(=S_{2^{N-1}})に等しくなる。

ということは、{a_i}の全N要素の和を2で割ったH=\frac{S_{2^N-1}}{2}を考えると
P_i\le H\le Q_i
が必ず言えることになる。
これの意味するところは、

  • すべての部分列ペア(全部で2^{N-1}個)は要素の和を座標軸に並べると、Hを中心としてP_iQ_i点対称な位置関係になる
  • S_{2^N-1}が偶数の場合:
    • Hは整数で、P_i(ないしQ_i)の要素の和合計がHになるものがあるならMedianはその中にあり、従ってHがMedianになる。
    • そうでないなら(奇数の場合同様)Hの上でH直後に来るものがMedianになる。
  • S_{2^N-1}が奇数の場合:
    • Hが整数ではなく、Hの上下にそれぞれ2^{N-1}個ずつの部分列(空集合を含む)が来る。
    • 空集合を抜くと、Hの下に2^{N-1}-1個、Hの上に2^{N-1}個来ることになるので、Hの上のH直後に来るものがMedianになる。

というわけで、合計として(1〜N\max a_iの範囲内で)ありうる数を時間内に求めることができるなら、Hから上を見て最初にありうる数を答えればよいことになる。

このありうる数を求めるDPはO(N^2\max a_i)の計算量になって一見間に合わなそうなんだけど、bitsetを使うことで計算量をざっくり\frac{1}{64}に落とすことができる。
(計算はshiftしてorして、の繰り返し)

実装してみて
→AC
https://beta.atcoder.jp/contests/agc020/submissions/3736800

12/9(日)

AGC 022 C - Remainder Game (700)

  • a_i < b_i は不可能
  • a_i == b_i の時はノーコスト
  • なので a_i > b_i のケースについてのみ考えればよい

あるビットが必要か否かを上から決めていく、みたいな定番のやつで行ける?(いやどうやって?)

WFでaからbへの可能な最小コストの遷移を求める、というのは思いついた (i%k=jになるi-jにコストkの辺を張ってからWFを回す)
WFのテーブルで各 a_i→b_i のコストをルックアップして足し込んだのが答え?

サンプル2〜5は行けるけど1が162になる…
b[i]が0になるものを特別扱いすべき?

0になるものがある場合、それを抜いて出した答えを使って0になるものが処理できるならそのまま、できないなら 2(=2^1)を足して、サンプルケースは通るようになったので提出してみる

→WA(1)
https://beta.atcoder.jp/contests/agc022/submissions/3748928

時間切れなので解説読むか

解説読んだ

あるビットが必要か否かを上から決めていく方式だった。
使っていいkの集合を限定してその都度WFを回せばいい…なるほど…WFを50回やる(からO(N^4)になる)というのは考えつかなかった(というか自分に許せなかった)。
そこまで分かれば解けそう

サンプル1とか524448なんて数字が出てくるけど…おや
k=19を使わないと解けない?なんで?19を0にできないから
そんなことないはず、最悪k=1を使えばどんな数でも0にできるのだから

あと、WFでコストを足し込む時は論理ORじゃないと駄目だよね
(適当な大きい数もORを使うなら適当な大きい数じゃなくてLLONG_MAXで大丈夫だ)

ごにょごにょ直して、
サンプル2〜5は行けるけど1が162になる…(またか)

どこで引っかかっているか見たら、19→0にするのに19→5→0 (kに7と5を使う)という経路が取れないケースがあった。(WFの回す回数をケチろうとしたせいだった)
直して
→AC
https://beta.atcoder.jp/contests/agc022/submissions/3764775

あと3問!

AGC 025 C - Interval Game (700)

  • 左端、 右端でそれぞれソートしてgreedyに遠いやつを取っていく作戦
  • サンプルケースはとりあえず3つとも通る

→RE
https://beta.atcoder.jp/contests/agc025/submissions/3765650

  • 左右の使用済みインデックスをリセットするのを忘れていた
  • コンパイラの末尾再帰に期待せずループで書いた

→WA
https://beta.atcoder.jp/contests/agc025/submissions/3765760

サンプルケース以外全部WA…

解説読んだ

「青木君はすべての区間を使う必要がないとしてもよい」
「高橋君を右に動かすための区間と左に動かすための区間の2つの役割に、各区間
分けて考えることができる」

高橋くんを動かせなくなったら途中で止めればいいだけか

計算あわない?
左端・右端のソート順が(やりたい事と)逆だ
(前のはサンプルデータの区間がかぶらずに綺麗に並んでるからたまたまうまく行ってた)
直して
→AC
https://beta.atcoder.jp/contests/agc025/submissions/3765884

あと2問!

12/10(月)

AGC 027 B - Garbage Collector (700)

これは出場回(だけど飛ばした問題)。

左からDPで…

  • k-1個目を取った後にk個目を追加するコストは 2(k-2)+2k^2-X
  • いやこれ計算量O(N^2)だし死ぬる
    • 幅を絞れば行ける?
    • いや、くっつければくっつけるほど減っていくのもあるから絞れない

問題再読

  • サンプルケースを見ると、何かを取った帰りに追加で拾っていっている
    • そりゃそうだ、わざわざ往路の荷物を増やす意味はない
    • あ、それだと最後に追加したやつのコストを (2k+1)x[i] で求めることができる
  • 往復回数を決め打ち(k)にした場合、できるだけ遠い所のを折り返しポイントとして、遠い順に拾っていくのがよさそう
    • ... 3rd 3rd 3rd 2nd 2nd nd 折返 折返 折返、みたいな感じ
  • それでも計算式が書きやすくなっただけでO(N^2)のままだよね
  • 単調増加でも単調減少でもないし…
  • もしかして(往復数の)凸関数になってる?
    • そう仮定して三分探索を書いてみる
    • 答え合うじゃん(そして速い)

→AC (20msec)
https://beta.atcoder.jp/contests/agc027/submissions/3768327

解説読む

往復数決め打ちの場合の計算量を累積和を用いて減らしている(なるほど)
それで十分間に合うのか
k台のロボットの作業、みたいに言ってるけどその方が考えやすい?(まあそこはどうでもいいけど)

64bitでオーバーフローする可能性がある?
→k=N=2e5のとき(2e5+2e5)1e9 + 2e5(2x2e5+1)1e9 = 4e14+8e19か(本当だ)

とするとなぜ自分の解答は通ったのか?
→三分探索だと(運良く)オーバーフロー領域の探索が発生しない?(N=2e5,X=1e9,x_i=1e9のサンプルを試すと1≦k≦4でLLONG_MAXを超えるが5≦kだと大丈夫。こういうケースでは1≦k≦4では単調減少なのでこの範囲に解が来ることはありえないのか?)

とりあえず累積和を使ったk全探索解法でも書いてみた(__int128_t を使用)
→AC (32msec)
https://beta.atcoder.jp/contests/agc027/submissions/3768414

三分探索解も累積和で高速化できて
→AC (12msec)
https://beta.atcoder.jp/contests/agc027/submissions/3768746
Fastest取れたか?と思ったけど
f:id:n4_t:20181210144016p:plain
11msecがいました

あと1問!

AGC 028 C - Min Cost Cycle (700)

これはこないだの解けなかった問題だ…

いくつまで使っていいかを二分探索して、それ以上のやつが相手に吸収されうるか調べて…
どれに吸収されるのかフロー使えば解ける?いや解けないかも?解けたとしても計算量多すぎだろ
みたいな所までは考えたんだけど
時間切れ

解説読む

最初意味が分からなくて
アルメリアさんの解説記事がヒントになった
なるほど

団子がN個、櫛がN本あって、リング状に繋がっているやつを適当に外すと -o-, o-, -o, o の4通りに分かれる。そのときあり得るパターンを考えればいい。

1) o- がN個 → いける
2) -o がN個 → いける
3) o- と -o が沢山 → o-を全部繋いで、-oを全部繋いで、その2群をくっつけるには -o- と o が1組必要。それ以上あった場合 -o- と o をくっつけて2群のどちらかに入れればいい。

a_i, b_i を一緒に並べて昇順ソートして、前半N個が4通りのどれに属するか調べる。
1)2)3)の場合そのN個の値の和を答えればいい。

それ以外の場合、すなわち前半N個に o- と -o が沢山あるがそれしかない場合にどうするか。
(この場合、すべての頂点が前半N個に1回ずつ現れる。鳩の巣原理ってやつね)
どこかからジョイント用の -o- と o のペアを持ってこないといけないのだけれど
o になる(両辺とも使わない)頂点を1つ決めて(wとする)、前半N個から頂点wから生えたやつ(必ず1つだけある)を抜いて、後半の最初のやつ(それがw絡みならその次のやつ)を使えばいい。(そのwをN個試して一番いいやつを採用、でいいのかな)

→AC
https://beta.atcoder.jp/contests/agc028/submissions/3770938

700まで埋まった!
f:id:n4_t:20181210211920p:plain