http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=RitsCamp17Day1
本物の解説はこっちです。
Day1の解説スライドです https://t.co/wa3pgp7mgS ジャッジ解はこちら https://t.co/ESSECDeZDi #rupc2017
— tubo28 (@tubo28) 2017年3月24日
以下、解説
A. Tounament（トーナメント）
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2228211&cid=RitsCamp17Day1
愚直にシミュレーションして数え上げていけばよいのだが、やり方が問題。
再起を使うと比較的簡単にできる。
int f(int L, int R) := [L,R]が全員棄権者か(1or0)
f(L,R)では
- a = f(L,L+(R-L+1)/2-1)
- b = f(L+(R-L+1)/2,R)
- a==1 && b==1 ならば試合がある（ans++）
- a==0 && b==0 ならば[L,R]は全員棄権者なのでreturn 0
f(0,N-1)をしてansが答え
B. Weight Range（重さの範囲）
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2228878&cid=RitsCamp17Day1
各色のボールの総数がすべて等しくなるのは、全部でLCM(N,M)個とったときになる。
LCM(N,M) < 10^6なので愚直にシミュレーションしても間に合う
C. Fractal Tree
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2228885&cid=RitsCamp17Day1
今回はいろいろ独立に計算できる系の問題なので、いろいろ独立にやる。
まず、最初に木T上で非決定的アルゴリズムを実行して頂点1からDFSをして頂点1から始めた時のコストの総和の期待値を求めておく(関数dfsを使って期待値expを求める)。
つぎに、木T'上で同様に計算していくが、関数dfsと同じように計算していくが、毎回、期待値expを足す。
これで答えが求まる(関数dfs2)。
D. Password（パスワード）
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2231666&cid=RitsCamp17Day1
解説にもあるが、答えは4文字以下となるので、答えを全探索する方向で計算する。
26^4=456976なので10^5くらいなので、全文に対してO(logN)くらいで存在判定すればよい。
これは、S[1] + "#" + S[2] + "#" + ... + S[N]とした文章のSuffix Arrayを構築して、二分探索で存在判定する。
E. Graduation Ceremony（卒業式）
上下の魔法と左右の魔法は互いに独立なので、別々に計算して結果を合わせる。
dp[i][j] := i番目までの文字列で魔法をj回使用したときの絶対値の最大値
絶対値だと上下どちらかが分からないので、これを計算するために
dpmax[i][j] := i番目までの文字列で魔法をj回使用したときの最大値
dpmin[i][j] := i番目までの文字列で魔法をj回使用したときの最小値
を計算して最終的に絶対値を比較すればよい。
このdpを上下と左右でそれぞれ行い、上下向けに魔法をa回、左右向けに魔法をb回使ったとして全探索すれば答えがみつかる。
dpバグりすぎてサブミット諦めた。
F. Card Game
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2231889&cid=RitsCamp17Day1
とても面白い問題。
事前計算として
C[i][j] := 数iをRで割った余りがjとなる数に変換するための最小コスト
を計算しておく(pre関数)。この計算が厄介。
数の交換を有向辺に見立ててダイクストラをするが、各数からダイクストラをやると間に合わないので、有向辺を逆に立てて、余りがjとなる数からダイクストラをする。
これで事前計算が間に合う。
あとは、各クエリについて両方の数を余りがjとするための最小コストを全通り求めて最小値を取れば答えになる。
G. Rainy Bus Stops（雨降りバス乗り換え）
ダイクストラで解く。
頂点を(バス停,時刻)、雨に濡れる時間をコストとしてダイクストラする。
頂点数が10^10くらいになりそうな感じがあるが、ダイクストラする上で関係する頂点はバスの出発到着時刻だけなので、頂点数は4*10^5くらいで収まるのでダイクストラできる。
辺を張るときに全探索していると遅いので、各頂点について出発時刻でソートした表を持っておき、それを二分探索することで高速に辺を張る。
H. Jump Party（ジャンプパーティ）
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2232355&cid=RitsCamp17Day1
大事な事実があり、これに気づかないと解けない
「一度衝突が起こったあとはずっと衝突が起こり続ける」
つまり、二分探索でいつ衝突が始まったかを検証できる。
bool chk(int t) := t回移動したときに衝突していないか
t回の移動を高速に行えばいいが、これはダブリングを使えば実現できる。
事前にダブリング配列を作成しておき(pre関数)、それを使って高速に移動させていく。
