2022-02-19

yukicoder No.1842 Decimal Point

yukicoder

問題：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

2021-11-09

ABC226 H - Random Kth Max

AtCoder

問題：H - Random Kth Max

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

①　「ｋ番目の値がｘ以上」⇔「ｘ以上の値がｋ個以上」

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

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

f:id:mkawa2:20211108184549j:plain

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

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)$ を図で表すと以下のようになる（縦軸の１目盛りは $\dfrac{1}{11}$ ）。

f:id:mkawa2:20211108233728j:plain

このとき、例えば $x=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)$ のことを累積分布関数というらしい。

2021-07-20

ABC210 F - Coprime Solitaire

AtCoder

問題：F - Coprime Solitaire

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

・解法の大まかな流れ

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

②　「頂点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

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

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

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

2021-06-11

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

yukicoder

問題：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$ を求めるための準備ができた。 $i$ と $k$ を2重ループで全探索する。その際、

$i$ は $P$ が最大となるように

$k$ は $P$ が最小となるように

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

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

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

提出コード：

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

2021-04-07

yukicoder No.1022 Power Equation

yukicoder

問題：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}$ の形にした時に同じ式になってしまう場合があることだ。例えば、