Hatena::Grouptopcoder

capythm@TopCoder このページをアンテナに追加 RSSフィード

2015-01-17AOJ-ICPC: Misterious Gems (100pt)

AOJ-ICPC: Misterious Gems (100pt)

14:34 | AOJ-ICPC: Misterious Gems (100pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - AOJ-ICPC: Misterious Gems (100pt) - capythm@TopCoder AOJ-ICPC: Misterious Gems (100pt) - capythm@TopCoder のブックマークコメント

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2000

解法

シミュレーション。

方角+距離で移動していく系の問題はdx,dy(=-1,0,1のどれか)を方角によって決めて、

それを距離分回す、という一般的なテクニック(?)を使うと便利だ。

ソースコード

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

2015-01-16AOJ-ICPC: 次期町長 (100pt)

AOJ-ICPC: 次期町長 (100pt)

00:44 | AOJ-ICPC: 次期町長 (100pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - AOJ-ICPC: 次期町長 (100pt) - capythm@TopCoder AOJ-ICPC: 次期町長 (100pt) - capythm@TopCoder のブックマークコメント

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1159

町長を決めるためにn人(n≧3)でゲームをする。

最初、ボウルにr個の石が入っている。以下のステップで進める。

・ボウルに石が入っている場合、ボウルを持っている人はボウルから1つ石を取り出し手持ちにする。

・そうでない場合、手持ちの石をすべてボウルに入れる

・次の人にボウルを回す

以下を繰り返し、一人の人が石を総取りすればゲーム終了である。

総取りする人の番号を出力せよ。

ただし、与えられる入力値の場合、ゲームは100万ステップ以内に保証される。

解法

100万ステップ以内に終わるのだからシミュレーションすればいい。

英語の読解ができれば解けますね。

たぶん解析的にも解けるような気がしますが・・・よくわかりません。

ソースコード

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

2015-01-15AOJ-ICPC: Hanafuda Shuffle (100pt)

AOJ-ICPC: Hanafuda Shuffle (100pt)

23:02 | AOJ-ICPC: Hanafuda Shuffle (100pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - AOJ-ICPC: Hanafuda Shuffle (100pt) - capythm@TopCoder AOJ-ICPC: Hanafuda Shuffle (100pt) - capythm@TopCoder のブックマークコメント

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1129

n枚のカードがある。花札シャッフルをr回行った後の一番上のカードの番号を求めよ。

解法

シミュレーションする。

遅そうだけど、最大50枚のシャッフル回数50回なので十分間に合う。

配列2つ用意しておくのが効率いい実装。

ソースコード

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

2015-01-14AOJ-ICPC: ICPC 得点集計ソフトウェア (100pt)

精進のため、1日1問AOJ-ICPCを解いてブログを書くようにします。

AOJ-ICPC: ICPC 得点集計ソフトウェア (100pt)

23:04 | AOJ-ICPC: ICPC 得点集計ソフトウェア (100pt) - capythm@TopCoder を含むブックマーク はてなブックマーク - AOJ-ICPC: ICPC 得点集計ソフトウェア (100pt) - capythm@TopCoder AOJ-ICPC: ICPC 得点集計ソフトウェア (100pt) - capythm@TopCoder のブックマークコメント

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1147

n個の点数が与えられる。その最小値と最大値を除いた点数の平均値を出力せよ

解法

最小値と最大値と合計値を計算すると、(合計値-最小値-最大値) / (n-2)が答え。

ソースコード

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

2015-01-12Codeforces #285 (Div.1)

Codeforces #285 (Div.1)

23:46 | Codeforces #285 (Div.1) - capythm@TopCoder を含むブックマーク はてなブックマーク - Codeforces #285 (Div.1) - capythm@TopCoder Codeforces #285 (Div.1) - capythm@TopCoder のブックマークコメント

A. Misha and Forest

問題

http://codeforces.com/contest/504/problem/A

無向グラフがある。頂点がN個(0, 1, ..., n-1)ある。ループや多重辺はない。

各頂点につながっている枝の数degree[k]と、つながっている先の頂点をxorした結果s[k]が与えられる。

グラフの全ての枝(V_from, V_to)を出力せよ

解法

ループがないので、葉があることが保証される。

degree[k]=1のものから処理していく。degree[k]=1の頂点は親ノードparent[k]=s[k]であることは自明。

親ノードの情報degree[ parent[k] ],s[ parent[k] ]も更新する(自ノードを切り離す)。

これを逐次実行すれば解ける。degree[k]=1になったものをqueueに突っ込んで順番に処理すると実装が楽。

ソースコード

http://codeforces.com/contest/504/submission/9415856

B. Misha and Permutations Summation

問題

http://codeforces.com/contest/504/problem/B

n個の数字(0, 1, ..., n-1)の順列はn!パターンある。これを順番にソートして、k番目の順列をPerm(k)と定義する。

つまり、Perm(0)=(0, 1, ..., n-1), Perm(n!-1)=(n-1, n-2, ..., 0) である。

2つの順列Perm(x), Perm(y)を与える。Perm((x+y) mod n!)を出力せよ。

解法

順列Perm(x)からxを求める必要がある。これには、階乗進数への変換が便利である。

例えば、3要素の階乗だと

s

012 -> 0 = 0*2! + 0*1!

021 -> 1 = 0*2! + 1*1!

102 -> 2 = 1*2! + 0*1!

120 -> 3 = 1*2! + 1*1!

201 -> 4 = 2*2! + 0*1!

210 -> 5 = 2*2! + 1*1!

という具合だ。

つまり、順列s[0..n-1]から A[1]*1! + A[2]*2! + ... + A[n-1]*(n-1)! の A[i]を求めたい。

上の例を見ると、A[2]はs[0]の値そのものであり、

A[1]はs[1]がs[1..2]の中で何番目に大きいか、の値になっている。

よく考えると、A[2]もs[0..2]の中で何番目に大きいか、の値だ。

A[n-1]は容易に求まるが、A[n-2]以降は容易ではない。

(n<=200,000なので、ナイーブな方法O(n^2)では計算が間に合わない)

そこで、BITを使う。B[0]=B[1]=...B[n-1]=1で初期化しておき、

A[n-i-1]=sum(B[0]... B[ s[i] ]) (=BIT.get(s[i]))で求め、B[ s[i] ]=0に更新(BIT.add(s[i],-1))するとよい。

BITを使うことで計算量がO(n log n)に減るので間に合う。

xからPerm(x)を生成する処理も必要だが、上記の逆をすればいい(多分)ので省略します。

具体的な実装は他の人のソースを見てください(´・ω・`)