こんばんは、しほみんです。
昨日また、競技プログラミングをしてきました。今回も考え方をまとめていきたいと思います。今回から自分のステータスを追加します。
＜自分のプログラミング力＞
・レートは600前後の茶色です。
＜Atcoderでのスタンス＞
・基本的に時間がないのでぶっつけ本番でやっている。そのため、回数の割にレートが低い気がする。現在約20回参加、5か月。
・目標はD問題までをちゃんと解けるようにすること。さらに短時間であればなおよい。レートは緑を安定的にとる。
今回はABC145に挑みました。
今回は、ABCの3問をこたえることができました。しかし、時間は45分かかってしまい、パフォーマンスは700前後でした。やはり20分程度で解答してパフォーマンスを挙げないとだめですね。
レートも565→580と若干上がりました。
今回はD問題を単純に理解できてなかったのでその部分きちんと理解したところでやっていきたいてす。
以下、ネタバレです。
A問題
半径rの円の面積は、半径1の円の何倍かをこたえる問題です。
半径rの円の面積はr*r*πです。一方、半径1の円はπです。
よってr*r*π/π = r*rが答えです。
B問題
ある文字列Sが現れた場合、S = T+Tと分解できるかどうか判定する問題です。
まず、文字列の数が奇数の場合成立しないのでNoです。
文字列の数が偶数の場合、文字数をnとしたら、
1つ目のTは1文字目から、2つ目のTはn/2+1文字目です。
よって、i文字目とn/2+i文字目を比較してすべて同じならYesとすればよいです。
C問題
全経路の平均値を求める問題です。
すべての町の位置が与えられています。町がN個とすると、それぞれすべての町を行く通り方はN!通りです。それぞれの通る距離を求めてその平均を出します。
今回、Nが2以上8以下とN!通りの経路をすべて愚直に計算しても出すことができます。
(この方法も今後必要なので勉強が必要なのですが....)
ただ、自分の場合、すべての通りを網羅する方法がうまく考えられなかったので、それぞれの経路が何回重複するか考えることにしました。
Nつの町がある場合、2つの町の距離はS = N*(N-1)/2通りです。
また、全部の経路を通る場合、それぞれのT = N! ×(N-1)の数だけ、2つの町の間を通ります。すべての通り方は等価のため、同じだけ通ります。よって、T/Sがそれぞれの経路の通る回数です。
よって、2つの町の距離の総和をWとすると。
W*T/S/N!となります。これを計算するとW*2/Nとなります。
よって、二重forループで町iと町jの距離を(i,j)にいれる行列で、三角行列を求めて、
その和を2/Nで割るだけです。
D問題
これは単純にnCr(mod p)を求める問題に置き換えられます。（最初動的計画法で遣ろうとしてましたが普通にメモリが足りなかったです...冷静にこっちがいいです...）
ナイトの駒の動かし方から連想される問題です。ナイトは(2,1)か(1,2)の動きをします。
(0,0)をスタートとした場合、(X,Y)に到達する方法を求める問題です。
まず、X+Yが3の倍数でなければ、ナイトは到達しません。その場合を省きます。
次に(2,1)の動きをm回、(1,2)の動きをn回とすると
X=2m+n, Y = m+2nです。
よって、m = (2X - Y)/3, n = (2Y - X)/3です。
m< 0またはn<0であれば到達しないので0です。
m=0かn=0であれば1通りしかないので1です。
あとはm>0,n>0であれば、n+mCnとなります。
これを求めればよいのですがmod pをする場合、Cは割り算をするので計算が狂います。
そのため、ここに工夫が必要です。
ここで逆元の考え方を用いります。
逆元とは...
a÷bをしてもmod pで成立させるように取り入れた概念。
a÷b =a×(1/b)と考えるとaに1/bかけられれば、法は成立する。
よって、1/bはaの逆元という。
このときaにbをかけたときmod p条件で1になること。
つまり、a*b ≡ 1(mod p)を満たすものであることが分かります。
このb求めるアルゴリズムは決まっていて検索すると出てきます。
この逆元さえ求められれればあとは単純です。
1.まずはm+nCnの分子を求める。modで常に余りを計算するようにする。
2. m+nCnの分母で1で出た解を割っていく。答えに逆元をかけてmod計算すれば破綻しないのでそのように計算する。
このとき、ans = ans * modinv(ansの逆元）% modで計算。
3. 答え出力。
ではこのbを求めるのに何を使うかをもう少し突き詰めたいと思いますが大雑把な理解なのでよくわからない場合はより詳しく調べた方がいいです。（アルゴリズムだけわかればよいのであればここから下は不要です。）
このbを求めるのに少し変形します。
つまりa*b - 1はpで常に割り切れます。つまり、a*b - 1 = pyとなり、
yを-yとするとa*b +p*y = 1で、これを満たすyがあればよいことになります。
この形を求めるにはユークリッドの互除法を拡張すればよいことになります。
この方法だとax+by=dでa,bが与えられた場合、(x,y)の組みが求められます。
aをbで割ると、a =qb+rとなります。
すると(qb+r)x+by = d ⇔b(qx+y)+ rx = dとなり、次は(b,r)で適応できます。
これを繰り返すと...最後は(d,0)の形になります。
つまり、dx+0y = dで(x,y) = (1,0)となります。
よって、(x,y)を逆にさかのぼれば、おのずと、先の条件を満たす(x,y)は出ます。
今回はaとpは互いに素なので、d = 1です。よって、あらかじめ、(b,y)の答えを(1,0)として、(a,p)の商を使って、逆算を行うことで同時に答えが出ます。
まあ正直D問題のアルゴリズムはよく思いつくなあと思いながら活用しようかなって感じです。自分もまだ完全には理解してないですがイメージはこんな感じです。
ちょいちょい精進を続けていきたいなと思います。
ではでは。
