Le Algorithm: atcoder

ラベル atcoder の投稿を表示しています。すべての投稿を表示

ラベル atcoder の投稿を表示しています。すべての投稿を表示

2015年6月20日土曜日

ARC 39 C:幼稚園児高橋君

問題

http://arc039.contest.atcoder.jp/tasks/arc039_c

解法

C[座標][i]=方向iに訪問済みマスが何個連続してるか
を持たせながら移動しつつ更新した。

C[移動前][i番目のコマンドの向き]=歩いた距離
C[移動後][i番目のコマンドの逆の向き]=歩いた距離
C[移動後][向きj] = C[移動後+j][j]+1
みたいな感じで更新した。

2015年5月16日土曜日

ARC 39 B: 高橋幼稚園

問題

http://arc039.contest.atcoder.jp/tasks/arc039_b

解法

n<=kならなるべく均等に配れば良いので、n人にまずk/n個ずつ配ってその後残ったk%n個のアメをn人に配れば良いのでnC(k%n)通り

n>kならばどんなに頑張っても幸福度は0なのでどう配っても良い。この場合は
k個のアメにn-1個の「仕切り」を考えてそれの並べ方を考えれば良い。(仕切りiと仕切りi+1の間のアメの個数が子供iがもらうアメの個数となる)
ので、(k+n-1)!/k!/(n-1)! = (k+n-1)Ck 通りとなる。

ソースコード

https://gist.github.com/knewknowl/f275cbbf7cf65aa3b3ab

登録: 投稿 (Atom)