Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-05-30SRM300台を練習していく part6

SRM 311 SumThemAll

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

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

(mediumにしては)簡単。

digitsの合計を表すテーブルを1000000まで持っておき、

lowerBoundとupperBoundを1000000で割った商と余りに分けてそれぞれ計算する。

続きを読む

SRM 311 MatrixTransforming

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

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

3x3のマスをflipする操作を繰り返す。最小何回で目的のパターンが作れるか?

左上のマスが合っていなければflipする という操作を全てのマスで試せばおk

続きを読む

SRM 312 AntarcticaPolice

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

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

各町から町へ(別の町を経由しても)到達できるかどうかはワーシャルフロイド法を使うと簡単に調べられる。

グラフを強連結成分分解して考える。詳しくはeditorial参照

http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm312

続きを読む

2011-05-28SRM300台を練習していく part5

div1のeasyとmediumを中心に練習。

easyは200点以上が目標。

mediumは解けなくてもeditorial見ながら実装する。

SRM 303 Knights

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

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

蟻本を参考に最大流のオレオレライブラリを作って解いてみた。

でもまだ最小カットと最大流が等しくなることが直感的に理解できないんだよなぁ。

続きを読む

SRM 300 JumpyNum

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

まずn桁目の数字がdであるとき、d00...00 〜 d99...99 までのJumpyNumを数える変数dp[n][d]を用意しておく。この数はDPにより求められる。更新式は以下の通り。

for (int j = 0 ; j <= 9 ; j++) {
  if (Math.abs(j - d) >= 2) {
    dp[n][d] += dp[n-1][j]
  }
}

そして、num以下のJumpyNumの数を求める関数をcount(int num)とおくと、

求める答えは count(high) - count(low-1) となる。←ここまでは自力でやった

countを求めるアプローチは以下の通り。


まず、1〜9, 10〜99, 100〜999 , ... , 10...00〜99...99 のJumpyNumの数を、10^(numの桁数 - 1) - 1 まで求める。

次に、10^(numの桁数 - 1) から (numの先頭の桁の数) * 10^(numの桁数 - 1) - 1 までのJumpyNumの数を求める。

そして最後に、numの桁を最初から固定しながら、(numの先頭の桁の数) * 10^(numの桁数 - 1) から num までのJumpyNumの数を求める。

このとき、固定された桁同士がJumpyNumの条件を満たさなくなったら、その場でループを抜ける。

これら全ての和が求める数になる。

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

続きを読む

2011-05-27SRM300台を練習していく part4

SRM 310 PyramidOfCubes

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

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

一番下のlevelに入るcubeの個数が決まれば上面と底面の面積が求まる。

あとはlevelごとに側面積を求めていく。

ちょっと苦戦。汚いコードだ( ゚д゚)、ペッ

続きを読む

SRM 306 LightSwitches

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

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

ある複数個のスイッチの組み合わせで再現できるスイッチを取り除いて、

答えは 2^(最後に残ったスイッチの数) ということはすぐ分かる。

問題はその余分なスイッチをどうやって見つけるか。

各スイッチはベクトルとみなすことができて、その各要素は各バルブにつながっているかどうか。(つながっている=1 つながっていない=0)

すると、余分なスイッチとは他のスイッチ(ベクトル)に対して一次従属であるということ。

余分なスイッチを全て取り除いた残りのスイッチ(ベクトル)は線形独立なので、

各スイッチに対応するベクトルを縦に並べた行列をAとおくと、この問題はAのランクを求めることに帰着できる。


参考:

http://ja.wikipedia.org/wiki/%E3%82%AC%E3%82%A6%E3%82%B9%E3%81%AE%E6%B6%88%E5%8E%BB%E6%B3%95

続きを読む

SRM 309 ScoreRecomposition

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

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

特にいい方法が思い浮かばなかったのでnext_permutationを使った。

質問の数は高々10だから、順列の数は10! = 3,628,800。いける!

続きを読む

2011-05-21SRM300台を練習していく part3

SRM 308 HuffmanDecoding

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

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

ハフマン符号化の逆をやる。200とだけあって簡単。

続きを読む

SRM 307 PartSorting

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

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

swap可能な範囲で大きな数を前に持ってこようと試みる。

続きを読む

SRM 308 CornersGame

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

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

意外なことに全探索(BFS)でいけた。キューを使う。

はじめは左と上へ動かす場合のみを考慮し、ゴールできないようなら右と下も解禁する。

続きを読む