AtCoder Regular Contest 048
- 2. A問題 階段の下
- 3. 問題概要 ? A階からB階まで、何回階段を上る必要がある か? ? ただし、x>0に対し、-x階は地下x階を表す ? ?109 ≤ ? < ? ≤ 109
- 6. 場合分け② ? AとBの符号が異なる場合 ? 「地下1階と1階の間」の階段を使うので、①に 比べて使う階段の数が一つ減る ? B-A-1が答え ? 以上でこの問題が解けた
- 8. 問題概要 ? N人の人がいて、レーティングとじゃんけんで 出す手が決まっている ? AtCoderじゃんけんでは、二人のレーティング が異なる場合高いほうが勝ち、そうでない場 合はじゃんけんの結果で勝敗を決める ? 各人について、ほかのN-1人とAtCoderじゃん けんをした時の対戦成績が何勝何敗何引き 分けか求めよ ? N<=100000, レーティング<=100000
- 9. 解法 ? 各レーティングと手ごとに、人のIDを要素とし た配列を持っておく ? 変数Kを「今見ているレーティングより低い レーティングの人の人数」として使うことにす る ? レーティングが低いほうから見ていく ? 最初はK=0
- 11. C問題 足の長い高橋君
- 12. 問題概要 ? N個の0,1からなる文字列の組であって、以下 の条件を満たすものの個数をmod 10億7で答 えよ(N<=100000) ? 条件: – ?番目の文字列の長さは??(?? ≤ 109) – 任意の? ≠ ?に対し、 ?番目の文字列の後に?番目 の文字列をひっくり返したものをつなげたものが 回文となる
- 13. 考察 ? 一番短い文字列の長さをDとおくと、すべての 文字列の先頭D文字は等しい – 一番短い文字列の後ろにほかの文字列をひっく り返したものをつなげたものが回文となるため – 逆に、各文字列の先頭D文字に関してはこれ以 上の制約がつくことはない
- 16. 考察 ? 2つの異なる文字列に対し、1つめの文字列 の先頭D文字を取り除いたものの後ろに2つ めの文字列の先頭D文字を取り除いたものを ひっくり返したものをつなげたものは回文 ? 赤字の2つは前の考察により回文だとわかっ ている ? 「回文と回文をつなげて回文をつくっている」 という主張
- 26. 証明 ? 赤、黄、緑すべての部分が回文 ? これは最初と同じ状況 ? 黄色い部分の長さは、AとBをつなげた文字列 の長さをAの長さで割った余り ? (黄色の長さ, 赤の長さ)の組は(A+B,B)から Euclidの互除法の1ステップで得られるものと 同じ
- 27. 証明 ? 黄色の長さが0でない限りこの操作は続けら れる ? この終了条件もEuclidの互除法と同じ ? 結局、この操作でEuclidの互除法と同じことが でき、Euclidの互除法はGCDを正しく求めるの で、結局AもBも周期gcd(X,Y)を持ち、その1周 期は回文であることが分かった
- 30. 解法 ? つまり、 ?? ? ?たちのGCDをgとおくと、各文字 列は、先頭D文字が等しく、かつそのあとは周 期gの同じ回文が並ぶ文字列となる ? このような文字列の総数は2 ?+ ? 2 通りである ので、O(N+log (??たちのmax))でこの問題が 解けた
- 32. 問題概要 ? N頂点の重みなし無向木があり、いくつかの 頂点にはたこ焼き屋がある ? 次のクエリをQ個処理せよ ? クエリ: 「始点と終点が与えられるので、たこ 焼き屋による前は速度1/2で進みたこ焼き屋 に寄ったあとは速度1で進む人が始点から終 点まで行く最小の時間を求めよ」 ? N,Q<=100000
- 33. 考察 ? 最適な移動経路は次の2つのうちのいずれか ? ①: たこ焼き屋を経由せずに始点から終点ま で最短経路で向かう ? ②: 始点からあるたこ焼き屋まで最短経路で 向かった後、そのたこ焼き屋から終点まで最 短経路で向かう
- 34. 考察 ? 最適な移動経路は次の2つのうちのいずれか ? ①: たこ焼き屋を経由せずに始点から終点ま で最短経路で向かう ? ②: 始点からあるたこ焼き屋まで最短経路で 向かった後、そのたこ焼き屋から終点まで最 短経路で向かう
- 35. 考察 ? ①: たこ焼き屋を経由せずに始点から終点ま で最短経路で向かう ? このケースは、単に始点と終点のLCAを求め て深さを見ればいい
- 36. 考察 ? 最適な移動経路は次の2つのうちのいずれか ? ①: たこ焼き屋を経由せずに始点から終点ま で最短経路で向かう ? ②: 始点からあるたこ焼き屋まで最短経路で 向かった後、そのたこ焼き屋から終点まで最 短経路で向かう
- 37. 考察 ? ②: 始点からあるたこ焼き屋まで最短経路で 向かった後、そのたこ焼き屋から終点まで最 短経路で向かう ? それは以下のような経路(緑がたこ焼き屋、青 い辺は速度1/2で進むパス、赤い辺は速度1 で進むパスを表す)
- 38. 考察 ? 与えられるグラフは木なので、黄色の点は始 点と終点を結ぶ最短経路上にあり、この経路 を通る時間は ? d(始点,終点)+d(始点,黄色)+d(黄色,緑)*3 – ただし诲(础,叠)で础-叠间の最短路长を表す
- 39. 考察 ? つまり、この問題は、始点と終点間のパス上 の頂点を黄色の頂点、たこ焼き屋のある頂点 を緑の頂点としてうまく選び、 ? d(始点,終点)+d(始点,黄色)+d(黄色,緑)*3 ? を最小化するクエリにこたえる问题
- 41. 考察 ? 各頂点vから一番近いたこ焼き屋のある頂点 までの距離の3倍をX(v)とおくと、 ? d(始点,終点)+d(始点,黄色)+X(黄色) ? の最小値を求めればよい ? つまり、d(始点,黄色)+X(黄色)を最小化すれ ばよい
- 42. 解法 ? まず、適当な頂点を根とする根つき木にして おく ? depth(v)で頂点vの根からの深さを表すことに する ? 始点と终点の尝颁础を尝とおく
- 43. 場合分け ? 黄色い頂点をLより始点側にとる場合 ? d(始点,黄色)+X(黄色)=depth(始点)-depth(黄 色)+X(黄色) ? よって、始点からLまでのパス上の ? X(黄色) -depth(黄色) ? の最小値を求めればよい
- 44. 場合分け ? 黄色い頂点をLより終点側にとる場合 ? d(始点,黄色)+X(黄色)=depth(始点)+depth(黄 色)-2*depth(L)+X(黄色) ? よって、Lから終点までのパス上の ? X(黄色) +depth(黄色) ? の最小値を求めればよい
- 45. 解法 ? どちらの場合も、X(黄色) ±depth(黄色)をあ らかじめ計算しておけば、この最小値はダブ リングを用いて求めることができる ? 前処理はLCAの初期化でO(Nlog N) ? 各クエリに対してはダブリングのO(log N) ? で計算できるので、O((N+Q)log N)でこの問題 が解けた