naoya_t@hatenablog

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

〈ARC埋め〉D問題集中アタック(続き:071 - 056)

引き続き埋め

ARC 071 D - 井井井 / ### (500)

  • 横方向、縦方向を独立に計算して、最後に掛け合わせれば良くて
  • 区間が何回使われるかは左に何通り右に何通り伸びるか分かれば求まる

→AC 11'18
https://beta.atcoder.jp/contests/arc071/submissions/2698725
なんか500点問題にしては簡単に解けた(方針合ってたけど計算合わなくなる系のミスが2ヵ所あってそれを直すのにかかった時間が半分)

解説解では区間じゃなくてそれぞれの座標が何回足されて何回引かれるかで考えてた(けど概ねやりたいことは同じ)

ARC 070 D - No Need (600)

N,K≦400を満たすセットが取れれば部分点300、とあるけど最初から満点解法を狙っていく

  • a_i以外の要素から成る、合計が [K-a_i, K) の範囲になる集合が存在するとき、a_i はキャスティングボートを握る、というかa_iなしでは存在できない集合が1つ以上存在するので「消せなくなる」。そういうのが1つもない場合は「消してよし」。
  • a_iは1e9までだけどK≦5000までだから2K=10000ぐらいで切っちゃっていいだろ
  • 合計がxになる集合の有無、をDPで求めておく。これは前からDPしたやつと後ろからDPしたやつを持っておく。このDPはO(NK)で出来る。
  • a_iの前と後ろで(a_i以外を使ってという意味)合計が [K-a_i, K) の範囲になる集合が存在するかを調べる。DP結果(10000)xDP結果(10000)を愚直に1:1で見ていったら全体でO(NK^2)になって死ぬので、片方は二分探索でO(NKlogK)にする。

→MLE(1) 42'53
https://beta.atcoder.jp/contests/arc070/submissions/2698911
ああ、int[5000][10000]が2つで200MBx2=400MB取ってる(256MB制限なのに)
1ビットずつしか使ってないのに。
ビットが立ってるやつだけを列挙した配列(lower_bound用)のために同様に配列を使ってて贅沢すぎた。
→charに変える、列挙配列はその都度作る
→AC 50'49
https://beta.atcoder.jp/contests/arc070/submissions/2698942
わーい

解説より

解説の満点解法では、a_iが不要なとき、a_i以下の全てのカードは不要である、ということを利用して「どこまで不要か」二分探索することでdpの回数をO(logN)に減らせてO(NKlogN)にしている。
その後に言及されている「他の方法」ってのが自分のと大体同じ。lower_boundじゃなくて累積和を使えば O(NK)まで落とせるよ!あとはDPにbitset使ったりとか。

ARC 068 D - Card Eater (400)

すぬけ氏の奇行シリーズ。

  • x = 数が何種類あるか
  • y = 食べてもいいやつ = Σ(それぞれの数が何枚あるか - 1)

2枚ずつ食べるので、yが偶数ならxが答え。奇数なら何か1枚犠牲になるのでx-1が答え。
→AC 7'49
https://beta.atcoder.jp/contests/arc068/submissions/2699082

解説解も同様

ARC 065 D - 連結 / Connectivity (400)

道路、鉄道それぞれ(別々に)union-findして、
ある都市が (道路島i, 鉄道島j) に属するとして
その (i,j) という組み合わせがいくつあるかを集計して(最大でも都市数=10万パターン)、
各都市についてパターンを同じくする都市の数を表示すればいい
→AC 11'55
https://beta.atcoder.jp/contests/arc065/submissions/2699158

解説解も同様

ARC 063 D - 高橋君と見えざる手 / An Invisible Hand (400)

基本は「安く買って高く売る」。道中での(そこまででの)最安値と(そこ以降の)最高値の差が最大になるペアがいくつあるか、が答え。
最安値を記録しておいて、最安値より高く売れる町で差額をpriority_queueに放り込む。
最後の町まで見たら、最高値と同額が何回出てくるか数えて返す。
→AC 9'41
https://beta.atcoder.jp/contests/arc063/submissions/2699221

解説より

A_iの値が相異なるという制約があるから出来ることで、さもなければ買う町が共通なケースがあったりしてもうちょい複雑になる点に注意。

ARC 062 D - AtCoDeerくんと変なじゃんけん / AtCoDeer and Rock-Paper (300)

全部gを出すとしたら相手のpの数だけ失点するわけだけど、そこを起点にして、どこにpを出していくのがよいか考えるんだけど

  • 相手gのところ:g×g → g×p なので+1
  • 相手pのところ:p×g → p×p なので+1

というわけで、どこに出しても+1
だったら可能な限り(floor(N/2)回)出して、スコアを計算するだけ
→AC 8'41
https://beta.atcoder.jp/contests/arc062/submissions/2699562

解説より

floor(N/2) - (相手のpの数)ね

ARC 061 D - すぬけ君の塗り絵 / Snuke's Coloring (400)

  • 10^9 \times 10^9 のキャンバスを用意するのは無理。座標圧縮したって無理。
  • (10^9 - 2)(10^9 - 2) の全ての3x3領域を調べるのは無理
  • 色を塗った場所の近傍だけ見ればいい。(重複は排除しておく)
  • 色を塗った場所はset>に入れておけばlog(N)で探せる。*1
  • 調べていない場所が何箇所あるかは計算で求めて、0の項に加算する。

→AC 22'16
https://beta.atcoder.jp/contests/arc061/submissions/2699321

解説解も同様

ARC 058 D - いろはちゃんとマス目 (400)

ARCの未踏400点問題はこれが最後かな。
左下のAxB領域を通らないパターンだけ数え上げたいんだけど、どこかに関所ラインを設けたとしてどうやったら重複なしに行けるんだろうと悩んでポモドーロ終了

解説を読んで

AxB領域の上辺を右に伸ばした線をまたぐ(W-B)箇所の関所の上に着いて下に下りるパターン、というふうに見ている。これだと…隣接する関所に(右に)滑っていくケースはどうなる?どの関所を通るかが問題であって経路は問わないからいいのか。
(関所を点として考えてたから重複に悩むのであって、線(というか1区間)で考えれば解決する)
あとはMODのnCrの計算を工夫して速くするだけ、か。

10C4×4C2,11C5×3C1,12C6×2C0 のように隣接したnCr (10C4 - 11C5 - 12C6, 2C0 - 3C1 - 4C2) が使われるのでこれはインクリメンタルに計算してキャッシュしておけば速い。

void prepare_comb(){
    ll last;
    for (int r=H-A+B-1,k=B; k<W; ++r,++k) {
        last = memo[ii(r,k)] = (k==B) ? comb(r,k) : DIV(MUL(last,r),k);
    }
    for (int r=A-1,k=0; k<W-B; ++r,++k) {
        last = memo[ii(r,k)] = (k==0) ? comb(r,k) : DIV(MUL(last,r),k);
    }
}

→AC
https://beta.atcoder.jp/contests/arc058/submissions/2701772

ARCの400点までの問題は制覇した!

現行のスコア体系になる前の分(ARC001〜057)

ARC 057 B - 高橋君ゲーム

dp[日][勝ち数] = pair(min(分子),max(分子)) みたいなDPを書こうとしてたんだけど計算が合わない。

時間切れにつき解説読む
  • Σa_i=Kのとき:すべての日の全てのゲームに勝つ以外にない→happy(勝率が上がる日)は初日だけ(なので1):これは特殊ケース
  • それ以外(K<Σa_i)のとき:「勝利K回」を「勝利K回以下」と言い換えても答えは変わらない(なぜ?)
    • それを利用すれば dp[日][勝ち数] = min(分子)で行ける(なぜ?)
  • 勝ちL(<K)回でhappyがt回とすると。勝ちK回でもt回happyになるような操作が可能であることの説明かと思ったらt回「以上」という話になってた。駄目だ解説についていけない…

もしかして、Σa_i=Kのケース以外では自分の実装のままで良い(maxは無駄なんだけど)のでは?
Σa_i=Kのときに1を返すようにしてあとはそのままで
→AC
https://beta.atcoder.jp/contests/arc057/submissions/2714556

DEGwer先生の問題は好きだけど解説がいつも理解できない(そしてこの時代はまだ英語解説がない)

ARC 056 B - 駐車場

  • 番号の大きい順から逆に見ていく
  • その番号より前は全て埋まっていると仮定(埋まってないならそこには到達できないわけで、いずれにせよそこ経由では来られない)
  • その番号より大きいスロットへの道を繋ぐ
  • その時点のグラフで入り口に繋がっているならその番号は「駐車可能」
  • という手順をUnionFindでやれば良いのでは

→AC 15'15
https://beta.atcoder.jp/contests/arc056/submissions/2714612

解説より

ある頂点までの距離を(実際の距離ではなく)辺の両端の頂点番号(の小さい方)をコストとするようなダイクストラをする(可能な限り大きい頂点番号を通る道を選択していく)。で、各頂点について、自分より大きい頂点だけを通って入り口に行けるかを見る。

i以上の頂点のみを通り始点から頂点iまで到達できることと、 iが答えに含まれることは等価

という観点からすると、解説にあるようなダイクストラもどきをするより逆順UnionFindの方がシンプルだし(自分には)分かりやすい。

*1:unordered_setでも良いんだろうけど