SRM701 Div1 2016.10.26
いつも通り一完
問題
Easy
TopCoder Statistics - Problem Statement
解法
が小さい時はDPで簡単に求めることができる。
よく考えたり実験したりすると、DPのテーブルはループしていそう。
ループの周期を求めてもいいのだが、周期はあまり長くならなそうな気がする(たぶん高々9とか？)ので、
5040周期とかで考えていいような気がする。
実際通った。
source
どこから見れるか分からんかった
1514 -> 1596
ARC008 2016.10.25
サークルで解いた
問題
C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008 | AtCoder
解法
全員に対しての最短経路を求めておいて、遠い人から順に配っていけばよい。
自分に対してはすぐに配れることに注意する。（で1秒以内に配れる場合など）
問題
D: タコヤキオイシクナール - AtCoder Regular Contest 008 | AtCoder
解法
セグメントツリー。
とりあえずは座標圧縮しておく。
葉ノードには、,
のペアを持たせておく。（初期値は
)
それ以外のノードは、左の子が,
、右の子が
,
を持っているとすると、
とする。
根の値が全ての機械を通した時の演算結果になる。
時系列順にセグメントツリーを更新しながら、答えを求めればよい。
AOJ-ICPC 2016.10.14
アジア地区の前日（だった）。
問題
問題概要
省略
解法
DP。
それぞれの種目別に、何回アピールを行うかを分けて考える。
ある種目について、アピールを行う回数を決めておくと、各アイドルに勝てる確率を求めることができる。
これを使うと、1位から3位になる確率をDPで求められる。最下位になる確率は全員に負ける確率である。
種目で
回アピールしたときの期待値が求められたので、各種目についてアピールする回数を全探索すればよい。
問題
問題概要
省略
解法
DP。
各カードを桁別に分けて考える。
桁のカードの右に
桁並べるような場合の数 を求める。
右に置くカードが枚のとき、左に置くことができるカードは
枚である。
この時の場合の数は となる。
この場合の数が求まれば、各カードの各数字が桁目にある時の場合の数が求まるので、これを全て足せばよい。
この時、リーディングゼロとなるようなものも含まれているので、そういったものの合計を求め、引く必要がある。
これは、1桁のカードを1枚減らした後（つまり、最初に置く0のカードを取り除いておく）、上と同じことをやればよい。
AOJ-ICPC 2016.10.10
問題
Network Reliability | Aizu Online Judge
問題概要
無向グラフが与えられる。
それぞれの辺は一定確率で消える。
グラフが連結である確率を求めよ。
解法
dp。
:= 頂点集合
が連結である確率 とする。
のとき
である。
のうちある頂点を
とし、
を
を含む
の部分集合、
をその補集合とする。
と
の間の辺の数を
とすると、
となる。
問題
Strange Couple | Aizu Online Judge
問題概要
重み付き無向グラフが与えられる。辺の重みは移動にかかる時間である。
頂点から頂点
に行く。
頂点には標識がある場合とない場合がある。
標識がある場合はTへの最短路となる辺に入る。
そのような辺が複数ある場合はその1つにランダムに入る。
標識がない場合はランダムな辺に入る。
かかる時間の期待値を求めよ。
解法
ガウスの消去法。
ある頂点から別の頂点に移動する確率と、その時間を漸化式にする。
全ての頂点についてそれを求め、１次方程式を解けばよい。
問題
Wind Passages | Aizu Online Judge
問題概要
細長い通路に複数の多角柱がおいてある。
風が通路を流れるとき、単位時間当たりに流れるを求めよ。
解法
どうみても最大流問題なので、最小カットを考えればよい。
解説スライドの図を見るとイメージしやすい。
左の壁から右の壁に多角形の中を通ることを許して移動するとき、多角形の外を移動する距離の最小値が答えになる。
つまり、壁および多角形間の距離を求めて、壁から壁への最短経路を求めればよい。
問題
Shadow Witch | Aizu Online Judge
問題概要
省略。
解法
「ゴールを飛び越える」は「跳ね返る」と考える。
ゴールまですごく遠いときはかなりの手数がかかりそうなので、ある程度近く(距離100000)ぐらいまでは期待値で移動できると考えてよさそう。
あとそこから後一手でゴールできるところまではDPで求める。
後一手でゴールできるところからは、漸化式がループするためDPできないので、一次方程式を解けばよい。
AOJ-ICPC 2016.10.9
実装軽いやつ
問題
Tree Reconstruction | Aizu Online Judge
問題概要
各連結成分が強連結なグラフが与えられる。
各頂点について、入ってくる辺と出ていく辺の重みが等しくなるようにすると、
一部の辺の重みを隠しても復元することができる。
最大でいくつの辺の重みを隠せるか。
解法
ある頂点の入ってくる辺の重みが全てわかっているとすると、出ていく辺のうち1つを隠すことができる。
全ての頂点について、出ていく辺の1つを隠すと入ってくる辺の重み全てが分かる頂点がなくなるので、ある頂点だけは全ての辺をそのままにしておく。
各連結成分についてこれが言えるので、連結成分ごとにが答えとなるのでこれを全て足せば良い。
問題
Enumeration | Aizu Online Judge
問題概要
省略
問題
Do Geese See God? | Aizu Online Judge
問題概要
文字列が与えられる。
文字列は以下の条件を満たす。
1.は
の部分列である。
2.は回文である。
3.は1,2を満たす文字列のうち、最短の文字列である。
Tとして考えられ文字列のうち、辞書順で番目のものを求めよ。
AOJ-ICPC 2016.10.8
解ける問題がなくなってきた。
問題
問題概要
省略
解法
全頂点対に容量0の辺を張っておく。
最初から辺があるものについては容量1にしておき、最大流を求めておく。以下、この残余グラフ上で考える。
追加のクエリが来たら、その辺の容量を1にし、から
に1流した結果を最大流に加える。
削除のクエリが来たら、その辺が使われていなかった場合(容量が1の場合)は容量を0にする。
そうでなければ、削除する辺の
から
に流れているとする。
その辺の容量を0とし、から
に1流す。
流れた場合は別のパスが見つかったということなので、最大流は変わらない。
流れなかった場合は最大流は1減らし、から
、
から
のフローを押し戻す。
これはから
、
から
に1流せばよい。
問題
Alternate Escape | Aizu Online Judge
問題概要
省略
解法
後退解析。
盤面の座標+盤外の頂点のグラフを考える。
辺で隣接関係を表現する。辺の重みは最初に壁があれば、なければ
としておく。
勝ち頂点へ遷移できる頂点は次の2つの条件を満たす頂点である。
・勝ちマスへ辺が張られており、その辺の重みがである。
・勝ちマスへ辺が張られており、その辺の重みがである。
勝ち頂点が増えなくなるまでBFSを繰り返し、初期状態で勝ち頂点にいた場合、勝ちとなる。
コーナーケースとして、一手で盤外に出られる場合は無条件で勝ちとなる。
問題
Deadlock Detection | Aizu Online Judge
問題概要
個のプロセスと
種類のインスタンスがある。
インスタンスは
個ある。
プロセスはインスタンス
を
個要求する。
デッドロックとは、異なるプロセスが互いに必要なインスタンスを占有しているため、プロセスが途中で実行できなくなることである。
デッドロックは適切な順番でプロセスを実行することで回避できる（終了したプロセスが占有しているインスタンスは解放されるため）。
プロセスがインスタンスを要求するログが与えられるので、デッドロックが発生することが確定する時間を求めよ。
AOJ-ICPC 2016.10.7
問題を解くのをさぼると死ぬ
問題
Reverse a Road II | Aizu Online Judge
問題概要
各辺の容量がの有向グラフが与えられる。
辺を一本だけ反転させ、 間の最大流を増加させられるか。
可能な場合はそのような辺は何本あるか。
解法
まず最大流を流し、残余グラフを作る。
残余グラフで から行ける頂点集合を
、
に行ける頂点集合を
とすると、
から
への辺が条件を満たす辺である。
問題
Vector Compression | Aizu Online Judge
問題概要
ベクトルの集合が与えられるので、任意の順番でベクトルを選んでいく。
あるベクトルを選ぶとき、既に選んだベクトルの1つを使ってベクトルを圧縮できる。
ベクトルを
で圧縮すると、
となる。(
は任意の実数)
全てのベクトルを選んだとき、それぞれのベクトルの大きさの和を最小化せよ。
解法
あるベクトルで別のベクトルを圧縮した時の大きさはを三分探索すれば求まる。(いい感じの式で計算することもできそう)
各ベクトルを頂点とし、ベクトルを使ってベクトル
を圧縮したときのベクトル
の大きさを辺
の重みとするような有向完全グラフを考える。
答えはそのグラフの最小有向全域木になる。
任意の頂点を根とすることができるので、あらかじめゼロベクトルをベクトルの集合に追加しておいて、それを根とする最小有向全域木を求めるとよい。
最小有向全域木はChu-Liuのアルゴリズムで求めることができる。
