2020-06-16

ACPCVC20200615 復習メモ

https://kenkoooo.com/atcoder/#/contest/show/de1c2a21-407e-41a6-bc64-deb6570852f3

3問目のJOI感に少しの興奮を覚えた

A - パズル

$HW-1$ パズルになっていて、ステップ数も $24$ ステップ以内とあまり大きくない。
onlinejudge.u-aizu.ac.jp
この問題を解いていると、これは IDA*で通るなという確信が付いているので数字が規定の位置から離れているマンハッタン距離をヒューリスティック値にしてやると、通る。
潜るにしろ、的はずれなところに $12$ 回くらいいく事とかなさそうなので (ヒューリスティック値が増える方向に進むとステップと合わせて $+3$ とか上がったりする)、かなり小さくなるんじゃないかなっていう感じにはなっている。ちゃんと計算量解析したいけど難しそう…

B - 擬二等辺三角形

細かい計算が必要でかなり精神を使う
$2$ 辺を $a, a+1$ みたいに書くとすると、もう $1$ 辺を使って三角形になるのは、 $\lbrack 2, 2a \rbrack$ である。あと、途中で $L-2a-1$ の長さまでしか使えなくなってくる。
しかも、 $a, a+1, a+2$ みたいになっていると、重複して計算してしまうところが出てきたり、そもそも、最後の辺の長さについては $a, a+1$ は使えないとか色々とめんどくさい制約がある。
とりあえず、 $\lbrack 2, \min(2a, L-2a-1) \rbrack$ の中に $a, a+1$ がある場合を考えると、 $a+1\leq L-2a-1$ みたいな制約が出てくるので、解くと、 $a \leq \frac{L-2}{3}$ まではそうらしいことがわかる。
そこで分けて、あとは数列が定められるのでこれらを $\mathrm{O}(1)$ で求めて終わり
数列を頑張る処理は場合分けとか重複部分の排除とか嫌な気持ちになることが多々あるので精神力を使って頑張って殴って解く。
一般化の式とか書くと多分頭がイカれてきそう()

C - 映画の連続視聴

$1$ 次元のDPとかがかなり浮かびやすい。 $H$ の累積和を取っておいて、連続した試聴に対して直接エッジを張ることを考えると、状態 $\mathrm{O}(N)$ , 遷移 $\mathrm{O}(N)$ の $\mathrm{O}(N^2)$ のDPが出来そうで、 $N \leq 3000$ よりかなり現実的
これはもちろん主要な時間だけ取り出す事で実現できているので座標圧縮が必要になる。
ところで、エッジの貼り方はどうすればいいだろうかということになる。
ある特定の時間からある特定の時間まででできるだけ同じ種類の多くの映画を見れば、できるだけ大きい得点になるので、そのような最適なスケジューリングをしてエッジを張って行くことが必要になる。
そこで、まず種類別にする。そして区間の終点でソートする。ソートした後、貪欲に映画を見ていくのが最適になる(これは蟻本とかに書いてある)。このような見方をするたびに、所定の位置にエッジを張っていくと、グラフが完成するので、それをDPで最大化すると、この問題は解ける。
こういうたくさん組み合わさっている系の問題ってJOIみがないかな(わからない)

感想

何回も思っているが、考察はできるだけ詰めておこう出来そうになかったらサンプルをたくさんためそう

2020-06-15

ABC170 参加メモ

ABC 競技プログラミング

温まってる時に限って精神が安定してるな
243th Perf=2069 1846->1870(+24)
Highestあたりにまた戻して行かないといけないので頑張ります

A - Five Variables

一つづつ判断してもいいがforで回して $0$ か判断するのが早そう

B - Crane and Turtle

最小が $2X$ でそこから二本ずつ増やして $4X$ に出来るので、 $Y$ は偶数で $2X \leq Y \leq 4X$ になっていれば "Yes" と出力できる。

C - Forbidden List

値を全探索する。flagとかで使ったやつを管理すればいい $0$ と $101$ が答えになることがあるということに注意

D - Not Divisible

$A \lt B$ みたいな条件で $A$ が $B$ で割れることはないので小さい順にソートしておく
$A_i$ がそれぞれ $A_i$ の倍数を全て埋めていくと(エラトステネスみたいに)、 $A_j(i \lt j)$ が呼び出された時に割り切れるかどうかがわかるので、やっていく。
計算量は調和級数になるので $\mathrm{O}(N \log N)$

E - Smart Infants

現在の幼児の位置を管理して、それぞれ一番大きい値を出せるようにすればいいので、 $2 \times 10^5$ 個 multiset を用意してやるとそれぞれの幼稚園で一番大きい値を取り出せる　移動とかも出来る
その一番大きい値たちを multiset に入れておくと、小さい値がいつでも取り出せるのでこの問題を解ける。

F - Pond Skater

普通にエッジ張って幅でやると言っても、使ったマス以降はだいたい使わなくていいので、そこで $O(HW)$ くらいで行けそうだなってなる。
気をつけるべきなのは、異なる方向で進んでいて、同コストになっている者同士は同じように見てはいけない。そのため、方向を持ちながら条件に気をつけてやると、ACする。
なんか見落としがありそうなので、嘘解法なんですかね(知見のある人教えていただけるとありがたいです)

感想

Eまでは順調だったが、Fでかなり時間をかけてしまった。
やっぱり実装力が落ちている気がするな。
とはいえ今はAtCoderだなという感じがある(同じこと毎回言ってる気がするが)
引き続き精進したい。

2020-06-14

東京海上日動プログラミングコンテスト2020 参加メモ

企業コン競技プログラミング

レートがどんどん下がるみんなに抜かされていく 824th Perf=1672 1864->1846(-18)
そんなことも言ってられないのでちゃんと参加メモを書きます

A - Nickname

これはひねりがなかったのですぐ解けた S.substr(0, 3) をして終わり

B - Tag

逃げる方向とかを固定したかったので $A \lt B$ になるように矯正
すると、相対速度 $V-W$ と $T$ の積が $B-A$ 以上になっていれば捕まえられる。
これを適切に描いたらAC long long とかにしておかないと掛け算でオーバーフローするんじゃないかな

C - Lamps

思いつくまでに時間がかかってしまった
操作は $\mathrm{O}(\log N)$ 回くらいすると、全ての数列が $N$ になってしまう。
これだけ気づければもう終わりなんだよね…

こんな感じで理由を説明すればいいかな。
まず、とりあえず $1$ 回操作すると、全ての数列は $1$ 以上になっている。
その状態から、ほとんどの数の寄与が操作毎に $2 A_i + 1$ になっていくので、
$\mathrm{O}(\log N)$ 回くらいで全部 $N$ になるという見通しがつく。

端を考慮した証明してくれている人とかいるのかな

操作自体は imos法を使えばいいので $\mathrm{O}(N)$ でいける。
よって $\mathrm{O}(N \log N)$ である。

$41$ 回やると制約上で全部行けるらしい。

D - Knapsack Queries on a tree

これ通したかったな…

先祖だけしか見ないので、各クエリ毎に要素は最大 $18$ 個くらいしか呼ばれない。
ただナップザックは制限がない状態だと $\mathrm{O}(2^N)$ になっているので、まあここでやるとしたら半分全列挙くらいしか無いだろうって思う。実際に計算量を考えてもぎりぎり通りそうっていう感じ。これだけだと通らないんだけれども。 9 9 で分けても通らない。
ここで、もうひとつ事実に気づくべきなのは、根の方の要素の組み合わせは少ないので、こっちを前計算で求められるということである。
例えば深さ $10$ のノードそれぞれに対して全列挙を求めてあげても、 $10 \times 512 \times 2^{10} = 5242880$ くらいの計算量にしかならないので、こっちに半分全列挙の比重をかけてあげる。
そうしたら、残り $8$ 個に対しての列挙をしてそれで、 $10$ 個の方の列挙した奴に対してupper_boundとかかけて計算すればいいので、結構計算量が厳し目だが通る。

感想

Dみたいな問題は計算量が通りそうだから祈りながらコードを書いていると死んでしまう。
祈るくらいなら、もうちょっと考えたほうが良い。

2020-06-12

ACPCVC20200518 復習メモ

ACPCVC 競技プログラミング

かなり遅れました。全部書きたいです。

A - ConvexScore

ある $S$ のスコアは $2^{n-|S|}$ であるが、これは内包されている点たちの集合を $T_s$ と置いた時にその部分集合の個数と一致する。
ここで、ある凸多角形を決めたときに、その内部のパターン数を求めて、全ての凸多角形に対して数え上げれば良いという問題①に落ちる。
ここで、 $3$ 点以上からなる凸包の面積が正になっているような点の集合の個数を全て数え上げるとする。
すると、それぞれの集合に対して凸包が一意に定まっているし、全ての凸包を網羅するので、①の答えになっている。

そのため、すべての点集合の個数 $2^N$ から、空集合、 $1$ 点しか無い集合、 $2$ 点以上の直線になっているものの集合の個数を引いてあげれば答えが出るということになる。

空集合の個数は $1$ , $1$ 点しか無い集合の個数は $N$ である。
$2$ 点以上の直線になっているものの集合の個数は、それぞれの直線で考えていくが、ある直線上に $k$ 点乗っている場合、それらの $2$ 点以上の集合の個数は $2^k - k - 1$ となっているので、それぞれの直線に対して $\mathrm{O}(N^3)$ で計算してあげると、最終的な答えが求まる。

スコアの性質をうまく使わないと解けない問題だった。

B - Bichrome Tree

ある部分木 $T$ があって、その根を $v$ としたときに、その $T$ の持つ重みの和がどちらかが $X_v$ , もうひとつが何らかの値 $val$ みたいになる(白黒は関係なくて、どっちの色でも $(X_v, val)$ のペアは達成できる)。この $val$ を最小化しておけば、 $T$ より大きい部分木に対して一番有利に働くだろう。
そこで、
$dp_v$ … 根 $v$ の部分木について、自分の色じゃない方の重み $val$ の最小値
と置く。これに対する漸化式が求まれば、 $dp_1$ の値が存在するか否かで作成可能かそうでないかが分かるはずである。

ここで、ある部分木の根を $u$ , $u$ の子を $v$ とする。
$v$ たちはそれぞれ、 $X_v$ , $dp_v$ の値を持っているが、どちらかを $X_u$ を構成する重みに割り振るか、そうでない方に割り振るかという選択を行うことが出来る。
すべて選択した後、重みの和が $X_u$ 以下(頂点 $v$ 自体も重みを割り振れるので $X_u$ になるように帳尻合わせが出来る) になっているものに対して、もうひとつの値 $val$ が一番小さいものを選べばいいということになる。
とすると、これも DP を用いて解くことが出来る。
$dp2_{v,j}$ ... 現在頂点 $v$ まで見た時に $X_u$ を構成する重みが現在 $j$ になっているときの、もうひとつの値の最小値
これを使うと、 $dp_u = \mathrm{argmin}_{1 \leq j \leq X_u} dp2_{n, j}$ とすることができるので $dp_u$ の漸化式が求まった。
$n$ は頂点 $u$ の子の数とする。

３重ループになるから一見間に合わなそうだが、辺の数は $N-1$ しか無いので $\mathrm{O}(N^2)$ になっている。

C - Four Coloring

これはグリッドを $45$ 度回転すると、ある点 $p$ から距離が $d/\sqrt{2}$ であるような点は $p$ を中心とした正方形を描くことになる。
この条件でやると、どうやら、 $1$ 辺 $d/\sqrt{2}$ の正方形を敷き詰めてもその正方形の点同士は条件を壊さない。
周辺が危険になっているので、他の色の正方形を敷き詰めることを考えていくと、
赤青赤青　 $\cdots$
黄緑黄緑
赤青赤青
黄緑黄緑　 $\cdots$
$\vdots$

みたいにすると、何一つ条件を壊さないようなので、このまま $45$ 度回転して元の座標に戻すとOK

感想

直感的にCのほうがBよりdiff高いのなんか違和感がある
Aみたいな問題は考察を間違えると、かなりドツボにはまりそう。　全然わからなかったら一回リセットして考え直してみるといいかも知れない。

反省

面白くない駄文ですが書きます。
競プロの時間を減らして色々なことに手を付けているつもりだったんですが、やっぱりつもりだったようです。考えてみれば何も達成してないのに他のことをやる意味がなかったです。今の所、学業と競プロをやり続けなければ、自分に何の価値も無いようなので頑張ります。　
このまま、社会性も実力もないのでは、将来大したこと無い事をしているヤバイおっさんに成り果てそう

2020-05-03

ABC165 参加メモ

ABC 競技プログラミング

発想自体は思いつきやすいが、そこからちゃんと詰めて書けるのかというところを頑張るべきだった。躓きすぎて5ペナABCDE5完(91:40+25:00)
1974->1945(-29, Perf = 1642, 859th) 調子悪いにしたら激冷えにはならなかったなと思っている

A

そうだよなあ…b/k*bで位置が出てくるわけだからそれがA以上なら包含してるんだよなあ
条件ミスって1WA

B

val += val / 100ですね
なんか思いつけなかった

C

こういう組み合わせは仕切ると出てくる。
すると最大でも $\binom{19}{10} = 92378$ くらいになるみたい
つまり全列挙してそれぞれポイントを計算すると $\mathrm{O}((N+M)_{N+M-1}\mathrm{C}_{N})$ くらい出てくる

D

とりあえず $B-1 \leq N$ のときだけ考える
見た感じ、 $x$ は $nB-1$ とかにしておくと良さそう(それ以外は $nB-1$ まで数を上げると $\lfloor Ax/B \rfloor$ だけ無条件に値が上昇するので最適解は $nB-1$ の中にあることが分かる)

もう実は $n$ の上限は小さいので十分間に合うけど、実は答えは $x=B-1$ のときになっている。
理由は $x=nB-1$ の解が $x=B-1$ のときと一致するからである。

あと言ってなかった $N \lt B-1$ のときは、 $x=N$ のときが一番大きいので、まとめると、
$x=\min(B-1, N)$ のときが答えである。

E

ダメな条件を列挙してみる $a_i \lt b_i$ とすると

$b_i-a_i=b_j-a_j$
$(a_i+N)-b_i=(a_j+N)-b_j$

さえ大丈夫ならいいっぽい
もし $b_i-a_i = d$ だったら、 $(a_i+N)-b_i = N-d$ になっているので、 $d \lt N/2$ みたいになるようにやっていけばかぶらないで済みそう
実際、 $M \times 2 + 1 \leq N$ という制約があるので頑張れば見つかりそう

差が奇数同士のものを集めると、例えば

みたいに入れ子にする発想が出る。
同じように偶数もこの入れ子の隣とかに

7 11

8 10

みたいにおいておくと、今の問題なら $M=5, N \geq 11$ について解くことができた。

これをちゃんと一般化して解けば終わり

F

LISを１段階戻す操作が適切にできれば解ける。
木が分岐しているときはある一方を深さで進めて処理したときにもう一方をやるにはLISの状態をもとに戻してからやらなきゃいけない。
もとに戻すにはLISの挿入操作をする前に　挿入するところのもとのデータと位置さえ持っておいて、戻すときにそのデータに戻せば $\mathrm{O}(1)$ でできる。
適切に潜ったり戻ったりして、その際に操作を行えば、すべての $k$ についてサイズは求まるので $\mathrm{O}(N)$ で解けました。

感想

スムーズに行かなかったなあ、Fにたどり着く前に時間をかけすぎてしまった
タイムスケジュールをきちんと組んで競プロに望んでいくのが好ましい。

2020-05-02

ABC164 参加メモ

ABC 競技プログラミング

１ヶ月位競プロをしていなかった(生活も難しい)
ただ、Ratedのコンテストには出続けていた(そうでなければ自分の実力を確かめられないため)
今回は問題(特にD, E)が自分にとって解きやすかったのでそこで速解きしてパフォは良かった
1929->1974(+45, Highest) Perf = 2311

A, B, C

Aは数の比較して終わり
Bは $\lceil C/B \rceil と \lceil A/D \rceil$ で倒すターン数が分かるので比較して終わり
Cはsetに入れるとできる

D

この問題はABC158-Eを少し特殊にした版　だけどABC158-Eの解で十分間に合うのでそれでやる
tinumukiti631.hatenablog.com
要点はSuffixに関する答え $U_i$ は $\mathrm{O}(N)$ で求められるのと、 $2019$ と $10$ は互いに素になっているので、 $U_i - U_{j+1} = 0$ になっていれば部分文字列は $2019$ で割り切れることになる。つまり、 $U_i = U_{j+1}$ であるような $(i, j)$ を求めればいいので、これはmapとかで左から数を記憶しながらやっていくと、求めることができる。

E

高校の頃に最短路系の問題はかなり解いた気がする。
ヘビのJOI君(JOI2016-2017-yo6)とか解くとこういうのは思いつくと思う

まず、最短時間を求めたいけど、銀貨が減るので補填しながら行かなければいけない。
ただ、[現在の駅][銀貨の数] の条件があれば、答えを最小のものにまとめても大丈夫
ところで、消費する銀貨は $1$ エッジで $50$ までになっているので、 $N$ 回移動することを仮定しても $2500$ くらいにしかならない。よって、大体配列のサイズは $N^3$ 程度になる。

$D_i$ の重みで銀貨を $C_i$ だけ増やすエッジと、銀貨を消費しながら $B_i$ だけ重みをつけて駅を移動するエッジの２つを適切に貼れば、あとは Dijkstra することでこの問題は解ける。

F

発想自体はそんなに難しくないと思う、実装がきつすぎるんだよな。
実装の方針をちゃんと立てるのは大事。というか、実装方針に関する考察という概念が競プロにはあるんじゃないかと思う(これは言わずもがなかもしれないが)。

まず、bitごとに操作が独立なので、bitごとに考えるという方針ができる。(ここで、 $u_i, v_j$ は $U_i, V_j$ に対して着目しているbitの値ということにしておく。)
$a$ の値はとりあえずすべて $0$ にしておく。どんどん $1$ を増やしていくというやり方だ。

次に、 $a_{i,j}$ について $1$ でなければならないところと $1$ にしても解に影響を与えないところを考える。
$1$ でなければならないところは列か行に対して「論理積が $1$ 」である。これを探して、適切に $1$ にする。
$1$ にしても解に影響を与えないところは、論理和論理積にかかわらず、 $u_i = v_j = 1$ であるようなところである。このようなところは、 $0$ になっている利点がないので $1$ にしてしまおう。

このようにしておくと、条件を満たさないところというのが、「論理和が $1$ になる必要があるような行または列でまだ $1$ になっていないところ」に限定される。

まず条件を満たさない行について考えると、行の中の要素のうちどこかを $1$ にできればいいわけである。
$1$ にするのが許される列は、「論理積が $0$ 」の列に限る。このとき、その列にある $0$ の数が $2$ 以上あれば列の値を $0$ に保ったままにしながら要素を $1$ に変換することができる。
このような列を見つけながら各行やっていくと、行に対する条件を満たせる。
列の条件も上記のことを同じようにやっていけば満たすことができる。しかも独立なので行の操作に依存していない。

これで $a$ は完成する。これは $a$ の解を持つものに関しては必ず正しいものを構築できる。ということは、正しいものを構築できていないものは $a$ の解を持たないということになるので、 $a$ が条件を満たしているのか判定して満たしていないものを $-1$ を出力すれば良い。
その他は、 $a$ として出力する。

こういうのを解くときは、データに関する統計みたいなものを出しておいて、いつでも使えるようにしたほうが嬉しい。今回なら「ある行(列)の 0 の数, 1の数」とか。大体、統計を出しておいたほうが実装が簡単になることが多いし、シミュレーションできるので頭が壊れることがないんじゃないかな。

感想

今回は山を当てたけど、苦手な問題を苦手のままにしておくと、よくない。

2020-03-28

ABC128, 129 DEF バチャ

競技プログラミング ABC

not-522.appspot.com
toyamaくんが参加してくれました　ありがとう　ありがとう

AB, DE解いて4完でした(400, 500に結構つまずいたというのもあったので反省)
Cが惜しかったです
今回はABCDEの解説をしてFは次のバチャで解きたいと思います

A: ABC128-D - equeue

操作Cや操作Dを先にやるのは明らかに無駄なので操作A, Bが終わったあとにやる。
すると、操作C, 操作Dはただ宝石を捨てるだけの操作になる。

こうすると、操作Aを何回やるか, 操作Bを何回やるかを決めると、何回宝石を捨てられるかがわかる。

操作Aを何回やるかと、操作Bを何回やるかを決めて取り出す->負の価値を持った鉱石を出来る限り捨てる
で決め打ちした時の最大値が出るので、後は全通り試して終わり

B: ABC128-E - Roadwork

座標 $X$ が時刻 $\lbrack S, T)$ のときに通行止めになっていると、時刻 $\lbrack S-X, T-X)$ に出発した人が止まらずに座標 $X$ に来た場合に通行止めを食らうという考察が出来る。

$i$ 番目の人は通行止めを食らう可能性のある座標のなかで一番座標が小さいものに対して実際に通行止めを食らうことになる。

そのため、 $i$ 番目の人を見ている時に、通行止めを食らう可能性のあるものが列挙できていて、かつ一番小さい座標を持てれば良い。

それをするには、始点と終点である $S-X, T-X$ を $D$ の座標に対応させて(座標圧縮?)、それぞれ、 $X$ を insert, erase するようなマークをつけておく。

そして、setやmultisetを使い、左から、命令に従って insert, erase をするようにする。
setの中のそのときの一番小さい座標を取り出して、おわり

C: ABC128-F - Frog Jump

動きを確かめてみると、図のようになっていれば問題文を満たす動きが出来ることが分かる。

f:id:tinumukiti631:20200328151715j:image

動いていくと、偶数回動いた先である赤丸と、奇数回動いた先である青丸に分かれる。
赤丸は座標 $0$ から伸びており、青丸は座標 $N-1$ から伸びている。
そして、図で書いたような条件があれば、手順2 と手順3のような動きを実現できる(矢印で実際に構成できているように)。
このような $d$ と赤丸, 青丸の数の決め方は、 $\mathrm{O}(N \log N)$ 程度しか無い(調和級数)ので、 $d$ に対して簡単な累積和を行って求めることで、 $\mathrm{O}(N \log N)$ で求められる。
境界条件があって、気をつけないといけないのは、赤丸と青丸が被らないかどうかと, $B > 0$ になるように動けるかである。

D: ABC129-D - Lamp

上下左右どのくらい'.'が連続しているかを4方向累積和を取って全部足して-3すると求まる。
1-indexed で解けば良かったなてこずってしまった

E: ABC129-E - Sum Equals Xor

典型的な桁DP
$A+B = A \oplus B$ を満たすには、 $A, B$ のある桁が $1$ 同士になっていないことが条件である。
あとは $A \oplus B$ が $L$ より大きくならないように調整してDPする。

$dp1 \lbrack i \rbrack$ … $1$ から $i$ 桁まで同じ値を選んできたために、 $L$ 以下になるかどうかが保証されていないようなものの個数
$dp2 \lbrack i \rbrack$ … $1$ から $i$ 桁のどこかの桁について小さい値を選んでいるので、答えが $L$ 未満になることが確定しているようなものの個数

この遷移をちゃんと考えて桁DPすればオーケー。

感想

C惜しかったなあ。考察を切り詰め切れてないのは事実で赤丸青丸のやつに気づけてても $A$ を決めようとするなどしてて問題を完全に帰着させられていない。考察段階で元の問題を少し切り離して考えてみるとか必要そう