3匹の猫

みみねこの競プロ精進メモ

AtCoder Regular Contest 117参加記(~C問題)

600点問題が解けると嬉しい!!
f:id:mmnkblog:20210418231705p:plain

A - God Sequence

各要素が正の整数である二つの数列a, bを考えることにする。この時、数列aの要素の総和と数列bの要素の総和が等しくなれば良い。A=Bのとき明らかに、a_i = b_iとすることで条件を満たすことができる。

A\lt B(数列aより数列bの方が長い)と仮定する。(逆ならswapする)
この時数列bの要素をb_i = iとなるように決めると、数列aの最後の要素を除いてa_i = iとし、最後の要素をa_A = \sum_{k=A}^{B} kとすることで条件を満たすことができる。最後の要素で数値を調整するイメージ。

計算量はO(A+B)

B - ARC Wrecker

階数が同じビルがあった場合、どんな操作をしてもそれらのビルの階数は等しいままである。よって回数が同じビルはひとまとめにしておく。以降、すべてのA_iに重複が無いものとして考える。ついでに数列Aを昇順に並び替えておく。

Xとして選ぶ数字は数列Aの要素のどれかとしてよい。また、X=A_iとしたとき、少なくともA_iの値は1減るため、A_iは最大でもA_i回しか選べない。

実験するとわかるが、操作の順番は結果に関係しない。つまり「各iについて、X=A_iを何回選ぶか」という情報だけわかればよい。さらに、X=A_iとした場合、i \le jを満たすすべてのjについて、A_jの値は1減る。先ほど昇順にソートした理由はこれで、A_iが小さい順から「何回A_iを選ぶか」を決めていくことで数え上げることができる。

XA_ik回選ぶとすると、A_iA_{i+1}は共にkずつ減る。A_iの値が変わらないようなXA_{i+1}を選ぶ回数の最大値は、(A_{i+1} - k) - (A_i - k) + 1 = A_{i+1} - A_i + 1回である。この数値はkによらず一定である。
よって(A_1 + 1)\times \prod_{ i = 1 }^{N-1} (A_{i+1} - A_i + 1)が答え。計算量はソートがボトルネックとなり、O(N\log N)

C - Tricolor Pyramid

文字を選ぶ操作をなにかの演算として表現したい。各文字を0, 1,  2で置き換えて演算結果を表にまとめる。二つの数をa, bとしたとき、演算結果は -(a+b)\bmod 3と表せる。

左からi番目の整数をa_iとすると、最上段の整数に含まれる各a_iの個数は二項係数を用いて表せる。具体的に、最上段の整数は(-1)^{N-1} \times \sum_{i=1}^{N} ({}_{N-1} \mathrm{ C }_i \times a_i) \bmod 3である。なので素直にこの式を計算すればよいが、\bmod 3上の{}_{N-1} \mathrm{ C }_iの値を求める方法がわからなかった。

http://www.junko-k.com/collo/collo29.htm
上のサイトを見ながら考えたところ、N-13^kで割った余りで場合分けすることでO(\log N)で求められることに気が付いた。なのでその場合分けを丁寧に書いて計算し解答。計算量はO(N\log N)

ちなみにコンテスト後にTwitterを眺めていたところ、この方法は「Lucasの定理」という名前がついていて、3進数での各桁の数字をもとにして計算するらしい。コンテスト中に定理を導出した自分すげえ!(素直)

感想

最強学生コンで失ったレートをほとんど取り返したので満足。

第二回日本最強プログラマー学生選手権参加記(~E問題)

脳みそ、うごけー!(動かない)
f:id:mmnkblog:20210417182131p:plain

A - Competition

難しすぎないか…?最初に考えた方針が「両方の肉を同じだけ買ったときの金額で考える」ものだったが上手くいかず、一度B問題を解きに行って戻ってきた。スーパー高橋で売っている肉の1gあたりの価格はY\div Xで求められる。同様に、スーパーすぬけで売っている肉の1gあたりの価格は(解であるZg当たりの価格をAとすると)A\div Zで求められる。この二つの式の大小関係を式で表すと、
\dfrac{Y}{X} \gt \dfrac{A}{Z}
となる。さらに式変形して、
\dfrac{YZ}{X} \gt A
となる。この式の左辺は定数なので、Aは一通りに定まる。割り算の扱いに注意。計算量は、O(1)

B - Xor of Sequences

制約より、数列A, Bに含まれる整数の範囲は1以上1000以下である。この範囲に含まれる整数が解の条件を満たすかを全探索する。
数列に同じ整数が重複することはないという制約があるため、整数をxとすると、数列A, Bに含まれるxの個数がちょうど1個なら条件を満たしているといえる。(ちなみにこの処理を、整数xを見つけるたびに真理値型のフラグに対してtrueとのXORを取るという処理に変えると、最終的なフラグの値がそのまま解となる。)
これを1000回繰り返す。計算量は、O(N A_{\max})

C - Max GCD 2

ユークリッドの互除法での2数の関係から考えてみるとわかりやすい。
整数x, yの最大公約数がdであるとき、x, yはともにdの倍数である。A以上B以下の区間内にdの倍数が2個以上存在すれば、xyの最大公約数がdとなるような(x, y)を選ぶことができる。これは、「A以上の整数のうちdの倍数の最小値」にdを加えた値がB以下かどうかを判定すればよい。
dとして考えられる値の最小値は1、最大値は\dfrac{B}{2}であるので、制約よりこれらの間にある整数を全探索しても間に合う。計算量は、O(B)

D - Nowhere P

これ以降の問題は解けていない。
何か簡単な数式で解を表現できるらしいが、そこまで至らなかった。
コンテスト中の方針としては、「とても良い列」ではない列のほうをカウントして全体から引く作戦で考えていたが、数列を重複して数えてしまう沼にハマって抜け出せなかった。

E - Level K Palindrome

レベルKの回文として考えられる文字列の長さの最小値を考える。最小の長さを持つレベルKの回文は、レベル1の回文aを、間に何も挟まずに組み合わせていくことで作れる。この時の長さは、2^{K-1}である。よって、高橋君が持っている文字列の長さをNとすると、N \ge 2^{K-1}を満たしている必要がある。ついでにいうとK19以上だと確実にimpossibleである。
さらに、レベルKの回文を2つのレベルK-1の回文に分解するとき、Nが偶数なら2分割、Nが奇数なら間に一文字挟んで2分割、となるしかないので、その文字列を構成するレベルk0\le k \le K)の回文の長さは一意に定まる。レベル0の回文の長さも決まるが、このときどの文字を変えるのが最適なのかがよくわからなかった。レベル0の回文は回文であってはいけないという制約が邪魔だった。

感想

レートが50下がって気分も下がったが初めてお酒を飲んで全部忘れたのでOK

AtCoder Beginner Contest 198参加記(~E問題)

コーナーケースに気を付けろ!!
     
f:id:mmnkblog:20210411231102p:plain

A - Div

A君が得るお菓子の個数をA個、B君が得るお菓子の個数をB個とすると、B=N-Aという等式が成り立つ。この式から、Aを固定するとB1通りに定まること、A, Bがともに正の整数でなければならないことを考えると、Aが取りうる範囲1\le A\le N-1の中にある整数の個数、つまりN-1が答えとなる。計算量は、O(1)

ちなみに制約がゆるいので、brainfuckでも簡単なif文の処理が書ければ解ける。

B - Palindrome with leading zeros

問題文中の操作は、「Nを文字列としてみたときの末尾から連続している0をすべて削除する」と言い換えられる。こうすることで、操作後の文字列N'が回文かどうかを一度判定するだけで答えが求まる。N=0のときの処理に注意。計算量はO(\log N)

C - Compass Walking

2歩歩くことで、ユークリッド距離が2R以内の点に移動することができる。また、x歩以下で到達できる範囲は、原点から距離がxR以内の範囲である。このことから、解xを二分探索して求めることができる。
ただし、1歩歩くことで到達できるのは原点からちょうどR離れている点だけであるので、二分探索して得られた解がx=1だった場合にのみ、原点からの距離で場合分けする。

二分探索について。ルートを使うと小数誤差にやられる危険性があるので、整数のまま計算する。具体的には、距離の大小さえわかればよく、距離は負の値を取らないので、距離の2乗をそのまま比較する。式は以下の通り。

X^2 + Y^2 \le x^2 R^2

また、解の最大値は2\times 10^5程度と見積もれるが、距離の2乗で比較する方針だと上式の右辺が最大で4\times10^{20}となりオーバーフローするので、二分探索するときの解の最大値は2\times 10^5\div rとした。こうすると右辺は単にx^2となる。計算量はO(\log (X+Y))

コンテスト中はこれで十分だが、より厳密に議論すれば二分探索を用いなくてもO(1)で答えを求めることができる(公式解説より)。考察をサボれるときはサボることも大事。

D - Send More Money

条件がごちゃごちゃ書いてあるが、普通に覆面算を解くだけの問題。各英小文字に一桁の整数を割り当てるので、文字の種類数が11以上ある場合は解なし。

文字の種類数が10以下だった場合、各文字に整数を割り当てる方法を全通り試す。文字の種類数をaとすると、{}_10 \mathrm{ P }_a通り試せばよいことになる。C++のnext_permutation関数に長さ10の順列を与えてループを回し、順列の先頭a個だけをみて実際に文字に割り当て、N_1 + N_2 = N_3が成立するか確かめる。計算量はO(N!)

E - Unique Color

与えられるグラフは木であるので、2頂点間を結ぶパスは必ず1つだけ存在する。もちろんそのパスが最短である。また、木の頂点1から頂点xまでのパス上に頂点yが含まれていた場合、そのパスに頂点1から頂点yまでのパスが完全に含まれている。

以上のことより、頂点1からDFSをして「よい頂点」でない頂点を探すこととする。具体的には、DFSをしながら通った頂点の色をメモしていき、頂点xの色がすでに登場しているなら答えから外す、ということをしていけばよい。

メモするための道具として集合(set、挿入・削除がともにO(\log N))を用いたがTLEしてしまった。setのかわりにunordered_setを使ってみたが変わらず。しかもこの方法はメモリも大量に使うため非常に重い。
もう少し考えると、DFSで戻ってくるとき「どのタイミングで色cが使われなくなったか」は「どのタイミングで初めて色cが使われたか」の解と等しいため、setを使わず、bool配列で管理することができる。
計算量は、O(N)

F - Cube

むずすぎ

感想

青パフォだったのでうれしいけど、Eでの2ペナがもったいないと思った

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)解法メモ(全問題)

タイトルが長すぎる

リアルタイムで参加できなかったコンテストのブログが抜けてて気になったので、暇なときに解き直してブログを書くことにしました。

A - Discount

算数。割合の計算は比を使った式で書くとわかりやすいと個人的に思う。
A:100 = B:x
と考えてもいいし、
A:B = 100:x
と考えてもいい。どちらにせよ
x = \dfrac{100B}{A}
という式になる。比を使った式の好きなところはこういうところ。

何パーセント引きか聞かれているので、100 - \dfrac{100B}{A}が答え。計算量はO(1)

B - Play Snuke

1軒しかお店が無いとする。このとき、A分かけてお店に着いた時、スヌケマシンの在庫は\max (X-A, 0)である。在庫が1以上のとき、つまりX-A1以上のときに限りP円でスヌケマシンを買うことができる。

お店がN軒に増えた場合でも各店舗での購入条件と購入金額はかわらない。また、どのお店を選んでも、その選択が影響することはないので、スヌケマシンを買うことができるお店のうち一番安く買えるお店での購入金額を求めればよい。計算量はO(N)

C - Unexpressed

事象Aとその余事象A^cの和は全事象\Omegaである。
a^bと表せないもの」 = 「全体」 -a^bと表せるもの」
なので、「a^bと表せるもの」の個数をカウントする。

a^bと表せるもの」の個数を上から評価する(最大値を見積もる)。
aを固定したとき、bを増やすとa^bも増加する。よって、1 \le a^b \le Nを満たすbの個数はb = \log_a Nである。
2 \le bに注意すると、aは最大で\sqrt N程度まで大きくなるので、全体の個数としては\sqrt N \times \log_2 N程度となる。(上から評価しているので、a=2として計算した。)
この値はN=10^5のときでもおよそ1.6 \times 10^6であるため、(a, b)の組を全探索しても実行時間制限に間に合うことがわかった。

カウントするときは重複やオーバーフローに注意して実装する。重複を避けるにはC++のsetなどを用いる。a=\lfloor N \rfloorで探索を打ち切る処理を忘れるとTLEするので注意。計算量はO(\sqrt N \log N)

D - Poker

かなり考えることが多いので順を追って考察する。

まず、「高橋君の勝つ確率」は\dfrac{高橋君が勝つパターンの数}{全てのパターンの数}で求められる。ここで言う「すべてのパターン」とは、すでに表向きになっていて裏向きのカードとして選ばれることのない8枚を除いた9K-8枚から2枚(高橋君の裏向きのカード1枚と青木君の裏向きのカード1枚)を選ぶ方法を指す。よって分母は{}_{9K-8} \mathrm{ C }_2となる。

高橋君に配られた裏向きのカードをx、青木君に配られた裏向きのカードをyと置く。高橋君が勝つパターンの数をカウントしたい。裏向きのカードが何の数かわかれば手札の点数を求めることができるが、ここで9K-8枚の中から2枚選ぶような全探索をするとO(K^2)の計算量となってしまうので実行時間制限に間に合わない。しかし、(x, y)の組み合わせとしては81通りしかないので、xyを決めたとき(x, y)が選ばれるのは何通りか求められれば、高橋君が勝つパターンの数も高速に求められる。

整数iが書かれたカードの残り枚数をC_iとする。x=yなら、C_x枚の中から2枚選ぶので{}_{C_x} \mathrm{C}_2 = C_x(C_x - 1)通りである。x\neq yなら、C_x枚の中から1枚、C_y枚の中から1枚それぞれ選ぶのでC_xC_y通りである。高橋君の手札の点数が青木君の手札の点数より高い場合にこの通り数をそのままカウントに加えることで、確率を求めることができる。

計算量は、手札の枚数をN、カードに書かれた整数の種類数をCとしてO(N+C^3)。この問題ではN=5, C=9であるため十分高速に動作する。

E - Oversleeping

電車の停止する区間は周期的に訪れ、\bmod (2X+2Y)上で一定である。高橋君の起きる区間も同様に、\bmod (P+Q)上で一定である。
ここで、中国剰余定理(CRT)を活用する。この定理は、
aで割るとp余り、bで割るとq余る整数x\bmod (\mathrm{lcm}(a, b))上にちょうど1つだけ存在する」
ということを言っている。さらに、この解となる整数xを構成する効率的なアルゴリズムが知られていて、O(\log(a+b+p+q))で動作する。実装には拡張ユークリッドの互除法を用いることが多いが、atcoder libraryに実装されているcrtをそのまま用いることもできる。

制約より、YQが小さいことがわかる。よって、電車が停止してからi秒後のタイミングと、高橋君が起きてからj秒後のタイミングが初めて一致するときがいくつか求め、(i, j)の組を全探索して最小値を求めればよい。具体的には、以下の2つの合同式を同時に満たす解xの最小値を、0\le i\lt Y, 0\le j\lt Qの範囲で全探索する。

x \equiv X+i \pmod{2X+2Y}
x \equiv P+i \pmod{P+Q}

計算量は、O(YQ\log(X+Y+P+Q))

F - Zebraness

まだ解けていないが、工夫することでフローの問題に帰着できるらしい。

感想

はじめてCRTを学んだが、そこまで難しくなくて食わず嫌いしていたなーと思った。ちなみにCRTは条件式が3本以上あっても解を求めることができる。

AtCoder Regular Contest 116参加記(~C問題)

今回は面白い問題だらけです。あ、既出問題を見つけられるということはその問題の解法を理解しているということだから、そんなに気にすることではないと思います。
f:id:mmnkblog:20210329011049p:plain

A - Odd vs Even

完全既出だったらしい。こんなことがあっていいのか?

いったん制約を無視して愚直に解いてみる。正整数を素因数分解する場合、愚直に\sqrt Nまで割っていく方法でO(\sqrt N)の計算量となる。約数を列挙する場合、各素因数ごとに何個選ぶかを考える。この時、Nの素因数に2が含まれていた場合、少なくともNの約数のうち半分は偶数である。

N=18 の例。

\begin{array}{c|c|c|c}
 \times & 3^0 & 3^1 & 3^2 \\
 \hline
 2^0 & 1 & 3 & 9 \\
 \hline
 2^1 & 2 & 6 & 18
\end{array}

さらにNの因数に4が含まれている場合、Nの約数のうち半分以上が偶数となる。逆に、Nの素因数に2が含まれていない場合、Nの約数が偶数となることはない。
よって、N2で割った余りと4で割った余りを見ることで答えが求まる。今回は大丈夫だが、素因数の話題が出てきたときは01の扱いに注意し、必要なら場合分けして対処する。

計算量は、O(T)

B - Products of Min-Max

整数列Aは順番を並べ替えても答えに影響しないので、昇順にソートする。こうすると、部分列Bの最大値と最小値を決めたとき、その間にある各要素に関してBに含めても含めなくても\max (B) \times \min (B)の値は変わらない。Bの最大値と最小値を全探索すると、計算量はO(N^2\log N)となる。
さらに、最小値を固定したときの式を書き出して\min (B)を括り出し、残った部分の式を他の最小値の場合と見比べると、その部分も効率的に更新できることがわかる。詳しい数式は公式解説に載っている。理解したいなら実際に式変形してみるのが早い。

よって、計算量をO(N \log N)に削減することができる。

C - Multiple Sequences

解けなかった。公式解説の数え上げによる解法がわかりやすかった。
また、問題文の条件に「A_i \neq A_{i+1}」を追加した小問題を考えると、動的計画法+数え上げで解けるらしい。この場合の計算量はO(M\log N)?になると思う。

感想

C問題をコンテスト中に解きたかった。解説を読んで理解できたので、まだまだ成長できそう。

AtCoder Beginner Contest 197(Sponsored by Panasonic)参加記(~E問題)

D問題みたいな数学問題もっと出してもいいんですよ
f:id:mmnkblog:20210328022948p:plain

A - Rotate

文字列で受け取ってもいいが、文字変数を3つ用意して入力順と出力順を入れ替えた方がシンプルに書ける。

計算量は、O(1)

B - Visibility

むずくない?

マス(X, Y)から始めて、上下左右の4方向に向かって探索する。もし探索途中に#が出現したら、それより奥のマスは障害物で遮られて見えないので探索をやめる。この個数をカウントしたものが答え。

計算量は、入力がボトルネックO(HW)。探索自体はO(H+W)である。

C - ORXOR

「長さNの数列を1つ以上の空でない連続した区間に分ける」、つまり、各要素の間に区切りを入れるか・入れないかを独立に選択する方法は全部で2^{N-1}通り。制約よりNは最大でも20なので、全パターンを試しても間に合う。こういう、「選ぶか」「選ばないか」の2択をいくつか選択するような状況の全探索にはbitを活用する。(bit全探索という)
C++では、ORの計算はa|b、XORの計算はa^bと書くことで簡単に計算できる。

計算量は、O(N2^N)

D - Opposite

正多角形の座標のうち、一番離れている2点の座標が与えられる。Nは偶数なので、この正多角形の中心の座標がわかる。
また、正多角形の隣り合う頂点は、正多角形の中心から見てちょうど\dfrac{2\pi}{N}だけ回転している。2次元平面状の座標を回転させるには、回転行列を用いるとよい。具体的には、

\begin{pmatrix}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{pmatrix}
\begin{pmatrix}
x\\
y
\end{pmatrix}=
\begin{pmatrix}
x\cos \theta -y\sin \theta \\
x\sin \theta + y\cos \theta
\end{pmatrix}
を用いればよい。ググると出てくる。
答えが小数になるため、誤差に注意。

計算量は、O(1)

E - Traveler

iのボールを回収するとき、現在の座標をxとすると、
・負の方向に進んでから正の方向に進む
・正の方向に進んでから負の方向に進む
という2通りの行動以外は最適な行動ではない。(引き返した分の時間が損であり、引き返さなくてもすべてのボールを回収できる行動が存在するため。)

つまり各色のボール群を回収する際は上記の2通りの行動のうちどちらかを選んで行動する。この時点で全通りを試すとO(2^N)の計算量となり、実行時間制限に間に合わない。
ここで、ある色までのボールを回収し終えた時点での座標は、その色のボール群のうち一番座標が小さいボールがあった位置か一番座標が大きいボールがあった位置かのどちらかである。それまでの行動を考慮しなくても、前の段階での終了時の座標を全通り試すだけで最適解が求まる。これを、動的計画法(DP)という。

よって、ひとつ前の色の座標の候補(2通り)と、ボールを回収するときの行動パターン(2通り)の全パターンを試して最適なものを選択していけばよい。

計算量は、O(N)


感想

EのDPは比較的簡単な方の部類だと思うのだが、コンテスト中は嘘の貪欲を書いていた。強くなりたい…!

AtCoder Beginner Contest 196参加記(~E問題)

水色なのにCでWA出たのでだめです
f:id:mmnkblog:20210321031700p:plain

A - Difference Max

xを大きくするとx-yの値も大きくなる。逆に、yを大きくするとx-yの値は小さくなる。なので、x-yの値を最大化する場合、xは最大に、yは最小にすればよい。つまりb-cが答え。
最大化するときの基礎的な考えが問われる良問。

計算量は、O(1)

B - Round Down

C++を使ってる前提で話すと、10^{100}なんてデカい数は扱えない。文字列で受け取れば、「小数点以下を切り捨て」したいので、文字列の先頭からピリオドが登場する手前までを切り取って出力すればよいことがわかる。先頭から1文字ずつピリオドかどうか判定しながらちまちま出力すればよい。

計算量は、O(\log N)

C - Doubled

解けなかった。
制約がある程度大きいのでO(1)で解こうと思ったがどこかで実装をバグらせたらしくWAが出た。想定解は前半の桁だけ全探索してN以下か判定するというもの。発想としては全く難しくない。過去に類題も出てるのになぜその発想に至らなかったのか…。

計算量は、O(\sqrt N)

D - Hanjo

制約が小さいので、ピースの置き方を全探索する。再帰関数によるDSFを書いた。残りの畳の枚数と現在の敷き詰め状態を引数として渡す。もし空白のマスが存在していたら、そこに「縦長」「横長」「正方形」の3種類を敷き詰めた状態をそれぞれ作って再帰呼び出しする。もう置けない状態なら1を返す。こう書くと、返ってきた値の総和が求める通り数になる。状態数は超ざっくり見積もって最悪でも3^{16} = 43,046,721通りしかない(実際にはさらに少ない)ので全探索しても実行時間制限に十分間に合う。

E - Filters

考察を書く。間違っている可能性が大いにある。

\max(x, a_i)もしくは\min(x, a_i)が登場するまでにxに足された数の合計をSとすると、\max(x + S, a_i)=\max(x, a_i - S) + Sである。クエリが来る前段階でa_i - Sは定数なのでこの答えはすぐに求められる。さらに\min(x + S, a_i) = -\max(-x, -a_i+S)-Sと書ける。さらにさらに、\max関数の定義から、xのほうが選ばれなければそれ以降xが解に干渉してくることはない、つまり前から見てk番目の\max関数でxのほうが採択されなかったときの答えは事前に計算しておくことが可能である(計算量の話はあとで考える)。なので、x-xのどちらかがある定数より小さいことが判明すれば、その時点で解が定まる。\max関数がK個あったとすれば、数直線がK+1個の区間に分割され、さらにクエリで与えられる数値はその区間のどこかに必ず含まれる。

つまりどういうことかというと、「クエリで与えられたx_i」と「\max関数のしきい値」をソートして前から見ていけばO( (N+Q)\log(N+Q) )で答えが求まるのではないか?ということだ。
この「数直線をK+1個の区間に分割する」ことで先ほどの前計算(xが絡まない場合)の解も求められそう。(ここが求められずに時間が来てしまった)

ここで脳みそが疲れたのでやめた。
公式解説によると、この定義の関数は合成することができるらしく、「定数(低)」「x+\alpha」「定数(高)」の3パターンしかないとのこと。クエリの数がバカ多いので合成できそうだとは思ったが合成した後のグラフの形がなぜエスカレーターみたいになるのかはわからなかった。

F - Substring 2

問題文がシンプルで簡単そうだがFFTを使うらしい。FFTってなんですか?

感想

コンテスト終了後もE問題を粘って解いていたが頭が腐っていたので解けなかった。レートが20くらい無くなった