AtCoder ABC 153

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

ABC153 F

水色問題は解けなあかんでしょ......つらい。

けっきょくソートを除いて $O(N)$ で解かなければならない。一番左から貪欲に爆破すればいいのだけれど，その地点での残り体力をいかにして求めるか。例えば爆破したときにそのダメージをqueに入れておいて，毎地点においてqueのfrontと比較して，爆破範囲を過ぎていたら取り除けばいい。するとqueを参照する回数は合計で $O(N)$ で済む。

試験も終わったし，また精進したい。レートが上がらんのよ。

2020-01-18

AtCoder ABC 142

詰まった問題を覚書程度に記す。

ABC142 D

atcoder.jp

公約数のうち素数の数を調べればいい。これは $O(\sqrt{N})$ でできる。ただし $N=gcd(A,B)$ 。
AとBの公約数は最大公約数の約数である。Nを素因数分解していけばよい。調べるのは $\sqrt{N}$ までで良くて， $\sqrt{N}$ を超えるような素因数は多くても１個しかない。

はじめ「最大公約数以下の素数をを列挙すればいいのかな～～～」と考えていたらそれだと $O(NloglogN)$ かかって解けないことに（TLE出してから）気づいた。こうして期せずして（？）充実した素数ライブラリを作成することができたのだ。はあ。

ABC142 E

atcoder.jp
「ハァ～最小重みマッチングかあ知らんなあ解説読んで実装しよ」とeditorialを見たら一番上に「動的計画法」って書いてあったから一目散に閉じた。

結局bitDPを使えば解ける。Nが非常に小さいことから気づきたいなあ。そもそもABCにネットワークフローは出ないのかしら。いずれ勉強しないとなあ。

ABC142 F

atcoder.jp
実装も考察も何一つ追いつかなかった。完敗。

解き方1

editorialのやりかた。いくつか図を書けばわかるが，一つ閉路をもってきたときに，そこにもし余分な辺が入ってあったとすれば，その余分な辺はショートカットになっている。つまり，その余分な辺を使えばより最適な閉路が手に入る。これを繰り返せばいい。

解き方2

辺をひとつ固定して，startをその辺の終点，goalを始点とする。そこからダイクストラ法を用いて，startからgoalまでの最短路が答えとなる。もちろんstartからgoalまでたどり着けなかったら固定する辺を変える。

最近けっこうABCの問題を解いているのだけれど，時間内にA~Fまで解けるようになる気がしない。どうすればいいのかなあ。

2020-01-18

AtCoder ABC 143

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

ABC143 D

atcoder.jp

解けたけど時間かかった。
$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;
}

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

こんちゅう

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

AtCoder ABC 153

ABC153 F

AtCoder ABC 142

ABC142 D

ABC142 E

ABC142 F

解き方1

解き方2

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