足跡-sokuseki-

りかの日進月歩の記録

ABC011 D 大ジャンプ

D - 大ジャンプ

問題概要

スタート地点の座標は  (0, 0) で、ゴール地点の座標は  (X, Y) とする。
1回のジャンプで、それぞれ  \frac{1}{4} の確率で以下の4つのうちどれかを行う。

  •  x 軸方向に  +D だけ移動する
  •  x 軸方向に  -D だけ移動する
  •  y 軸方向に  +D だけ移動する
  •  y 軸方向に  -D だけ移動する

ちょうど  N 回のジャンプでスタート地点からゴール地点に到達できる確率を求めよ。


制約
 0 \le N \le 1000
 1 \le D \le 10^9
 - 10^9 \le X, Y \le 10^9

解法

 x 軸方向に  i 回移動するとき、 y 軸方向に  n-i 回移動することになる。
また、このとき、  x 軸の正の方向に  j 回移動すると、  x 軸の負の方向に  i-j 回移動することになるので、到達点の  x 軸座標は  D  j - D  ( i - j ) になる。
 y 軸方向にも同様に考えて、 y 軸の正の方向に  k 回移動すると、  y 軸の負の方向に  n-i-k 回移動することになるので、到達点の  y 軸座標は  D  k - D  ( n - i - k ) になる。
到達点の座標が  (X, Y) であればよい。

つまり、 x 軸方向の移動回数  i  x 軸の正の方向の移動回数  j  y 軸の正の方向の移動回数  k を全探索して、その到達点の座標が  (X, Y) ならば、その確率を答えに足しあわせればよい。

 i 回の移動のうち正の方向に  j 回移動するのは  _i C _j 通りあり、 i 回正負のどちらかに移動するのは  2^i 通りあるので、 i 回の移動のうち正の方向に  j 回移動する確率は  \frac{ _i C _j }{2^i} である。
よって、 i 回の移動のうち正の方向に  j 回移動する確率を前計算することで、  O(N^2) で求めることができる。

なお、制約の  N が大きいので、「 i 回の移動のうち正の方向に  j 回移動する場合の数」は計算できない。パスカルの三角形を計算する時の遷移で2で割ることで確率を計算できる。

ちなみに、 x 軸方向の移動回数  i を決めると、ゴールにたどり着くための x 軸の正の方向の移動回数と x 軸の負の方向の移動回数はわかるので、この問題は  O(N) で解くこともできる。

Submission #2121336 - AtCoder Beginner Contest 011

ABC037 D 経路

D - 経路

問題概要

 H  W のマス目があり、それぞれのマスには整数  a_{i j} が書かれている。
このグリッドの中の好きなマスから開始し、今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができる(移動しなくてもよい)。
ありうる移動経路の個数を  10^9 + 7 で割った余りを求めよ。


制約
 0 \le H , W \le 1000
 1 \le a_{i j} \le 10^9

解法

dp[  i ][  j ] := マス  ( i, j ) で動くのを終了する場合の移動経路の個数

として、  a_{i j} が大きい順に dp[  i ][  j ] を計算していく。
dpテーブルは全て1で初期化しておき、dpテーブルの更新は、マス  ( i, j ) の4近傍のマス  ( x, y ) に対して、

dp[  i ][  j ]  += dp[  x ][  y ];

をする。

すべてのマス  ( i, j ) に対してdp[  i ][  j ] の総和が答えとなる。


Submission #2119231 - AtCoder Beginner Contest 037

CODE FESTIVAL 2016 Grand Final B Inscribed Bicycle

B - Inscribed Bicycle

幾何。

問題概要

三角形の頂点が与えられる。
三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。

制約
 0 \le x_i, y_i \le 1000


解法

まず、三角形の内部に半径  x の円がかけるとはどういうことかを考えてみる。
円の中心と三角形の辺の距離が  x 以上であれば、半径  x の円がかける。
つまり、三角形の内部で、各辺から  x 以上離れた場所(図の緑の三角形)に円の中心があれば、その円の円周は三角形の辺上か三角形の内部にあることがわかる。
f:id:wk1080id:20180220230806p:plain


次に、三角形の内部に半径  x の円が重ならないように2つかけるとはどういうことかを考える。
それぞれの円の中心と三角形の辺の距離が  x 以上であり、2つの円の中心の距離が  2x 以上であれば、半径  x の円が重ならないように2つかける。
つまり、三角形の内部で、各辺から  x 以上離れた場所(図の緑の三角形)にそれぞれの円の中心があり、2つの円の中心間の距離が  2x 以上ならば、その2円の円周は三角形の辺上か三角形の内部にあり、かつ2円は重ならないことがわかる。
f:id:wk1080id:20180220230751p:plain


ここで、元の三角形の内接円の半径を  r とすると、元の三角形の内部で各辺から  x 以上離れた点の集合からなる三角形の内接円の半径は  r - x である。よって、2つの三角形の相似比は  r : r - x

2つの円の中心間の距離を  2x 以上にするためには、「元の三角形の内部で各辺から  x 以上離れた点からなる三角形」の少なくとも一辺が  2x 以上であればよい。つまり、与えられた三角形の3辺のうち最も長い辺の長さを  A とすると、内部の三角形の最も長い辺の長さは  A \times \frac{r - x}{r} になるので、これが  2x 以上ならば、与えられた三角形の内部に半径  x の円が重ならないように2つかける。


よって、半径の長さ  x を二分探索で決め打ちして、それぞれの  x について、三角形の内部に半径  x の円が重ならないように2つかけるかどうかを判定すればよい。

Submission #2118930 - CODE FESTIVAL 2016 Grand Final(Parallel)

ABC036 D 塗り絵

D - 塗り絵

はじめての木DPです。

問題概要

 N 頂点の木が与えられる。
両端の頂点が黒で塗られるような辺がないように、頂点を白または黒でぬるとき、塗り方の通り数を  10^9 + 7 で割ったあまりを答えよ。

制約
 1 \le N \le 10^5


解法

漸化式を立てて木の上でDPをしましょう。

 f( x ) := 頂点  x を親とする部分木に含まれる頂点をすべて白または黒で塗り、両端が黒で塗られた辺が存在しないようにする方法の通り数。
 g( x ) :=  f( x ) と同じ。ただし、頂点  x は必ず白で塗らなければならない。

とすると、以下の2つの漸化式を作れる(ただし、 y_1 , y_2 , … , y_k  x の子とする)。

  •  f( x ) = g( x ) + g( y_1 ) \times g( y_2 ) \times … \times g( y_k )
  •  g( x ) = f( y_1 ) \times f( y_2 ) \times … \times f( y_k)

なぜこの漸化式がつくれるのかは、次のサイトがわかりやすいです、これで理解しました。
漸化式を立てて「tree DP問題」を解く D - 塗り絵 - マツシタケイタの技術ブログ(勉強中)

あとは、木の葉から順番に  f( x )  g( x ) を埋めていくことで、  O(N) で求められる。
葉から根にむかって順番に求めるには、dfsをつかって根まで行き、帰りがけに計算すればよい。

Submission #2117216 - AtCoder Beginner Contest 036

TPC追いコン A 不完全迷路

A - 不完全迷路

問題概要

高さ  H  W の迷路が与えられる。
壁のマスを1マスのみ道のマスに変えたとき、スタートのマスからゴールのマスへの最短経路長が最長となるようにしたい。
そのときのスタートからゴールまでの最短経路長を求めよ。

制約
 1 \le H, W \le 298


TLE解法

それぞれの壁のマスに対し、そのマスを道に変えたときのスタートからゴールまでの最短経路をすべて求めて、その最大値を出力する。
計算量は  O((HW)^2) になる。

Submission #2039448 - TPC追いコン

解法

ある壁のマスを道に変えたとき、そのマスを通るスタートからゴールまでの最短経路長は、
(そのマスの上下左右どれかのマスの、スタートからの最短経路長) + (そのマスの上下左右どれかのマスの、ゴールからの最短経路長) +   2
であることがわかる。
f:id:wk1080id:20180218192951p:plain
また、変更するマスは1つのみなので、「そのマスの上下左右どれかのマスの、スタートからの最短経路長」と「そのマスの上下左右どれかのマスの、ゴールからの最短経路長」は、与えられた迷路から求めることができる。

与えられた迷路の道のマスすべてについて、スタートからとゴールからの最短経路長を前計算しておき、それぞれの壁のマスに対し、そのマスを道に変えたときのスタートからゴールまでの最短経路を求めて、最大値を出力する。
この場合、計算量は  O(HW) になる。

Submission #2107477 - TPC追いコン

立命館NAIST競プロ合宿参加記

2/10-11に立命館大学にて1泊2日の競プロ合宿を行いました。

 

1日目

昼に集合して、自己紹介からスタート。

きりんさん以外は面識があったので、NAISTの方々とはお久しぶりです〜みたいなノリだった。

 

その後、レートが水色未満の人はAOJ-ICPCのばちゃ、それ以外の人はこどふぉばちゃをしていた。

Dashboard - Codeforces Round #443 (Div. 2) - Codeforces

A問題は誤読してWAをだしつつもAC、B問題は条件が足りてなくてWAってた。C問題は読んだけどビット演算苦手だな〜と思って手をつけられず。(最悪か?

 

ばちゃ終了後は感想戦をして、あとはらてあさんとTwitterの話をしていた。

 

その後、学内の宿泊施設にチェックインして荷物を置いてから、やざてん先輩オススメの天天有というラーメン屋に行きました。おいしかった。

 

 

部屋に戻ったら9時前だったので、NAIST部屋にお邪魔してみんぷろオンサイトをした。

「みんなのプロコン 2018」 - 「みんなのプロコン 2018」 | AtCoder

 

開始早々ABの2完して、Cをずっと考えてたけど嘘解法しか浮かばず。2人が最適に行動するの苦手。

コンテストが終わってから感想戦をした。みんなCに詰まってたみたい。

 

そのあとは部屋に戻って、シャワー行ったりTwitterしたりしてた。

Twitter見てたら、らてあさんが徘徊してるみたいだったから、参戦して575探索とかした。

 

2日目 

1日目と同じ部屋で同じようにばちゃした。

Dashboard - Codeforces Round #326 (Div. 2) - Codeforces

 A問題は誤読してWAをだしつつもAC、B問題は素因数分解して各素数かけたら合わないな〜ってなってた。C問題はビットっぽい気配がして読むのをやめた。(最悪か?(あれデジャヴか?

 

感想戦を少しして、コンビニに昼ごはんを買いに行き、快適な部屋を求めて部室棟へ移動。

 

昼ごはんを食べてからAPCばちゃをしました。

https://not-522.appspot.com/contest/6395698329157632

Aはなんか勘違いしてて2WAした。Bは意味不明。

ということで1完で終わった。かなしいね。頭がない。

終わってからBを通した。むずすぎか?

 

その日は19時から第2回 RCO日本橋ハーフマラソン 予選 - 第2回 RCO日本橋ハーフマラソン 予選 | AtCoderがあったので、早めに解散した。

解散の前にみんなでおはなしして、次は夏ごろに合宿できたらいいねってことになった。

 

また合宿やるぞ!!

 

 

一応立案者で準備とかしたんですが、やったのは

  • 参加希望者の予定を聞いて日程を決める
  • 学内宿泊施設を予約する
  • 活動場所を確保する

だけなのでそんな手間でもなかったです、合宿の楽しさがINFなので苦でもない

CODE FESTIVAL 2017 Final C Time Gap

C - Time Gap

問題概要

 N 人の都市について、高橋君の都市との時差が与えられる。
高橋君を含めた  N+1 人の都市のうち、すべての2つ都市の時差の最小値を  s としたときの、 s の最大値を求めよ。

制約
 1 \le N \le 50


解法

num[  i ] := 高橋君との時差が  i 時間の人数
とする。

num[  i ]  > 3 となる  i が存在するとき、高橋君との時差が  i 時間の人の中で、互いの時差が0時間となる2人が必ず存在することがわかる。よってその場合の答えは0となる。

そうでないとき、 高橋君の都市が0時であるとする。
num[  i ]  = 2 となる  i については、  i 時の都市と  24 - i 時の都市が存在することが確定する(時差を最大にしたいので2人の時差を0時間にしたくない)。

num[  i ]  = 1 となる  i については、 i 時の都市か  24 - i 時の都市かがわからないので2通りある。
よって、num[  i ]  = 1 となる  i について全探索する。
このような  i の数を  a とすると、 a は高々12であり、すべての場合に対しそれぞれの都市間の時差を調べるので、この全探索にかかる計算量は  O(a^2 \times 2^a) となる。


Submission #2099469 - CODE FESTIVAL 2017 Final (Parallel)

[追記]
解が13個しかないので、決めうちしてから2-SATで殴ることもできます。
Submission #2150954 - CODE FESTIVAL 2017 Final (Parallel)