Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-15SRM300台を練習していく part9

SRM 322 GroupWork

|  SRM 322 GroupWork - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 322 GroupWork - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6804

スキルが低い人は他の出来る人の足を引っ張ってしまう。あるあるな話。

解法はグループ内でのスキルの最小値を固定して、それぞれについて何人参加できるか調べるだけ。

続きを読む

SRM 322 ExtendedDominoes

|  SRM 322 ExtendedDominoes - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 322 ExtendedDominoes - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6779

閉路を全部検出して、閉路のつながり方を全部調べようとして分けわかんなくなった。

editorialを見て解法を理解。自力では解けなかった。

続きを読む

SRM 325 FenceRepairing

|  SRM 325 FenceRepairing - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 325 FenceRepairing - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6827

DPするだけ。div1easyとだけあって簡単。

300だが恐るるに足らず。

続きを読む

SRM 324 PalindromeDecoding

|  SRM 324 PalindromeDecoding - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 324 PalindromeDecoding - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6767

問題文の通りに素直に実装するだけ。200でもいいんじゃないかと思った

続きを読む

SRM 324 TournamentPlan

|  SRM 324 TournamentPlan - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 324 TournamentPlan - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6807

プレイヤーが2回以上移動するのは損なので、全てのプレイヤーが一堂に会する形にしたい。

はじめは最小全域木作るだけかなと思ったけど、それだとサンプルが通らない。

各プレイヤーの初期位置のXとYにそれぞれついて、

地点の候補として各プレイヤーからの距離を計算し、和を返すだけだった。

続きを読む

SRM 323 RoadsAndFools

|  SRM 323 RoadsAndFools - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 323 RoadsAndFools - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6674

散々悩んだ挙句、普通にDPして何通りあるか数えることにした。

2通り以上か0通りだったら終わり。

1通りの場合、ある箇所が逆順になっていたら、どちらかを全長から引いて、を繰り返してsequenceを求める。

続きを読む

SRM 321 WeirdSort

|  SRM 321 WeirdSort - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 321 WeirdSort - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6755

てきとーに書いたら通ってしまった。

辞書順最小だからdfsでよくね

⇒ {1, 1, 1, 1, …, 1, 2} なパターンだとTLEする

⇒ じゃあ同じ数字をまとめちゃおう(上の例だと、{1, 2} ⇒ {2, 1} ⇒ {2, 1, 1, ... , 1} とする)

⇒ {1, 1, 2, 2, 4, 4} みたいなパターンでWAする(正解は {1, 1, 4, 2, 2, 4} で、4が分離する形になる)

⇒ それじゃ同じ数字を1個とn-1個に分けてまとめよう

⇒ 通った

続きを読む

2011-08-06SRM300台を練習していく part8

SRM 321 Chocolate

|  SRM 321 Chocolate - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 321 Chocolate - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6598

長方形でない形には分割できないので、 x * y = nTiles となる形に分割できるかどうか考える。分割は高々2回。

x か y のどちらかが width もしくは height と等しければ分割は1回で済む。

続きを読む

SRM 319 ConstructBST

|  SRM 319 ConstructBST - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 319 ConstructBST - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6714

二分探索木を作って、各ノードの左の子と右の子の数をカウント。

再帰的に重複組み合わせを計算していく。

続きを読む

SRM 320 ExtraordinarilyLarge

|  SRM 320 ExtraordinarilyLarge - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 320 ExtraordinarilyLarge - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6398

x, yの末尾についている階乗(!)の数をカウントし、同数だけ取り除く。(x! = y! なら x = y だから)

そして 0! = 1に注意してシミュレーション。

続きを読む

SRM 319 BusSeating

|  SRM 319 BusSeating - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 319 BusSeating - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6715

各空席の位置を座標に変換して、組み合わせを全探索。

続きを読む

SRM 320 ContestSchedule

|  SRM 320 ContestSchedule - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 320 ContestSchedule - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6708

コンテストを終わりの早い順に並び替え、DPするだけ

続きを読む

2011-08-05SRM300台を練習していく part7

SRM 310 FloatingMedian

|  SRM 310 FloatingMedian - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 310 FloatingMedian - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6551

ソート済みのlistに対してはCollections.binarySearchが使えるので、

インデックスをずらす際に取り除く値の位置と、新しくリストに挿入する値の位置を二分探索で探してあげる。

続きを読む

SRM 316 PlacingPieces

|  SRM 316 PlacingPieces - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 316 PlacingPieces - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6540

難しい。解いたのはだいぶ前だけど今やれって言われたら多分出来ない

続きを読む