競プロ解法メモ

自分用のメモが主目的なので厳密性は求めないでください

yukicoder No.1842 Decimal Point

問題:No.1842 Decimal Point - yukicoder

 やっていることは公式解説と同じだと思う。自分みたいに「具体例がないと分からん」っていう人用。

A=314,B=13,C=3

とする。つまり

314\div 13の小数第3位

を求める。筆算で求めるとして、小数第3位の直前までやると以下のようになる。

f:id:mkawa2:20220219104245j:plain

求めたいのは緑のマス。ここを決めるためには何が分かればいいかというと

f:id:mkawa2:20220219104921j:plain

最後の数(=5)が分かればよい。よって、まずこの数を求めることを考える。では、この数が何かというと、以下のように小数点以下に0を付けて考えてやれば

f:id:mkawa2:20220219105450j:plain

31400\div 13の余り

だと分かる。つまり問題のA,B,Cを使っていうと

Aに0をC-1個付けて、Bで割った余り

ということ。この余りをRとして式で表すと

R=A\cdot 10^{c-1}\% B

となる。これさえ求まれば、あとは以下のように

f:id:mkawa2:20220219110130j:plain

0を付けて(=10倍して)、緑に入る数字を求めればいい。この場合なら

50\div 13=3\ldots 11

なので以下のように3が入る。

f:id:mkawa2:20220219110741j:plain

つまり、先程のRを使えば、答えは

\lfloor\frac{10R}{B}\rfloor   ※\lfloor\  \rfloorは切り捨てを表す

となる。

 

提出コード:

#740773 (Python3) No.1842 Decimal Point - yukicoder 

ABC226 H - Random Kth Max

問題:H - Random Kth Max

 

 解説動画で分からなかったところを、あとから理解したのでメモ。

 

① 「k番目の値がx以上」⇔「x以上の値がk個以上」

 これはあとから考えてみれば当たり前だった。

 ある数列を大きい順に並べる。このとき、k番目の数をx以上にしたい。

f:id:mkawa2:20211108184549j:plain

それには、x以上の数をk個以上作れば良い。

f:id:mkawa2:20211108184124j:plain

ということだった。

 

② 「確率変数がx以上になる確率を求める関数f(x)」を積分すると期待値が求まる

 f(x)を「結果がx以上になる確率」としたときに、期待値はf(x)積分することによって求まる。図で表すと以下の通り。

f:id:mkawa2:20211108230851j:plain


このことを離散値の場合を例にとって、直感的に理解したい。

 以下のような、確率が均一でないサイコロがあるとする。

f:id:mkawa2:20211108231705j:plain

これに「x以上が出る確率f(x)」の欄を加えると次のようになる。

f:id:mkawa2:20211108232043j:plain

f(x)は上段を右から累積和にしたものになる。そして、このf(x)を図で表すと以下のようになる(縦軸の1目盛りは\dfrac{1}{11})。

f:id:mkawa2:20211108233728j:plain

このとき、例えばx=4(左から4番目の棒)について考えてみる。棒の高さが表しているのは「4以上になる確率」だ。では

「4になる確率」は?

というと、「(4以上になる確率)-(5以上になる確率)」なので、この部分になる。

f:id:mkawa2:20211108234840j:plain

ところで、

期待値は「A ✕ (Aになる確率)」の和

で求められる。図の中で「4 ✕ (4になる確率)」が表すものは、以下の部分の面積になる。

f:id:mkawa2:20211109000906j:plain

これを残りの目についても考えると

f:id:mkawa2:20211109000319j:plain

このようになる。よって「A ✕ (Aになる確率)」の和、つまり

期待値はグラフの面積になる!

ここから、積分の解説でお馴染みのように棒の幅を限りなく細くしていけば、f(x)が連続な関数の場合に置き換えることができる。ちなみにf(x)のことを累積分布関数というらしい。

 

ABC210 F - Coprime Solitaire

問題:F - Coprime Solitaire

きちんとした解法や証明は公式解説で。ここでは主に計算量削減パートをメモ。多分、解説動画でsnukeさんが最初にACした方針。

 ・解法の大まかな流れ

① すべてのカードの表と裏を頂点としたグラフを考える(つまり頂点数がカード枚数の2倍になる)

② 「頂点uを使ったら頂点vも使わなくてはならない」という関係を有向辺u→vで表す

③ 強連結成分分解(SCC)をして、同一成分内に同じカードの表と裏が含まれていなければ"Yes"、含まれていれば"No"

ここで問題となるのが②。問題の条件より

頂点a,b,c,d,e,fのうち、使えるのは1つ

 という状況が生まれる。頂点aの反対の面を頂点\overline{a}とする。このとき、例えば頂点cからの辺は次のようになる。

f:id:mkawa2:20210720130415j:plain

頂点cを使う場合、頂点a,b,d,e,fは使えない。よって、頂点a,b,d,e,fの反対の面を使うしかなくなる。すると、上の図のような辺になる。

これを残りの頂点a,b,d,e,fからもやるのだが、この通りすべてやると

辺の本数がO\left( N^{2}\right)となってTLE

してしまう。ここからが本題。では、どのように辺を張ればよいか。

まずは次のような準備をする。以下のように、反対の面の頂点1つにつき2つの頂点を増やす。 

f:id:mkawa2:20210720130422j:plain

そして、右向き用の辺(赤)と左向き用の辺(青)を張る。

f:id:mkawa2:20210720130425j:plain

これで準備完了。先程の頂点cからの辺は以下のような2本で済む。

f:id:mkawa2:20210720130418j:plain

どの頂点からも2本か1本の辺で済むので

辺の本数がO\left( N\right)で抑えられる

(※1つの頂点が素因数ごとに何度か登場するので厳密にはO\left( N\right)ではないと思うが、それはブログタイトル下のコメント通り。)見ての通り頂点と辺が結構増えるので、定数倍が重い気がするが、元々Nが小さめであるし、1秒ちょっとで通ったので気にしない。

提出コード:Submission #24389859 - AtCoder Beginner Contest 210

 

yukicoder No.1151 チャレンジゲーム

問題:No.1151 チャレンジゲーム - yukicoder

Nが小さいので、全状態を列挙してDPする。状態の変数としては、(先手が取ったカード)、(後手が取ったカード)、(どちらの番か)の3変数ですべての状況を表現できる。これで、勝つ確率を求める関数P(3変数)でも作って、確率の高い遷移先を選んでいくというのが基本だと思うが、

今回はそれができない

なぜなら

「2回」の遷移後に元に戻ることがあるから

今、先手の番だとして図にしたのが次の画像 

f:id:mkawa2:20210610230728j:plain

S:先手が取ったカード、T:後手が取ったカード(両方ともbit表現)

S_{i}っていうのは、Sの状態からA_{i}のカードを追加した状態。T_{j}とかT_{k}も同様。

このように2手先でループしているので、ここまでをまとめて考えないと先手がどのカードを狙うのが最適かは分からない。よって、関数Pを次のように定義する。

P\left( S,T\right) :先手の番において、先手の取ったカードがS、後手の取ったカードがTのとき、先手が勝つ確率

求めたいのはP(0,0)

ここからは上の図を利用して、P(=P(S,T)のこと)を求める式を考える。方針としては、P=(Pを含む式)という等式を作り、これをPについて解く。

先手が狙うカードをA_{i}に決め打ちしたとき、Pは次の式で表される。

P=\dfrac{1}{A_{i}}P_{1}+\dfrac{A_{i}-1}{A_{i}}P_{2}   ・・・★

先手はこれが最大になるようにA_{i}を選ぶことになる。次にP_{1}を考える。P_{1}はループとは関係のない値なので、A_{i}を固定してしまえば定数として求めることができる。後手がA_{j}を狙うとすると

P_{1}=\dfrac{1}{A_{j}}P(S_{i},T_{j})+\dfrac{A_{j}-1}{A_{j}}P(S_{i},T)

となる。ここで重要なのは、A_{j}を選ぶのは後手なので

P_{1}が最小となるようなA_{j}を選ぶ

こと。これでP_{1}の値は求まるので、これ以降は定数として扱う。次にP_{2}について考える。後手がA_{k}を狙うとすると

P_{2}=\dfrac{1}{A_{k}}P(S,T_{k})+\dfrac{A_{k}-1}{A_{k}}P

となる。この式を式★に代入し、Pについて解くと

P=\dfrac{A_{k}P_{1}+(A_{i}-1)P(S,T_{k})}{A_{i}+A_{k}-1}

となる。これでPを求めるための準備ができた。ikを2重ループで全探索する。その際、

iPが最大となるように

kPが最小となるように

決めるようにする。もう少し詳しく言うと

iを固定する→kを全探索して上の式よりPの最小値を求める →各iについて求めた最小値のうち最大のものを最終的なPとする

という流れになる。すべて取られた状態から、取られた枚数の降順にdpしていけばいい。初期値は、すべてのカードが取られたときで、先手の得点の方が多ければP(S,T)=1、そうでなければP(S,T)=0となる。

提出コード:

#665321 (PyPy3) No.1151 チャレンジゲーム - yukicoder

yukicoder No.1022 Power Equation

問題:No.1022 Power Equation - yukicoder

解説を読んだものの、自分で消化するのに苦労したので記録。

まず、a^{b}=c^{d}を満たす条件を考えてみる。

a=c=1のとき・・・・・・b,dが何でもよいのでN^{2}通り

b=dのとき・・・・・・a=cならばよいのでN^{2}通り

a=c=1かつb=dのとき・・・・・・N通り

よって、全部で\left(2N^{2}-N\right)通り。これらは別に数えておいて、それ以外を考える。

a,b,c,d\leq10^{9}なので、大き過ぎて実際に計算していくのは無理。そこで、自分で具体例を作ろうとしてみると次のような方法が見つかった。

2^{12}=2^{12}

2^{2\times6}=2^{3\times4}

\left(2^{2}\right)^{6}=\left(2^{3}\right)^{4}

4^{6}=8^{4}

これを逆に考えると、a^{b}=c^{d}という式はa,cを変形して

\left( t^{x}\right) ^{b}=\left( t^{y}\right) ^{d}(ただしxb=yd

という形に出来ることが分かった(素因数分解の一意性から、必ずできることは証明できそう)。それでは、これにあてはまるt,x,y,b,dを数え上げればいいかというと、大きな問題がある。それは、t,x,y,b,dが異なっていてもa^{b}=c^{d}の形にした時に同じ式になってしまう場合があることだ。例えば、

4^{6}=16^{3}

という式は

\left(2^{2}\right)^{6}=\left(2^{4}\right)^{3}

という形にも

\left(4^{1}\right)^{6}=\left(4^{2}\right)^{3}

という形にもできてしまう。よって、重複が出ないような数え上げ方が必要になる。そのために、数え上げのルールを1つ追加する。それは、

x,yが互いに素になる場合だけに限定する

というもの。前述の例で言えば、下の形だけを許すことになり、上の形を重複して数えることはなくなる。さらに、但し書きのxb=ydからb=ky,d=kxk自然数)となるので、まとめると

\left( t^{x}\right) ^{ky}=\left( t^{y}\right) ^{kx}(ただしx,yは互いに素)

ということになる。 あとは、x,yを全探索して、そのときの\left(t,k\right)が何通りあるか数えていく。t^{x}=a\leq Nなので、tが最小の2の場合を考えても、x\log _{2}Nぐらいまででよさそう。yについても同様。

提出コード:#645190 (Python3) No.1022 Power Equation - yukicoder