こんちゅう

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

AtCoder ABC 153

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

ABC153 F

atcoder.jp

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

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

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

AtCoder ABC 142

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

ABC142 D

atcoder.jp

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

はじめ「最大公約数以下の素数をを列挙すればいいのかな~~~」と考えていたらそれだと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まで解けるようになる気がしない。どうすればいいのかなあ。

AtCoder ABC 143

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

ABC143 D

atcoder.jp

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

ABC143 E

atcoder.jp

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

ABC143 F

atcoder.jp

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

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

さて,X回の操作を行うときの,選べる最大のカード数を調べたい。例えばおかしの詰め合わせをX個作ることを考える。ただしこのお菓子の詰め合わせには,同じおかしを2個以上いれてはいけない。各おかしiC_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_iXの大小の境界をずらしていけば計算できる。

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

AtCoder ABC 144

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

ABC144E

atcoder.jp

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

ABC144F

atcoder.jp

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

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 xb_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,1b_i=1,2x=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ごとに別の数列として改めておくと,問題の状況と完全に一致する。

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)で求まる。ただし足しすぎ(M個以上足してしまう)に注意。

なお,幸福度が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)
なので,けっきょくxyMで割った余りを用意しておけば十分。
z=yx^{-1}であり,x^{-1}=x^{M-2}なので(モジュラ逆数),これでやっと答えが出る。最後の方はこういう問題では当然なのかな。

解き方2

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

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;
}

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