2となります(自分はようやくこのあたりで手がかりを見つけたような感じがしました)。(x+1)(x**2+1)/2と答えを具体的に書けました。今回の場合、さらに嬉しいのが、LCMが四則演算で書けているので剰余を取る操作とも相性が良いです。2つの方法を3つに応用できないか?2つの場合でうまく行きそうなので、3つ以上の場合に話を拡張できないかと考えます。c)なので、再帰的に2つの場合の議論が適用できそうです。x**4+1)となります。ここで、[2]はxの偶奇によってあったりなかったりすることを意味します。わからない形になりますが、試しに、x**4+1を(x**3+x**2+x+1)で割り算して、同じように最小公倍数を求められないかを考えてみます。すると(x**3+x**2+x+1)(x-1)+2と先ほどと同じように余りが2になることがわかります。今は割り算をしましたが、(x**3+x**2+x+1)の方を見ても、x**k-1という形の式の因数分解でx**4-1=(x**3+x**2+x+1)(x-1)というのがあるので、そちらからもこの計算はできます。結局3個の場合、最小公倍数はxが奇数の場合:(x+1)(x**2+1)(x**4+1)/2/2xが偶数の場合:(x+1)(x**2+1)(x**4+1)とわかりました。具体的な値で確かめてみるちょっと自信がないので、具体的に数字を当てはめて計算してみます。今回は小さな値でも計算途中の値が大きくなってしまいそうなので、小さめの数にしておきます(コーナーケースにぶつかってしまう危険性はありますが...)。3281)/2=10*82*6562/2/2となりよさそうな感じがします。3で予想を立てたほうが結論に早く到達できたかもしれないです。一般の場合でも同じことは適用できるか?さて、3つでもできました。嬉しいのは3つの場合を2つの場合と類似した方法で解けた事で、この方法を再帰的に繰り返すことで、一般の個数の場合に問題を解けそうです。細かい計算は省略しますが、これは一般の場合でも正しいことがわかって、xが奇数の場合:(x+1)(x**2+1)・・・(x**(2**(r-l+1))+1)/2**(r-l)xが偶数の場合:(x+1)(x**2+1)・・・(x**(2**(r-l+1))+1)となります。分子が複雑な形をしていますが、これは「LCMを計算すべき数をすべて掛け算する」ということを無理やり数式で表現しようとしているだけです。(x+1)(x**2+1)(x**4+1)・・・の計算を簡単化する答えが明示的に式で与えられたのは嬉しいのですが、まだ駄目です。lが10**18以下なので、この値をfor文などを用いてこのままの形で計算することは出来ません。何らかの方法で計算を省略しないとなりません。pを用いて、「実はこれらの値はかなり重複をしている」とか、「実は値がループしている」とかのからくりが働いて計算が簡単になるとかが起こらないかということです。一つのアプローチは同じように値が3つの場合などで試してみてわかりました。x**8-1/x-1となります。この値は等比級数の和の公式で書けます。rなどが大きくても時間をかけずに計算できるので、計算できそうです。最後に残ったのが、x=k**(2**l)の偶奇の判定と、xの値の計算です。前者は単純で、kの偶奇がそのままxの偶奇になります。pした値を計算します。これは前述したフェルマーの小定理を用いて計算をできます。(p-1))を計算すればよさそうです。擬似コードにするとこんな感じです。answerになりました。間違いケースを見てみると、k=pというケースでした。p)の形で用いていて、この形のフェルマーの小定理はkとpが互いにその場合しか成立していません。この部分を修正したのが前述の提出コードが得られました。コーナーケース実際にコードを書いてみると(そして提出して何回もWAをもらうと)この議論には様々なコーナーケースがあることに気付かされます。次のようなものがありました。等比級数の和の公式はる公比が1の場合分けを行う。(p-1))は等しくない。グラフが与えられている。クエリとして、スタート地点とゴール地点のペアが与えられる。各クエリに対して、「もしその枝がグラフから除かれたら、スタートからゴールまで辿り着けなくなる」という枝の本数を答えよ。第一歩すぐに思いつくこととして次の二つがあります。ワーシャルフロイドを行い、スタートからゴールまでたどり着けるかを検査するという方法では計算量的に間に合わないと言うこと。一般に、各クエリごとにグラフに対して思い処理を行うような解法は取れないということです。最初にグラフに対して前処理を行った後に、クエリに対して短時間で答えられるような処理でないといけません。ひとつは「その枝を除いてしまったらグラフが非連結になってしまうような枝」を探せば良さそうという事(後で見てみると、このような枝のことを「ブリッジ」と呼ぶ事が多いらしいです)。これがわかるならば、ブリッジとなる枝が、それぞれのクエリで何回数えられるかに問題が帰着できます。これは一つ目に思いついたことと相性がよさそうです。ブリッジを見つければ良さそうブリッジを見つけるアルゴリズムは探せば出てきそうなので、ここでは、本当にそれで解けそうかを考えていきます。一度このようなブリッジがわかれば、ブリッジ達を除いたグラフをいくつかの連結成分に分割できます。すると嬉しいのは、スタート地点(またはゴール地点)を同じ連結成分に属している節に移動させても、クエリに対する答えは変わらないということです。従って、それぞれの節はどの連結成分に属しているかさえ知っていれば十分問題に答えられそう情報が得られるということです。ブリッジを探すアプローチが良さそうです。連結成分を節だと思って新しいグラフを作成すると、グラフは木になってしまいます。これは仮に島をひとつにまとめ上げる操作が可能ならば、グラフははじめは木だと思って解いても構わないということです。残課題ここまでで残っている課題は次のようになります。ブリッジをどのように見つけるか連結成分を一つの節と思って新しいグラフを作ることはできるか?ブリッジがそれぞれのクエリで何回呼ばれるか?この問題のグラフが木であると仮定した時にどのように解くか?この中で、2番目の課題は比較的簡単で、連結成分の個数を求める深さ優先探索をブリッジを用いずに行えば良いです。残りを解くことを考えます。1つ目の課題を解く1番目の問題は自分ではわからなかったのでRADさんの解法を参考に書きました。リンク先のdfsという関数がこのブリッジを見つける操作に対応します。基本的には深さ優先探索です。ある点vにつながっている枝eがブリッジかどうかを次のように判定しています。eの方向に探索していって、すでに探索済みのノードにぶつかるかを判定する。探索済みのノードuにぶつかっていたとしたら、u→vという方向では既に探索している上で、さらにeを用いずにv→uに移動できることを意味します。これはv→u→・・・→(e)→vというループができており、すなわちeがブリッジでないことを意味します。前述のRADさんの解法では、探索した順番に節にidを振っていき、fup[v]でvに隣接しているノードのなかでidが最も小さい節のidを格納しています。その上で、vに隣接する節をすべて探索し終わった後で、vのidとfup[v]を比較して、すでに探索済みのノードに接触したかを判定しています。4番目の問題ですが、少し考えてみると問題で与えられたグラフが木だと、スタートからゴールまでどの枝を取り除いても、ゴールに到達できなくなります。この場合(クエリに対する答え)=(スタートからゴールまでの経路の長さ)です。グラフを木に限定したことで確かに問題が簡単になっているので、このグラフを木の場合に帰着させる方針は正しそうです。kの変数制限下で行えるかということです。クエリの数が節の数と同じくらいあるので、実質的に全節から全節への最短距離を求めなければならないことになりません。全節から全節への最短経路の計算というと自分の頭にはワーシャルフロイドしかなかったのですが、これではn**3かかるので間に合いません。Ancestor)を用いるのが一般的なようです。確かに、根から各頂点までの深さを求めれば、木の場合、経路長は(スタートの深さ)+(ゴールの深さ)-(LCAの深さ)*2となります。Query)を用いて高速に解く事ができます。その詳細はTopCoderのチュートリアルなどにありますのでそちらを参照して下さい。第一歩のところで書いていたブリッジごとに値をカウントするというアプローチ(下の擬似コード参照)を取っていないことに気が付きます。|カウンター387116。