Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-27SRM300台を練習していく part2

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

ナイトの駒の関係はグラフに帰着できる。

さらに、ナイトの動き方の制約上、駒は大きく分けて二種類に分類でき、

同じ種類の駒が関係を結ぶことはない。

(こういう特別なグラフを「2部グラフ」というらしい)

問題は、グラフのノードを取り除いて、関係(リンク)の無いグラフを作るとき、

取り除く必要のある最小のノード数を求める、というもの。

そして、この問題はどうやら「2部グラフの最大マッチング問題」というものに帰着できるらしい。

確か蟻本に載っていたような気がするので、あとで調べる。

SRM 304 Conditional

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

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

条件付き確率。分母はメモ化再帰で求められる。

メモ化再帰の際、探索中に既に条件

「値がvのサイコロを少なくともひとつは使う」

を満たしたかを示すフラグ isok を用意する。

続きを読む

SRM 304 PolyMove

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

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

自力では解けなかった。

各頂点を1だけ引き伸ばすことによる面積の増加分を全て求める。

隣り合う頂点を使うことはできないので、DPをする。更新式は以下のとおり。

dp[i] = max(dp[i-2] + i番目の頂点を伸ばすことによる増加分, dp[i-1])

注意しなければならないのは、最初の頂点と最後の頂点が隣り合っているため、

最初の頂点を使う場合と使わない場合とで二パターンのDPをする必要があること。

続きを読む

SRM 305 UnfairDivision

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

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

各人のassetsの分け方の全パターンを列挙する。

続きを読む

2011-03-25SRM300台を練習していく

SRM 301 IndicatorMotionReverse

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

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

状態の差分をとって、差分が連続しているものをグループ化する。

方針は割とすぐ浮かんだ。


それにしてもなんだかアホなコード。130点ぐらい

続きを読む

SRM 302 DivisorInc

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

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

はじめはNを増やすように探索しようかと考えたが、間に合わないので方針を転換。

Mを減らしながら、メモ化再帰ならいける。

こういう問題を素早く解くのは苦手だ・・・110点ぐらい。

続きを読む

SRM 301 EscapingJail

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

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

ワーシャルフロイド法というものを学んだ。

続きを読む

2011-03-15div2hard 三本勝負(SRM491, 493, 497)

SRM493 div2 第三問(1000pt) CrouchingAmoebas

|  SRM493 div2 第三問(1000pt) CrouchingAmoebas - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM493 div2 第三問(1000pt) CrouchingAmoebas - hama_DU@TopCoderへの道

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

範囲を絞って正方形の位置を全探索。

はじめ、Amoebaの動かし方について、

x軸 or y軸に沿っていくらでも動かせる(飛車の動き)かと勘違いした。

続きを読む

2011-03-13SRM494、SRM498など(DIV1)

SRM498 第二問(450pt) FoxStones

|  SRM498 第二問(450pt) FoxStones - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM498 第二問(450pt) FoxStones - hama_DU@TopCoderへの道

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

各マスを、ポイントからの距離の組み合わせによってグループ分けするだけ。

続きを読む

SRM494 第一問(250pt) Painting

|  SRM494 第一問(250pt) Painting - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM494 第一問(250pt) Painting - hama_DU@TopCoderへの道

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

大きいブラシから塗れるかどうか試していけばおk

続きを読む

SRM494 第二問(500pt) AlternatingLane

|  SRM494 第二問(500pt) AlternatingLane - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM494 第二問(500pt) AlternatingLane - hama_DU@TopCoderへの道

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

各木の間のBeauty期待値を計算していけばいい、ということに気づきさえすれば簡単。

あとは 100,000 * 100,000 でintの範囲を超えてしまうため、longで計算することに気をつける。

続きを読む

2011-03-08SRM497(DIV1)

PermutationSignature

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

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

本番中では方針が浮かばず、書いちゃ消し、書いちゃ消しを繰り返した。

サンプルを見たら、D の部分だけ数字を入れ替えればいいのでは、と思った。

数列の端から端までをlen回なめる、バブルソート的な感じで実装。


問題文中の

If no such permutation exists, return an empty int[] instead.

(該当する数列が存在しない場合は、空の配列を返せ)

という文言が妙に気になり、そんなパターンあるかいなと思いつつも

疑心暗鬼にテストを繰り返し、時間がかかってしまった。

続きを読む

CssRules

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

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

この問題は2つのパートに分かれている。

  • 与えられたxhtmlをパースする
  • 最小ルール適用回数を求める

本番中ではパースするコードが正しく書けなくて撃沈。

与えられたxhtmlをパースする

正規表現を使ってタグを切り分けていく。

各タグにつき、タグ名、タグID、目的の色、および含まれるタグの一覧を記憶。

最小ルール適用回数を求める

各idのタグにおいて、8 * 8 * 8 通りのCSSパターンが考えられる。

その各パターンにおいて子のタグにそのCSSが適用できるかどうかを調べ、

タグが子を持つ場合は再度 8 * 8 * 8 通りのCSSパターンを試す。

正しく探索する方針が思いつかず、editorialを見て理解。

こんなんどう考えたら思いつくの・・・?

続きを読む

2011-03-07SRM482(DIV1)

だいぶ昔のするめだが練習として解いてみた。

LockersDivOne

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

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

普通に探索すると間に合わないけど、

配列に「次の空いてるドア」を覚えさせとけば大丈夫。

学校の課題で、Cでリンクリスト実装したときのことを思い出しながら書いた。

続きを読む

HanoiGoodAndBad

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

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

この問題は2つのパートに分かれている。

  • Daveが手数分動かした際の輪っかの状態を作る
  • Earlがその状態に辿りつくまでの手数を求める

Daveが手数分動かした際の状態を作る

問題文中の solve_Dave(N) を実行するのに 2^N - 1 ターンかかることを考えると、

2^(N-1)-1 ターンあれば 上からN-1個の輪っかをsourceからspareに移すことができ、

余ったターンのうち、

  • 1ターンは 上からN個目の輪っかをtargetに移す
  • 2^(N-1)-1ターンは再度solve_Dave

に使える。

このとき、最初に移す輪っかの数の偶奇により、spareとtargetが入れ替わるので注意する。

再帰関数を愚直に実装した。残り手数が0になったところで終了する。

Earlが特定の状態に辿りつくまでの手数を求める

一番下の輪っかから順番に考えていけばOK。求める状態の輪っかの位置が、

  • sourceにあるなら経過ターン数は0
  • spareにあるなら経過ターン数は (3^(N-1) - 1) + 1
    • 上にあるN - 1個の輪っかを target に移すのに 3^(N-1) - 1 ターン
    • 自身を spareに移すのに 1ターン
    • この状態で、上の輪っかについて考える。sourceとtargetが入れ替わるのことに注意する
  • targetにあるなら経過ターン数は (3^(N-1) * 2 - 2) + 2
    • 上にあるN - 1個の輪っかを sourceからtarget、targetからsourceに移すのに 3^(N-1) * 2 - 2 ターン
    • 自身を sourceからspare、spareからtargetに移すのに 2ターン
    • この状態で、上の輪っかについて考える。

続きを読む