naoya_t@hatenablog

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

〈ARC埋め〉700点問題(ARC 060 E, 068 E, 069 E, 073 E, 076 E)

700点問題埋めるぞ〜
なんか急に難しくなってきたw

8月25日

ARC 081 F - Flip and Rectangles (700)

  • 問題読んで考えてるうちに寝落ち(どこから手をつけたらいいか分からなかったんだけど)
  • 隣接する2行に注目。隣りの行と共通する桁を探す(=隣りの行のxorを取る)。
    • 後にどの桁を何回フリップしようが、この2行の関係はこのxorか、not(xor)のいずれかしかない。
  • xorの結果を見て、隣り合う桁が両方1の所をo、そうでない所をxとする
    • xor=1100111 なら oxxxoo
  • not(xor)についても同様に
    • xor=1100111 なら 0011000 なので xxoxxx
  • この「行間」が取れるパターンは oxxxooxxoxxx のいずれかである
    • o はその回りを囲む4点を同じ色に出来ることを表す
  • 例えば次の行に oooxoo が来たとして、
oxxxoo
oooxoo

で o で出来る最大の長方形は右端の2x2の正方形だが、これは(2+1)(2+1)=3×3の領域を同じ色に出来ることを表している。

上から順に1行(1行間)ずつ、最大面積を更新していく。
(前の行まで繋がっているすべての長方形について、区間と高さの配列を保持しておく)
これだとO(HW^2)だよね、でも1行あたりの連続した o は最大でW/3組なので、H(\frac{W}{3})^2 で9e8になるしギリギリ行けるか?

→WA
いくつかのケース(テストケース番号の若いものばかりだ)でWAが出ている。

隣りの行と全く噛み合わない場合に0が出てるけど、そんなことないよね
1行(ないし1列)だけなら他のすべてを犠牲にすれば揃えられるのだから、max(1×H, 1×W)を下回ることはない。
要するに2x2以上の長方形についてしか考慮に入れていなかったけど、1xHとか1xWも出来るよという話。

そこだけ直して
→AC
https://beta.atcoder.jp/contests/arc081/submissions/3068873
1606ms(ギリギリ感)

ox を隣接行でまとめて処理してたけど、まとめずにやったらプログラムはよりシンプルなのでは?
→TLE
ああ、そうなるとやっぱりO(HW^2)制約が効いてくるのね

解説より
  • 2x2枠の中に黒(白)が奇数個ある箇所〈悪い部分〉は、何をどう頑張っても同じ色にできない
    • 何らかの操作によって新たな〈悪い部分〉が生じることはない
  • だから〈悪い部分〉を含まない長方形領域を考えればいい

うまく操作を行えば長方形 S を選ぶことができることと,S が悪い部分を含まないことは同値です.


そうなの…?

〈悪い部分〉を含まない長方形Sを黒で塗りつぶす操作:

  • とりあえず最初の行が黒くなるように後先考えずに白い桁をフリップする
    • この時点で悪い部分が含まれることはない
    • すると次の行の左2つは黒黒か白白でしかありえない
    • 〈悪い部分〉を含まないのだから、1つ視点をずらして左から2番目3番目を見たときにも黒黒か白白でしかありえない
    • ということは2行目は全て黒か全て白のいずれかになっているはず。全て白なら行フリップして全て黒にする。
    • 以下同様

で、2x2の〈悪い部分〉の中心の格子点に印をつけて、この印を含まない最大面積の長方形を求めればいい、と。

この「印を含まない長方形」は,最大長方形のアルゴリズムを用いると O(HW) で求めることができます.

とあるけど

最大長方形のアルゴリズムというのは、ヒストグラムの最大長方形の面積をstackを使ってO(n)で求めるやつ(蟻本に載ってる)の応用で、上から(y)見ていってそこまでの段のx地点で上にどれだけ伸ばせるかをインクリメント(なりクリアなり)して、それに対してヒストグラムのやつをかます方法。

それはいいとして。
印を含まない長方形(角や辺に来るのはOK)ってどう見たらいいんだ?
→(マス目じゃなくて)格子点レイヤーで見て最大面積になる長方形を見つけて、それの縦横を+1ずつしたもの、か

ちなみに、悪い部分(印のついている部分)の求め方は隣接する2x2コマでの黒(ないし白)の数の偶奇、なので、隣接コマ同士のxorを縦方向にかけたものを今度は横方向にかけて、みたいな求め方もできる。

→AC
https://beta.atcoder.jp/contests/arc081/submissions/3070655
252ms。O(HW) だし最初の自分の解 (1606ms) より大分速くなってる。

ARC 076 E - Connected? (700)

  • 同じ数字が2つとも長方形の外枠に乗らない限り無視してよさそう
  • 長方形の外枠に乗っている数字だけ見て、どれかがクロスしていればNO、していなければYES
    • 時計回りに(あるいは反時計回りに)並べて
    • クロス判定はスタックで行けそう(233211 みたいなのを左から読んで、topと同じなら下ろして、さもなければ乗せて、最後に空になっていればクロスしないのでYES。1212 とか下ろす機会がないのでNO)

→AC 20'30
https://beta.atcoder.jp/contests/arc076/submissions/3067267
一発で通せるとはね(そして解説と同じ解法だった)

8月20日

ARC 073 E - Ball Coloring (700)

  • N=1のときは1。以下、N≧2のとき。
  • xy混ぜてソートして
  • 1) /最小 - 最大を赤青で取り分けた場合
    • (これは必ず出来る。1つの袋に最小と最大が入っていた場合は自明。最小と最大が別々の袋に入っていた場合も自明。)
    • その他の袋で小さい方を赤に、大きい方を青に入れる。
  • 2) 最小 - 最大を片方の色(例えば赤)に寄せた場合
    • (これは出来ない場合がある。1つの袋に最小と最大が入っていた場合。この場合、1) の分け方のみが可能)
    • どうやって、もう一方(青)に入る数の最小 - 最大の差を最小化したらいい?
    • そこで悩んでタイムアップ
解説読む
  • 解説解もそこまで同様だった
  • どうやって、もう一方(青)に入る数の最小 - 最大の差を最小化したらいい?って所
    • とりあえず、各袋の小さい方を青に寄せる
    • 青に寄せた小さい方の数をソートして、小さい方から、同じ袋に入っていた大きい方の数に入れ替えながら、青の最小 - 最大を更新していく(残っている小さい方の数、入れ替えた大きい方の数、最初に赤に入れた全体の最小と最大の数それぞれと同じ袋に入っていたため青に入れられた2つの数、に着目)

→AC
https://beta.atcoder.jp/contests/arc073/submissions/3050589
なんか応用が効きそうだ

ARC 069 E - Frequency (700)

  • とりあえず山の高さごとにまとめる
  • 自分より大きい山が消えないとsに現れることはない
    • ある高さの山の一番番号が若いやつ:その山と同じ高さの山がすべて1ランク下の高さに揃うまでの手数
-- それ以外:0
    • みたいなのを書いてみた。サンプルケース通るじゃん
    • 計算量はO(NlogN)だよね
    • いちおうlong longで計算して

→WA (48'20)
https://beta.atcoder.jp/contests/arc069/submissions/3049924

まあ甘いですわな

  • 例えば、番号#1の山が一番高かったとすると、本来1がΣ山の高さでその他は0、みたいな答えになるはずなのだけれど、1ランク下の高さに揃った時点で用済みになってしまってうまく行かない。
  • 1ランク下の高さに揃えていく時に、若い番号を持ち越していくべき。
    • priority_queueでよくね?
    • last_top を pq.top() で取るように変更

→AC (58'53 + penalty)
https://beta.atcoder.jp/contests/arc069/submissions/3049986

WA(1)食らったけど、700にしてはすんなり解けた。
とはいえ以前D問題を解いたときに33'38かかっているので、C問題も合わせると1時間40分以内に2投目まで出来るかギリギリのラインだ…

解説読んだ

大体やってることは同じだし、計算量もO(NlogN)だけど

  • vector<pair<int,int>>に入れて降順ソートして左から。(それまでの最小の山番号を保持しながら)

別にmap<int,vector<int>>にまとめなくても良いということで。

8月14日

ARC 068 E - Snuke Line (700)

区間がN=最大3e5個与えられて、d(1〜M=1e5)の倍数が含まれている区間の個数を1〜Mについてそれぞれ返すクエリ問題。
40分以上かかったけど自力で方針思いついた。

  • 区間[li, ri]をx=1〜√Mで割っていって、得られた区間 [ceil(li/x),floor(ri/x)] を追加していく。この区間が有効なら、割った数xについても(未登録なら)[x, x] を追加。
    • 区間が [lo, hi] なら, a[lo]++, a[hi+1]--
    • √Mがジャストの数かそうでないかで境界条件に注意。
  • imos
  • 計算量は O(N√M)
    • 3e5×√1e5 = 9.48e7だし間に合うでしょ
  • あれー最悪ケースで4.7sかかる
    • どこで時間食ってるんだろう(ループを何度も見返す)
    • もしかして入力?(30万行とか読むし)
    • cin を scanf に変えたら2s切った
    • よし出すぞ

→AC 1'35'34''
https://beta.atcoder.jp/contests/arc068/submissions/3006776
一発AC嬉しい。(そしてサーバ上では1197ms)
ぎりぎり時間内(=Eだけに取り組んでたら取れた)

解説よむ

O((MlogM + N)logM) らしいんだけど...
Fenwick Tree(フェニック木/Binary Indexed Tree (BIT))を使えとな。

  • 区間の幅(inclusive)がwなら、d≦wなdは必ず1回以上訪れるというのは自明
    • d=wのときは1回
    • d>wのとき、1回も訪れることができない可能性がある
      • そこまでは分かる
  • 区間を幅ごとに分類しておいて
    • dを1〜Mまで回しながら
    • 初めてd≧wになった区間を何か(Fenwick Tree等)に追加(1加算)
      • Fenwick Treeへの区間追加でO(logM)なら、全部でN区間あるからO(NlogM)か
    • dの倍数を全て調べる
      • 各dについてdの倍数を全て調べる計算量って...M/1+M/2+...+M/M = M(1+1/2+1/3+...) = O(MlogM) か。それにFenwick Treeのクエリの計算量(O(logM)か)を掛けてO(M log^2M)
    • 合計O((MlogM + N)logM)。なるほど

後で解説の解き方でもやってみるか

Fenwick Tree (Binary Indexed Tree, BIT)

区間への加算も Fenwick Tree 等を用いることで 1 回あたり O(log M) で行うことが可能です.

簡単に言えば

  • Segment Treeのメモリ効率を良くしたやつ
  • 長さNの配列 v[] があるとして
    • v_i=v_i+w\displaystyle\sum_{i=a}^{b}v_i をO(logN)で出来る
    • しかも必要なのは長さNの配列のみで、実装もシンプル
      • 1ベースの方が実装がしやすいけど0ベースもまあ書ける

区間 [a,b) に+wするにはFenwick Treeを2本用意して(p,qとする)

  • p.add(a,+w); p.add(b,-w);
  • q.add(a, -wa); q.add(b, +wb);

これで区間 [0,c) の合計が p.sum(0,c) * c + q.sum(0, c) で求まる。
(例えば、aが0とcの間にあるとしたら、求めたい [0,c)の合計は(c-a)w = cw-awである。p.sum()=w, q.sum()=-wa なので、w * c - wa = (c-a)w といい感じに補正されている。)
→AC
https://beta.atcoder.jp/contests/arc068/submissions/3008242
(サーバ上で370ms。速い)

8月13日

ARC 060 E - 高橋くんとホテル (700)

N(=1e5)軒のホテルがそれぞれ座標 x_1,...,x_N に一直線に並んでいて、一日に距離Lだけ進むことができる高橋くんがあるホテル a からあるホテル b に行き着くのに何日かかるかというクエリをQ=1e5本こなす問題。
1回のクエリの計算量をO(logN)とかO(√N)とかのレベルにまで落とすことができるか。

  • 各ホテルから1日で行き着ける最遠ホテルを求めるのはO(logN)で出来る。これは簡単。
    • こうして求めた配列を使って、2日で行き着ける最遠ホテルを求めるのはO(1)で出来る。(2ステップするだけ)
      • 1日目で既に最後のホテルに到達してしまうならなにか門番的な値(0ベースならN、1ベースならN+1とか)を入れておく
    • 同様に4日で、8日で、…、2^(R-1)日で行き着ける最遠ホテルを求めておくとすると、全部でO(log^2 N) だ
    • 高々R=17段なのでメモリ的には問題ない
  • こうして準備したテーブルで、aからbへの旅路をどう高速に求めるか
    • aから1日,2日,4日,8日,...の項を見ていって、bそのものかbに一番近い所(a')まで移動する。bそのものに到達したらそこでおしまい。
    • a'から同様に1日,2日,4日,8日,...と見ていく。
      • 最後に、どうしてもbそのものにたどり着けない(bを越えてしまう)なら工程数に+1を足しておしまい。
    • この計算量は整数を2進表記するコストみたいな感じ。O(logN)?O(log^2 N)?
  • いずれにせよ間に合う

→RE 1:07
https://beta.atcoder.jp/contests/arc060/submissions/3001359
あ?
ああ、前計算の段数をけちってるせいだ(Nが2の累乗ジャストの時に死ぬ)
一箇所、ループの<N<=Nに直して
→AC 1:11
https://beta.atcoder.jp/contests/arc060/submissions/3001372
時間かかっちゃったけど自力で解けて嬉しい

解説より

大体解説解も同じなんだけど、前計算のテーブルを1日,2日,4日,8日,...と見ていかなくても二分探索でやるといいよね(O(log log N)だ)

…ダブリングにより…

そうかこういう前計算テーブルの作り方は「ダブリング」というのか
(いや、蟻本にも載ってるってよ…そろそろ蟻本を読み返したら学びが多いかも)