yukicoder No.1842 Decimal Point
問題:No.1842 Decimal Point - yukicoder
やっていることは公式解説と同じだと思う。自分みたいに「具体例がないと分からん」っていう人用。
とする。つまり
の小数第3位
を求める。筆算で求めるとして、小数第3位の直前までやると以下のようになる。
求めたいのは緑のマス。ここを決めるためには何が分かればいいかというと
最後の数が分かればよい。よって、まずこの数を求めることを考える。では、この数が何かというと、以下のように小数点以下に0を付けて考えてやれば
の余り
だと分かる。つまり問題のA,B,Cを使っていうと
Aに0をC-1個付けて、Bで割った余り
ということ。この余りをRとして式で表すと
となる。これさえ求まれば、あとは以下のように
0を付けて(=10倍して)、緑に入る数字を求めればいい。この場合なら
なので以下のように3が入る。
つまり、先程のRを使えば、答えは
※は切り捨てを表す
となる。
提出コード:
ABC226 H - Random Kth Max
解説動画で分からなかったところを、あとから理解したのでメモ。
① 「k番目の値がx以上」⇔「x以上の値がk個以上」
これはあとから考えてみれば当たり前だった。
ある数列を大きい順に並べる。このとき、k番目の数をx以上にしたい。
それには、x以上の数をk個以上作れば良い。
ということだった。
② 「確率変数が以上になる確率を求める関数」を積分すると期待値が求まる
を「結果が以上になる確率」としたときに、期待値はを積分することによって求まる。図で表すと以下の通り。
このことを離散値の場合を例にとって、直感的に理解したい。
以下のような、確率が均一でないサイコロがあるとする。
これに「以上が出る確率」の欄を加えると次のようになる。
は上段を右から累積和にしたものになる。そして、このを図で表すと以下のようになる(縦軸の1目盛りは)。
このとき、例えば(左から4番目の棒)について考えてみる。棒の高さが表しているのは「4以上になる確率」だ。では
「4になる確率」は?
というと、「(4以上になる確率)-(5以上になる確率)」なので、この部分になる。
ところで、
期待値は「A ✕ (Aになる確率)」の和
で求められる。図の中で「4 ✕ (4になる確率)」が表すものは、以下の部分の面積になる。
これを残りの目についても考えると
このようになる。よって「A ✕ (Aになる確率)」の和、つまり
期待値はグラフの面積になる!
ここから、積分の解説でお馴染みのように棒の幅を限りなく細くしていけば、が連続な関数の場合に置き換えることができる。ちなみにのことを累積分布関数というらしい。
ABC210 F - Coprime Solitaire
きちんとした解法や証明は公式解説で。ここでは主に計算量削減パートをメモ。多分、解説動画でsnukeさんが最初にACした方針。
・解法の大まかな流れ
① すべてのカードの表と裏を頂点としたグラフを考える(つまり頂点数がカード枚数の2倍になる)
② 「頂点uを使ったら頂点vも使わなくてはならない」という関係を有向辺u→vで表す
③ 強連結成分分解(SCC)をして、同一成分内に同じカードの表と裏が含まれていなければ"Yes"、含まれていれば"No"
ここで問題となるのが②。問題の条件より
頂点のうち、使えるのは1つ
という状況が生まれる。頂点の反対の面を頂点とする。このとき、例えば頂点からの辺は次のようになる。
頂点を使う場合、頂点は使えない。よって、頂点の反対の面を使うしかなくなる。すると、上の図のような辺になる。
これを残りの頂点からもやるのだが、この通りすべてやると
辺の本数がとなってTLE
してしまう。ここからが本題。では、どのように辺を張ればよいか。
まずは次のような準備をする。以下のように、反対の面の頂点1つにつき2つの頂点を増やす。
そして、右向き用の辺(赤)と左向き用の辺(青)を張る。
これで準備完了。先程の頂点cからの辺は以下のような2本で済む。
どの頂点からも2本か1本の辺で済むので
辺の本数がで抑えられる
(※1つの頂点が素因数ごとに何度か登場するので厳密にはではないと思うが、それはブログタイトル下のコメント通り。)見ての通り頂点と辺が結構増えるので、定数倍が重い気がするが、元々が小さめであるし、1秒ちょっとで通ったので気にしない。
提出コード:Submission #24389859 - AtCoder Beginner Contest 210
yukicoder No.1151 チャレンジゲーム
問題:No.1151 チャレンジゲーム - yukicoder
Nが小さいので、全状態を列挙してDPする。状態の変数としては、(先手が取ったカード)、(後手が取ったカード)、(どちらの番か)の3変数ですべての状況を表現できる。これで、勝つ確率を求める関数P(3変数)でも作って、確率の高い遷移先を選んでいくというのが基本だと思うが、
今回はそれができない
なぜなら
「2回」の遷移後に元に戻ることがあるから
今、先手の番だとして図にしたのが次の画像
S:先手が取ったカード、T:後手が取ったカード(両方ともbit表現)
っていうのは、の状態からのカードを追加した状態。とかも同様。
このように2手先でループしているので、ここまでをまとめて考えないと先手がどのカードを狙うのが最適かは分からない。よって、関数Pを次のように定義する。
:先手の番において、先手の取ったカードがS、後手の取ったカードがTのとき、先手が勝つ確率
求めたいのは。
ここからは上の図を利用して、(のこと)を求める式を考える。方針としては、=(を含む式)という等式を作り、これをについて解く。
先手が狙うカードをに決め打ちしたとき、は次の式で表される。
・・・★
先手はこれが最大になるようにを選ぶことになる。次にを考える。はループとは関係のない値なので、を固定してしまえば定数として求めることができる。後手がを狙うとすると
となる。ここで重要なのは、を選ぶのは後手なので
が最小となるようなを選ぶ
こと。これでの値は求まるので、これ以降は定数として扱う。次にについて考える。後手がを狙うとすると
となる。この式を式★に代入し、について解くと
となる。これでを求めるための準備ができた。とを2重ループで全探索する。その際、
はが最大となるように
はが最小となるように
決めるようにする。もう少し詳しく言うと
を固定する→を全探索して上の式よりの最小値を求める →各について求めた最小値のうち最大のものを最終的なとする
という流れになる。すべて取られた状態から、取られた枚数の降順にdpしていけばいい。初期値は、すべてのカードが取られたときで、先手の得点の方が多ければ、そうでなければとなる。
提出コード:
yukicoder No.1022 Power Equation
問題:No.1022 Power Equation - yukicoder
解説を読んだものの、自分で消化するのに苦労したので記録。
まず、を満たす条件を考えてみる。
のとき・・・・・・が何でもよいので通り
のとき・・・・・・ならばよいので通り
かつのとき・・・・・・通り
よって、全部で通り。これらは別に数えておいて、それ以外を考える。
なので、大き過ぎて実際に計算していくのは無理。そこで、自分で具体例を作ろうとしてみると次のような方法が見つかった。
これを逆に考えると、という式はを変形して
(ただし)
という形に出来ることが分かった(素因数分解の一意性から、必ずできることは証明できそう)。それでは、これにあてはまるを数え上げればいいかというと、大きな問題がある。それは、が異なっていてもの形にした時に同じ式になってしまう場合があることだ。例えば、
という式は
という形にも
という形にもできてしまう。よって、重複が出ないような数え上げ方が必要になる。そのために、数え上げのルールを1つ追加する。それは、
が互いに素になる場合だけに限定する
というもの。前述の例で言えば、下の形だけを許すことになり、上の形を重複して数えることはなくなる。さらに、但し書きのから(は自然数)となるので、まとめると
(ただしは互いに素)
ということになる。 あとは、を全探索して、そのときのが何通りあるか数えていく。なので、が最小の2の場合を考えても、はぐらいまででよさそう。についても同様。