2020-01-18

AtCoder ABC 143

解けなかった問題を覚書程度に記す。

ABC143 D

解けたけど時間かかった。
$a,b$ を固定して $b\le c < a+b$ なる $c$ の個数を調べればいい。その調べ方について累積和で実装したのだが，二分探索でupper_boundとlower_boundを使えば一瞬だった。実際みんな一瞬で解いてた。

ABC143 E

atcoder.jp

解けたけど（ｒｙ
ワーシャルフロイドを２回使えばいい。INFの値をlong longに対応していなくて詰まった。

ABC143 F

atcoder.jp

解けた.....ならよかったんだけどなあ。難しくない？

考え方としてはたぶん典型的なんだと思う。つまり，
・K枚のカードを選ぶときの，操作を行える最大の回数 $g(K)$
と，
・X回の操作を行うときの，選べる最大のカード数 $f(X)$
は問題として等価であることを見抜かないといけない。K,Xの座標軸を用意するとより直感的。この言い換え力がほしい。

さて，X回の操作を行うときの，選べる最大のカード数を調べたい。例えばおかしの詰め合わせを $X$ 個作ることを考える。ただしこのお菓子の詰め合わせには，同じおかしを２個以上いれてはいけない。各おかし $i$ は $C_i$ 個あるとする。このような設定のもと，おかしの詰め合わせには最大何個のおかしを入れることができるか？
各おかし $i$ を， $X$ 個まであるだけ徴収する。そのあとお菓子の詰め合わせを作り始める。まずはおかし1を $X$ 個の袋にひとつずつ入れていく。おかし1がなくなったら次はおかし2をひとつずつ入れていく。それを繰り返す。各おかしは $X$ 個以下なのだから，おかしが同じ袋に入ることはない。よって，
$f(X)=\sum_{i=1}^N min(C_i,X) / X$
となる。
あとは $\sum_{i=1}^N min(C_i,X)$ を効率的に求められればいい。editionalのように式を変形してもいいし， $C_i$ を昇順にソートしておいて， $C_i$ と $X$ の大小の境界をずらしていけば計算できる。

他にもいろんな解法があるみたい。もっと考察すればよかったかも。

2020-01-14

AtCoder ABC 144

解けなかった問題を覚書程度に記す。

ABC144E

atcoder.jp

解けたけどめっちゃ時間かかった。
$A_i$ を昇順， $F_i$ を降順でソートすればいいのは直感的。あとはスコアを２分探索すればいい。
２分探索について，lhsとrhsの更新とか細かいところでちょっと詰まった。気を付けないといけない（より一般的なライブラリを作ればいいのかもしれないけれど，まあ注意すればいいだけの話かなあ）。

ABC144F

atcoder.jp

難しい...けれど解説を見れば超簡単。これは頑張って考察したかったなあ。
ルートを消さないときの期待値は大きい部屋から逆にdpすればいい。ルートを消すとき，期待値が最小になるように消すのだから，頂点iから出るルートのなかで一番コストのかかるものを除けばいい。あとはそれを1~N-1について確かめる。 $O(NM)$ 。

2020-01-14

AtCoder ABC 150

解けなかった問題を覚書程度に記す。
atcoder.jp

ABC150F

難しくない？？（ずっと言ってる）

結局XOR演算について正しく理解しているかという話になる。基本的な性質はググれば出てくるが，
$a\oplus b=b\oplus a$
$(a\oplus b)\oplus c=a\oplus (b\oplus c)$
$a\oplus a=0, a\oplus 0=a$
$a\oplus c = b\oplus c \Leftrightarrow a=b$
$a\oplus c \neq b\oplus c \Leftrightarrow a\neq b$
くらいだろうか。証明は真理値表より。

$a_{k}\oplus x, a_{k+1}\oplus x,\cdots ,a_{k-1}\oplus x$ と $b_0,b_1,\cdots ,b_N$ が全て一致すれば言いわけだが，もしこれがとあるkについて成立していれば，すべてのiに対して， $a_{k+i}\oplus x \oplus a_{k+i+1} \oplus x=b_i\oplus b_{i+1}$ が成立している。これは先ほど述べた性質より $a_{k+i}\oplus a_{k+i+1}$ と一致しているため，このようなkをKMP法を用いて探せばいい。逆を考えることで $x$ を特定できる。
KMP法についてはググったら出てくる。が，結構理解する&実装するのに時間がかかった。でももうライブラリも整備したし，次は大丈夫。なはず。

このままだとeditorialそのままなので何か書く。例えば $a_i=0,1$ ， $b_i=1,2$ ， $x=0,1$ であり，XORがただの足し算であるような状況を考える。
$A:0,0,1,0,0,1,0,1$
$B:2,1,1,2,1,2,1,1$
このとき，条件を満たすような $k,x$ を探すのに $O(N^2)$ かける人はいない。Aはただシフトして同じものを足しているだけなので，例えばそれらの差分は変わらない。差分を用いてBと効率的に比較できる。
ところでこの状況は一般的である。つまり，2を0と置き換え， $a_i$ をbitごとに別の数列として改めておくと，問題の状況と完全に一致する。

2020-01-14

AtCoder ABC 149

解けなかった問題を覚書程度に記す。

ABC149E

atcoder.jp

こういう問題をすっと解きたい。

ナイーブにやるとすると $A_i+A_j$ を上からとればいい。しかしこれは数列の長さが $O(N^2)$ でありソートにも時間がかかるのでできない。困った。

ここで，この $N^2$ 個の数列の特別な構造を用いる。例えばあらかじめ数列Aをソートしておけば， $A_i$ を固定した時の $A_i+A_j$ は単調増加の数列となる。つまりその中では2分探索などの強力なツールを $O(logN)$ で実行できる。完全にランダムな $N^2$ この数列のときには，前処理に結局 $O(N^2logN)$ かかるので使えない。今回は $O(NlogN)$ で済んでいる。これがミソ。

幸福度が $D$ 以上となるような $A_i+A_j$ のペアの個数を探す。これは $A_i$ を固定した数列に対して二分探索を実行すれば求まるので， $O(NlogN)$ で済む。あとは $D$ について二分探索することで，幸福度が全て $D$ 以上であるようなペアが $M$ 個以上あるような， $D$ の下限を求めることができる。
そのような $D$ が求まれば，あとは各 $A_i$ を固定した時の数列に対し， $D$ 以上のものの和を求める。これは $S_n=A_1+\cdots +A_n$ で表される累積和を用いれば $O(NlogN)$ で求まる。ただし足しすぎ（Ｍ個以上足してしまう）に注意。

なお，幸福度が $D$ 以上となるような $A_i+A_j$ のペアの個数を探すところで，しゃくとり法も使える。数列Aをあらかじめ昇順ソートした後，テーブルの横軸が $A_1,A_2,\cdots A_N$ ，縦軸が $A_N, \cdots ,A_1$ となるように配置すれば結構綺麗な形になる。つまり，各 $A_i$ を固定した行について幸福度が $D$ 以上となる最小の $A_j$ は，下に行くにつれ単調に右にずれていく。

ABC149F

atcoder.jp

難しくない？？？？？？？？？？？？？？？？？？？？（逆ギレ）
競プロという（一般的に見て）マイナーコンテンツの，年の瀬の，unratedのコンテストの時間内に，こんな難しい問題を解く人が100人以上いるなんて，日本の未来は明るいですよ。ほんとうに。いやほんと。

解き方1

editorialの解き方。まず期待値の線形性からこんな鮮やかに分割できるところがすばらしい。Sの穴あき度の期待値は，Sの頂点数の期待値から，Sに含まれる黒丸の期待値を引いたもの。Sは全ての黒丸を含むように構成しているのだから，後者については $\frac{N}{2}$ となる。問題は前者。
Sの頂点数の期待値について，これまた各辺にバラして考えて，（各辺がSに含まれる期待値の合計)+1となる。ただし空グラフの分は除く。
各辺がSに含まれる期待値は，その辺により木が $x_e$ 個と $N-x_e$ 個の木に分解されるとして，
$(1-(\frac{1}{2})^{x_e})(1-(\frac{1}{2})^{N-x_e})$
となる。あとはこれを枝について和を取る。まとめると，
（こたえ） $=\sum_e (1-(\frac{1}{2})^{x_e})(1-(\frac{1}{2})^{N-x_e})+1-\frac{1}{2^N}-\frac{N}{2} \\ =\frac{1}{2^N}(N2^{N-1}+(N-2)-\sum_e (2^{x_e}+2^{N-x_e}))$

となる。この分母を $x$ ，分子を $y$ とおき， $x=pM+x', y=qM+y'$ とする。すると求める $z$ は，
$(pM+x')z \equiv (qM+y') (mod M)$
なので，けっきょく $x$ と $y$ は $M$ で割った余りを用意しておけば十分。
$z=yx^{-1}$ であり， $x^{-1}=x^{M-2}$ なので（モジュラ逆数），これでやっと答えが出る。最後の方はこういう問題では当然なのかな。

解き方2

たぶん頂点ごとに見る方がはるかに見通しが立ちやすい（し方針も立てやすい）と思う。解説はいろんなサイトがしているからここには書かないけれど（じゃあeditorial丸写しもするな）。単なる木の再帰を全方位DPっていうみたい。言葉尻が強い。

2020-01-13

AtCoder ABC 147

解けなかった問題の簡単な説明を覚書程度に記す。

ABC147E

atcoder.jp

DP。まず $|A_{ij}-B_{ij}|$ を計算する。

dp[i][j][k]:i,jマスまで行ったとき偏りkを実現できるかどうか

とすると， $|A_{ij}-B_{ij}|$ の最大値をMとして $O(HWM(H+W))$ くらいで解ける。

kは別に80までで十分なんじゃないか？と思ったこともあるけれど反例がある。例えば今の偏りが60で，マスが40,50,50と続いたとき，60+40-50-50をしないと0にはならない。

ABC147F

atcoder.jp

難しくない？解説見ても数日実装できなかった。

$D=0$ は別処理。 $D>0$ として一般性を失わない。 $S+T$ の値は固定なので結局 $S$ の値としてどれだけあるかを数えればいい。
高橋君がK個取るとする。するとSとして取りうる値はKX+(0+1+...+K-1)D～KX+(N-k+N-k+1,...,N-1)Dとなる。

じゃあこれでKを固定した時の値が $O(K)$ で出せたからあとはKを0~Nまで動かせば完成だ！...と思ったら，これだと $O(N^2)$ かかってしまう。しかしKを変えたときの値が重複する可能性もあるのでKに対する単純な直和ではない。
制約からどうやら $O(NlogN)$ くらいで解かないといけないらしい。こっからが辛かった。

KX mod Dで場合分けをすると, KX mod Dが異なる列は絶対にカブらない。例えばD=2,X=1,N=5として,
K=3のとき 3+(0+1+2)*2~3+(2+3+4)*2
K=4のとき 4+(0+1+2+3)*2~4+(1+2+3+4)*2
について，K=3と4で被っている値はない。(3 mod 2 != 4 mod 2より)

KX mod Dで場合分けを実行する。例えばKX mod D = aとなったKたちに対して，それらの数列の和集合が答えになる。
例えば上の例でK=2のとき2+(0+1)*2~2+(3+4)*2なので，K=4のときの数列と重複が存在する。これはイベントソートにより効率的に計算できる。たとえば交差が1の数列たちを考えて，それらの初項と末項が $a_1,a_n,b_1,b_n$ とすると,

vector<pair<ll,ll>> timetable;
timetable.push_back(make_pair(a_1,1));
timetable.push_back(make_pair(a_n,-1));
timetable.push_back(make_pair(b_1,1));
timetable.push_back(make_pair(b_n,-1));

として,timetableを1項目でソートした上で一つずつ取り出し，

for(auto& t : timetable) {
     if(res > 0) ans += t.first - before;
     before = t.first;
     res += t.second;
}

とでもすればいい。一つ一つにばらすと典型テクニックらしいんだよなあ。

2020-01-13

AtCoder ABC 151

うぎゃあ。解けなかった問題の簡単な説明を覚書程度に残します。

ABC151F

atcoder.jp

けっこう正答率が高い。

解き方1

最適な円は必ず2点or3点を通る。どうしてかというと, まず0点or1点しか通らない円は2点通る円のほうが最適であることが分かる。N個から2点取ってきて，こいつらを通る円を考える。でも2点だと円が確定しない。2点を直径とする円内に他の点が全てあればそれが最適。なければ外にある点を結んだ3点を通る円のうちいずれかが最適（もちろん全部ハズレの場合もある）。
この解法は $O(n^4)$ でできる。根拠は, 3点取ってくるのに $O(n^3)$ で，それごとにN個の頂点に対して円内に入ってるか確かめる必要があるから。

最適な円は必ず3点通るやろ！っつって頑張って実装してたが，方針が違う上そもそも実装力が無くて間に合わず。つらるん。

解き方2

editorialのやりかた。二分探索を使う。Rを固定し，各頂点を中心とするN個の円の交点を全て求める。このとき交点のできない円のペアがあったらやり直し。各交点からN頂点までの距離がR以下かどうか調べる。R以下なら半径Rの円で全ての頂点を覆うことが出来る。そのような交点が一つでもあったらRを小さくして再チャレンジ，一つも無かったらRを大きくして再チャレンジ。
結局これは，２つの円を選ぶことで全体の円の中心となりうる点を2つに絞っているところがミソである。１ステップあたりの計算量は,２つの円を選ぶのに $O(n^2)$ で，それに対してN頂点が円内に入っているか調べないといけないので， $O(n^3)$ となる。あとはこれを十分な精度とするために,はじめの区間をTとすると， $T2^{-n}<10^{-6}$ くらいになるよう $n$ を設定すればいいのかな。

解き方3

最小包含円でググると良い感じのライブラリが出てくるらしい。へええ。

解き方4

三分探索とやらでできるらしい。 $f(x,y)$ を $x,y$ を中心としたときのN頂点までの最長距離の二乗の最大値とすると, $f(x,y)$ は凸関数になるらしい。ほんまか。まあでもそれはそうで, 例えば $x$ を固定したとき，
$f(x,y)=max((y_1-y)^2+const,\cdots ,(y_N-y)^2+const)$
であり，図を書いてみると確かに凸関数っぽい。でもこれって解が自明にならない？よく分かってない。こんど実装してみよっと。

【追記】上で見たように， $x$ で止めても $y$ で止めても凸関数だから, いわゆる鞍点が存在しない．つまり, 例えば $x$ を一つ固定したときの $f(x,y)$ の最大値を $g(x)$ とする．このとき $g(x)$ は凸関数になる．
$x,x'$ に対して $x1=px+(1-p)x'$ としたとき $g(x1)\le pg(x)+(1-p)g(x')$ を示せばいい． $g(x1)=f(x1,y1)$ とすると, $g(x)\ge f(x,y1), g(x')\ge f(x',y1)$ であり, yを止めたとき $f$ は凸関数なので,
$pg(x)+(1-p)g(x')\le pf(x,y1)+(1-p)f(x',y1)\le f(x1,y1)=g(x1)$
が成立する．
もしかしたら合成関数が云々とかでもっと簡単に言うこともできるかもしれない．蟻本に載ってた気がするので帰ったら確認してみる．
ともかく $const*O(N^2)$ で出来るのは魅力的。実装も簡単。

2020-01-12

AtCoder ABC 146

解けなかった問題の簡単な説明を覚え書き程度に残す．

ABC146D

atcoder.jp

使用する最小の色数は最大の頂点の次元数．あとはどう構築するかだけれど，例えばqueueを使った幅優先探索を用いればいい．らしい．

ABC146E

atcoder.jp

難しくない？めげそう．
とりあえず累積和をとる（らしい）． $S_i=A_1+...A_i$ とすると，求めるのは
$(S_j-S_i) \% K=j-i, j-i< K, j> i$
なるi,jのペアの個数．もちろん $O(N^2)$ なのでナイーブには解けない．

こんなときにはしゃくとり法が使えるらしい．式を
$(S_j-j)\% K = (S_i-i) \% K$
と変形する（この変形すら思いつける気がしない）． $S_i-i$ を改めて $S_i$ とする。すると,iを固定したときに，求めるのは[i,i+k-1]のなかの，S_iと等しいSの個数．これは区間のSの個数をmapで管理しておいて，区間をずらすたびにそれらを増減させると $O(NlogK)$ で解ける． $logK$ はmapのコスト．

ABC146F

atcoder.jp

難しくない？（２回目) でもFにしては簡単らしい．というのも

解き方1

貪欲でいける．後ろから飛べるだけ飛べばOK．もしスタートからゴールまでのルートが存在すればこの方法で必ず解が見つかる．
複数個の解があったとき，このような解のとり方が辞書順最小となることも示せる．なんてこったい．

解き方2

貪欲じゃなくても解けるみたい（強い人はこっちがすぐ思いつくのかな）．
dp[i]:地点iからゴールまでの最小手数とする．するとこれはdp[i+1]~dp[i+M]までの最小値+1になる．
つまり[i+1,i+M]の区間内の最小値をいい感じの計算量で求められたらいい．これはRMQを使うと実現できる．
dequeでも出来る．らしい．あとでやらねば．

こんちゅう

エッセイ・小説・ブログ・楽譜置き場。不定期更新。

AtCoder ABC 143

ABC143 D

ABC143 E

ABC143 F

AtCoder ABC 144

ABC144E

ABC144F

AtCoder ABC 150

ABC150F

AtCoder ABC 149

ABC149E

ABC149F

解き方1

解き方2

AtCoder ABC 147

ABC147E

ABC147F

AtCoder ABC 151

ABC151F

解き方1

解き方2

解き方3

解き方4

AtCoder ABC 146

ABC146D

ABC146E

ABC146F

解き方1

解き方2