Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-02-12SRM457 Div1 500 TheHexagonsDivOne

SRM457 Div1 500 TheHexagonsDivOne

| 19:24 | SRM457 Div1 500 TheHexagonsDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM457 Div1 500 TheHexagonsDivOne - SRM diary(Sigmar) SRM457 Div1 500 TheHexagonsDivOne - SRM diary(Sigmar) のブックマークコメント

7つの六角形が蜂の巣のようにくっついた図形がある(中央の六角形の周りに6つの六角形がくっついている配置)。
この六角形の中に、1つずつ数字を入れる。数字は1~n*2の間のいずれかであり、同じ数字は2回使えず、隣り合った六角形の中の数字はnで割った余りが異なる値でなければならない。nが与えられたとき、数字を配置する方法が何通りあるか答えよ。ただし、回転すると同じ配置となるものは1つと数える。
nは1~150の間の値。

以下、C++のTop Submissionを参考にした解法です。
この問題では、数字は全部でn*2個あり、そのうち隣同士に配置できないペアがちょうどn個あると考えることができます。例えばn=10なら、1,11が1つのペア、2,12が一つのペアとして、数字全体を10個のペアの集合と考えることができます。
既に配置した数字の個数を深さとして、dfsと枝刈りにより答えを求めます。ここで、既に配置してあるペアの数、及び各六角形に配置した数字を配列などで記憶しておきます。n=10の例では、1,2,3,12が配置済とすると、配置済のペア数は3です(2と12は同じペアだから)。
深さ0から、新たに数字を配置していきます。新たに数字を配置する場合、配置済のペアに含まれる数字を配置するか、配置されていない新たなペアの数字を配置するかの2通りに場合分けすることができます。

  • 新たなペアの数字を配置する場合

配置済のペア数をcとすると、(n-c)*2種類の数字を配置可能です(ただしn-c>0のときのみ)。どの数字を配置しても同じ条件なので、とりあえずc+1の数字(上記のn=10の例でいうと4)を配置してdfsした結果を(n-c)*2倍します。(この枝刈りによって効率的に解が算出できます)

  • 配置済のペアに含まれる数字を配置する場合

上記の方法で新たなペアの数字を配置すると、配置済のペアに含まれる数字は1~c及びn+1~n+cの範囲の数字になります。この範囲でfor文を回して、配置する数が配置済でなく、隣の数字と同じペアでない場合のみ、dfsします。

最終的に7個目まで数字を配置できた場合に、解を+1していきます。
上記のような手法でdfsをすると、最終的にペア数は最大でも7なので、繰り返し回数は7!*(2^7)=約650,000を超えることはありません。
最後に、回転すると同じ配置になるものを除くため、dfsによる解を1/6することで最終的な解が算出できます。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100212

2010-02-11SRM457 Div1 250 TheTriangleBothDivs

SRM457 Div1 250 TheTriangleBothDivs

| 14:09 | SRM457 Div1 250 TheTriangleBothDivs - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM457 Div1 250 TheTriangleBothDivs - SRM diary(Sigmar) SRM457 Div1 250 TheTriangleBothDivs - SRM diary(Sigmar) のブックマークコメント

GMT-9からGMT+9までの19種類のタイムゾーンのいずれかで時刻を表示する特殊なデジタル時計がある。表示方法は"HH:mm GMTof"。HHは00~23で時を表し、mmは00~59で分を表し、ofはグリニッジ標準時間からのずれを表す(例えばGMT+4ならGMT+0から4時間進んでいる)。グリニッジ標準時間はGMT+0で表されるため、GMT-0という表示になることはない。
この時計の一部が読み取れなくなった。読み取れない部分は?で表示される。このとき、GMT+0のタイムゾーンにおける時刻を"HH:mm"の形式で答えよ。複数の解がある場合、最も辞書順で早い解を答えよ。

  • 解1

"00:00 GMT-9"から"23:59 GMT+9"まで全てのパターンについて与えられた時刻と合致するか試行し、GMT+0に補正したときの時刻が最も早い時刻になる場合の解を返すことで答えが求められます。なおmmの部分は常に?を0に置き換えて良いので試行回数を減らすことができます。問題文に明示的に書いてありますが、GMT-0という表記がないことに注意する必要があります。

  • 解2

HHの部分とofの部分で?の有無から、合致しうるGMT+0の時刻の範囲を計算することができます。HHの10の位が?ならiを0~2、?以外ならiをその値、HHの1の位が?ならjを0~9、?以外ならjをその値として、i*10+jを計算し、ofの部分も同様に取りうる範囲の値を調べて補正します。for文でiやjやof部分の値を変えつつ試行し、最小値を求めます。iやjなどの初期値、終了値を求めるためにある程度細かい場合分けが必要になります。また、i*10+jが24以上になる場合を除かなければなりません。

ほとんどの人は解1のような方法で解いてたと思います。
私は本番中は解2の方法で解きましたがi*10+j>=24のときを除くのを忘れてSystem Testに落ちてしまいました。
やはりなるべくコードは簡単に書けるほうが良いですね。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100211