読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ2326 Number Sorting

AOJ

解法

制約を見ると,B-A \le 10^5 という怪しい制約があるので,D=B-Aとします.
まずこの時点で想定解法はO(D)O(D log D)とかその辺を疑います.(桁DPの可能性もありますがこの制約である必要があまりなさそうなので切り捨てました.)

小さい数字から追加して条件を満たす集合を作っていくことを考えると,新たに追加する数字は集合に入っているどの数字よりも辞書順で大きい数字になります.
この形は配るDPっぽい形なのですが実装がしづらいので,漸化式を立てて貰うDPにします.
集合のうち最も大きい数字がvである組み合わせをF(v)とし, \left[ A,B \right] のうちvが辞書順で何番目であるかをS(v)と表すと,

F(v)=1+\sum_{u < v \& \& S(u) < S(v) }F(u)
という漸化式が立てられます.
愚直にやるとO(D^2)ですが,辞書順にFの値を決定していくことを考え,未決定の値は0であるとしたとき,
F(v)=\sum_{i = A}^{v - 1} F(i)
というように連続した区間の値の合計値をとればいいことになります.
あとはBITで殴ればいいので,計算量はO(DlogBlogD)になるとおもいます.
辞書順のソートのところで,SA_ISを使って殴るとO(D(logN+logD)まで落ちそうな気がしますが,そこまでする必要はないと思います.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1942114#1
ソースコードではG( S(v))=F(v)となるGを値の昇順に求めています.
やってることはほぼ同じです.

AOJ1302 Twenty Questions

AOJ

SRM694Div1Med「Distinguishable」に似ていたので誤読をした(というより同じ問題だと思ってしまった.)

問題文

Twenty Questions | Aizu Online Judge
例によって日本語訳はないです.

解法

どんなオブジェクトも与えられた質問によって一つに特定できることが保証されているので,特定できるかどうかを心配する必要はないです.
というわけで,全探索をして解を探します.
適当に全探索をすると,O(n!2^n)みたいな感じでTLEになってしまいます.
冷静になると,今まで使った質問の順序は関係ないので,質問の結果が(まだ質問してない,yes,no)の3通りと考えると状態数が3^nになります.
なので,メモ化をすることでO(3^n)で解けます.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1939651#1
コードでは質問の結果ではなく残ってる物体の候補の集合をbitに起こして管理しています.

それと,emacsで書いててインデントが崩れてた問題が解決した気がします.

AOJ1330 Never Wait for Weights

AOJ

問題文

Never Wait for Weights | Aizu Online Judge
日本語訳は他の方のブログ見てください

解法

!を頂点の連結クエリ,?を連結成分内のrankの差を取得するクエリとしてみてみましょう.
Union-Findしたい気持ちになってくると思います.
Union-Findについて,自分の親を連結成分内の最もWeightの大きい頂点とすると,重みの差の一意性っぽいものができそうです.
頂点の順位が独自に決めていいわけではなく与えられるため,蟻本のような実装だとうまくいかないです.
ところが,rankによる処理を行わなくてもfind時の親の付け替えを行うだけで全体のならし計算量がO(logN)になります.
これを利用するとO(QlogN)で解けます.

実装上の工夫としては,親からの距離をrank(v)に保持しておき,find時にセグ木の遅延評価のような処理を施すと更新が楽になると思います.

    int find(int x){
	if(par[x]==x)return x;
	else{
	    int p=find(par[x]);
	    rank[x]+=rank[par[x]];
	    return par[x]=p;
	}
    }

AOJ2333 僕の友達は小さい

AOJ

問題文がなかなかキチってて好き

解法

ナップサックで解けそうな気がしてくるので,DPで考えてみます.
すると,W-(選んだ友人の高さの合計)が選んでない人の高さの最小値未満なら条件を満たすことが分かると思います.

そのため,dp(選んだ友人の高さの合計,今まで選んでない人の高さの最小値)=(組み合わせ)というDPを更新すればよさそうです・
選んでない人の高さの最小値はあらかじめ友人を高さでソートしておくと楽になると思います.
また,選んでない人の高さは値ではなくindexで持っておかないとTLEしてしまうので注意が必要です.

計算量はO(N^2W)

AOJ2222 Alien's Counting

AOJ

最近出次数1のグラフ問題やりすぎて慣れてしまった

解法

出次数が高々1という制約があるので
TopCoderのSunny Graphと同じように考えると,一つの連結成分は1つの単純閉路といくつかのパスを繋げたような形になります.
閉路について考えると,閉路に含まれる指を曲げると閉路全体を曲げる必要が出てきます.
閉路を一つの頂点としてみることができるので,強連結成分分解をしたい気持ちになります.
で,このグラフを強連結成分分解(というか閉路を一つの頂点としてまとめるだけ)をしてやると,有向辺はその頂点の親ノードを指しているとみることができます.
つまり,辺の向きを逆にしてやればそのまま根付き木になります.
与えられたグラフは森になるので,各根付き木に対して木DPっぽく数え挙げてやって最後に掛け算をすれば答えが出ます.

AOJ2200 Mr. Rito Post Office

AOJ

ICPC国内予選の過去問ですね
実は去年解いた記憶があります(まあ去年は青コーダーでしたし激遅だったのでいい復習になりました
10分で解きたい問題

解法

あらかじめ,陸路のみ,海路のみの全頂点間最短路についてワーシャルフロイドを使って求めておきます.
どう見ても制約がDPっぽいので,DPでどういう状態を持たせていくかに考えていくと,
(i番目の目的地,船が放置されている位置)の情報を持って,その状態の最短距離を保存しておけばよさそうです.
で,状態の遷移なのですが,

  • 船を放置したまま陸路で次の目的地へ向かう
  • 船まで最短路で移動し,ある地点で船を放置し(海路の最短距離を使う),そこから次の目的地へ陸路を使って移動する

の2パターンだけなので最初に求めた全頂点間最短距離の情報を使えばO(1)で取り出せます

計算量はO(N^3+RN^2)

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1928897#1

TCのレートが黄色で安定するようになってきました

AOJ2306 Rabbit Party

AOJ

解法

全然関係ない話をすると,グループに含まれる頂点集合からなる完全グラフのMSTのスコアがそのままそのグループのスコアになる(本当に関係ない)

グループが既にあったとして,そのグループに一人追加することを考える.このとき,元のグループのある人と新しく追加する人の間に関係がなかった場合,新しく追加する人のスコアは0になるし,他の人のスコアが増えることはない.
つまり,最適な頂点集合は与えられた辺で完全グラフを構築できる必要がある.
辺の数は100以下なので,選ぶことのできるグループはかなり限られる.
というわけで適当に完全グラフを保ちつつ一人ずつ追加していく全探索を適当にしてやれば通ります.

ソースコード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1926065#1
計算量なんてなかった.間に合う自信はあったけど計算量の見積もりがしづらい