Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-29SRM507 Div1

  • 250:242.03, 500:212.32(-25), 900:Opened, score:429.35, rank:104, rating:2029(+59)
  • 久々に赤い人たくさん。ターゲットもいる部屋だった。
  • もっと500を早く解けるようになりたい。。

SRM507 Div1 250 CubeStickers

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

Problem Statement

コーディングフェーズ

うーんうーん・・普通に考えれば3色で塗り分け可能だよな

それから、1色で3枚以上あっても意味ない。同じ色は対面にしか貼れないから。

ということは、、3色未満ならNO

3色以上あるとき、、1枚しかないやつはどうするか・・

1枚しかないのは2つ組み合わせれば1色×2枚の扱いにできるから、2色以上の枚数と1色の枚数を適当に数えればいいや

書いた→サンプル通った→提出

そこそこ早くできた。


ソースコード

続きを読む

SRM507 Div1 500 CubePacking

| 14:02 | SRM507 Div1 500 CubePacking - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM507 Div1 500 CubePacking - SRM diary(Sigmar) SRM507 Div1 500 CubePacking - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

むずい・・・math的な雰囲気もするが、たぶん探索系だな

Lが最大10と小さいのを利用するのか?うーん・・・分からん・・・

底面のサイズとかで探索するんだろうか・・・でも探索の範囲が分からない・・・

探索の範囲についてはサンプル1はすごくいいヒントで、解が素数×素数×素数になる可能性があるのが分かる

つまり、解の最大は2,000,000,000くらいだが、そうすると1~20億くらいまでの素数を探索しなきゃならない

その組み合わせを底面サイズとして用いるとなると、さすがに計算量が明らかにオーバーする

うーん・・・探索の範囲を限定しようとすると、素因数分解みたいな話か・・?


あ、もう残り45分か

900が簡単だったらまた残念なことになるから、ここらで問題を読んでおこう

900はDPぽいが、ストレートにやると、計算量が2億超えるので難しいな・・

提出者も全然いない・・これはきっと難しいんだ

15分くらい費やしてまた500に戻る


さて、素因数分解とかって、答えが分かってたら計算できるけど、答えの範囲ってどうなるんだ?

そうか・・ここでLの最大10が生きてくるんだ

底面L*Lの長方形にすると、解が最大でもL*L*L*Nb+Ns+L*Lになるじゃないか

最小はL*L*L*Nb+Nsだから、たかだかL*L(=100)の範囲に解が必ずある!

ということで、解の値をイテレートして、解となりうるかどうかを調べれば良いのでは

解になるかどうかは、素因数分解まではする必要はないな。適当に約数を求めて、、サイズLの箱が全部収まるか調べればOK

書いた

サンプル合った

大きい入力で試す→だいたい300msくらい。問題ないかな・・・

提出


チャレンジフェーズ

サンプル弱いから、色々適当に書いて出しちゃってる人がいるに違いない

この人怪しい→突撃→失敗 読み間違えた・・

どんどん他の人が落ちていく・・ターゲットの人が落としまくっている。やばい

今度は明らかに間違ってる人発見→落とせる入力作成中に落とされる

だめだ・・・チャレンジ強い人がいるとやられたい放題だな・・


ソースコード

続きを読む

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

2011-05-23SRM504.5 Div1

  • 250:193.15, 550:TLE(-100), score:93.15, rank:608, rating:1970(-129)
  • 色々失敗しすぎて痛々しすぎる回だった。最近調子が悪い。ひどくレーティングを下げている。

SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit

| 23:21 | SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit - SRM diary(Sigmar) SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

とりあえず下1桁だけ考えればよいことは分かった

ここで4の数と7の数でイテレートすればすぐ終わったんだけど、何を思ったかDFSを始めてしまった

しかもうまく書けなくてえらく時間がかかる

何とか15分くらいで書いて提出

幸先悪い・・・


ソースコード

続きを読む

SRM504.5 Div1 550 TheJackpotDivOne

| 23:21 | SRM504.5 Div1 550 TheJackpotDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM504.5 Div1 550 TheJackpotDivOne - SRM diary(Sigmar) SRM504.5 Div1 550 TheJackpotDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

サンプルの最後に答えが書いてあるように見えるんだけど・・気のせいかな・・

(最終的に全員同じ金になる)

ストレートフォワードに考えれば、全員同じ金になるまでシミュレーションして、その後は残り金を一気に分配で計算できるだろうが・・・

いくらなんでも簡単すぎ。そんなのが550であるはずがない(←あるはずがあった)

まあでも他に思いつかないしとりあえずやってみよう

できた

サンプル合うなあ・・計算時間も問題ない

最大ランダムケース投入

TLEする

デバッグしてみる

オーバーフローしとる

何それ・・・Javaの人有利じゃん・・・

しかしそもそもBigIntegerを使ったとしてもこの方針で最大ランダムケースが時間内に終わるのだろうか

手元にある遅い多倍長ライブラリで試してみよう

答え合わない

意外と使ってないライブラリの適用にすごく時間がかかる。ライブラリのインタフェースが非常にいけてなかった

時間かかったが、できた

最大ランダムケース問題ない

時間なくなってしまったしこれでとりあえず出すか・・

提出

さて・・

本当にランダムで最大ケースになるのか

・・・

・・・

ならない

最大は、{{1,1,1,...,1,1,10^18}, 10^15}ぐらいのようである

試してみる→TLE

終わった・・・・・・

チャレンジでも頑張ろう


チャレンジフェーズ

ということで多倍長演算をしている人に先程の最大ケースを投げてみる

4失敗

終わった・・・なぜだろう・・


後で

自分の持ってる多倍長ライブラリがあまりにも遅すぎるだけだった

本来進むべき解法は、各moneyをそれぞれ人数で割って商と余りを求めておくことだった

何か色々横道にそれているうちに真っ当な解から外れてしまったな・・・

計算量もちゃんと見積もっておくべきだった。

今回の最大ケースは、1回の分配で( (最大の人の金)-(最小の人の金) )/人数(=47)くらいのお金が配当されるので、47回で最大と最小の差が46/47くらいになると考えれば良い

従って47*log_(47/46) 10^18=約10万くらいなので計算量は楽勝である。うーん・・・


ソースコード

以下は多倍長を使わずにできるよう修正したもの

続きを読む

SRM504.5 Div1 900 TheTicketsDivOne

| 23:21 | SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

見たところ、無限にDPを繰り返せば答えが出るタイプのよくあるやつにしか見えない

実際には無限に繰り返さず適当に打ち切っても精度的には問題ない

漸化式さえできれば、書くだけ

これこそ550くらいが適正じゃないのか・・・

今度から900が出たら問題くらいは読もう・・・


ソースコード

続きを読む

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

2011-05-22Google Code Jam 2011 Round 1A

  • A-small/A-Large/B-small(3WA)/B-Large:Passed, score:50, penalty(time):2:20:56, rank:139
  • A, B, Cがそれぞれポイントに合った難易度でいいセットだったと思う

Google Code Jam 2011 Round 1A A FreeCell Statistics

| 23:13 | Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) Google Code Jam 2011 Round 1A A FreeCell Statistics - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

サンプルが親切。

PGが0か100のときに、PD!=PGだと矛盾するのでBroken

それ以外の場合は、PGはGの上限がないので任意の値で実現可能

(典型的にはGを100の倍数とすると、G*(PG/100)が必ず整数になるので、G*(PG/100)がN以上となるようにGを適当な100の倍数とすれば必ず実現できることが分かる)

ということで後はN以下のDでD*(PD/100)が整数となるものがあればPossibleということになる

式を変形するとD*(PD/100)=x⇔PD/100=x/D

すなわちPD/100を約分すると最小のDはその分母となる

ユークリッドの互除法を使用して最小のDを求め、N以下となるかどうかを確認すればOK

small通った

Largeダウンロード、一瞬で回答出た

中身を確認すると全てBrokenになっている・・・

問題文の上限を見直すと、10^15と書いてある。オーバーフローしている。不注意だった。

intをlong longに直す。

再度run。今度はPossibleがたくさん出てきたので良さそう

提出

ここまで15分くらい


ソースコード

続きを読む

Google Code Jam 2011 Round 1A B The Killer Word

| 23:13 | Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) Google Code Jam 2011 Round 1A B The Killer Word - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Seanの戦略が分かりにくい。exampleなかったらかなり理解が大変だったろうな・・

さて方針が思いつかない。

普通にシミュレーションするとLargeでTLEするよなあ

色々考えたが、Seanの戦略はシミュレーションしないとやはり最大失点を求めることが難しいように感じる

よく考えれば、シミュレーションを適当に効率化すればLargeでも間に合いそうな気がする

方針は、、、

  • 同じ長さのwordをグループ化して、各グループ毎にポイントを求める
  • 同じグループの中でも、1文字guessする毎に、開いた文字の位置が全く同じものをグループ化する
  • グループが1つになった時点でそのグループのシミュレーションを終了する

ぐらいのことをやれば良いのでは。

書いた→サンプル合った→提出→WA

なぜだ・・・

分からないので適当に細かいところを直してみるが合計3WA

再度問題文を読みなおす

ポイントが同じ場合はDictionaryで早く現れる順と書いてある

てっきり辞書順かと思っていたが、lexicographically smaller(earlier)とは書いていない

Dictionaryって、引数の名前かよ・・・

直した

通った

年のためsmallの時間を計測

0.08秒くらい。Largeは1000倍くらいのスケールなので大丈夫そう

Largeダウンロード

1分くらいで計算終了

提出

ここまで2時間くらい

最後のWAのデバッグで30分くらい無駄にした。問題文は本当によく読まないと・・・・・・

(問題文があまり良くないような気もするが)


ソースコード

提出時から多少整形しました

続きを読む

Google Code Jam 2011 Round 1A C Pseudominion

| 23:13 | Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) Google Code Jam 2011 Round 1A C Pseudominion - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

残り30分弱では解けませんでした

以下は終了後の検討内容


まず、turnボーナスは手に入ったと同時に全部使ってしまったほうが良いのは明らか

turnボーナスが0のものはどう考えれば良いかという問題になるが、ここではcardボーナスの最大値が小さいのが重要なポイント

smallはcardボーナスが最大1なので、smallから考える


cardボーナスが1のものをc1、0のものをc0というグループに分ける

ここでc1及びc0を使用枚数を固定すると、各グループの中ではどんな順番で使ってもscore以外の状態が変わらない

従って、各グループの中ではscoreボーナスが大きい順に使ったほうが良いのだろうということになる

また、c1とc0についてはc1を先に使ったほうが選択肢が広がるため、まずc1をスコアが大きい順に使用し、次にc0をスコアが大きい順に使うという順序になる

あとはc1の使用枚数を全探索すれば、答えが出る。


ということで、Largeも同様にできそうであるが、実はこの考え方だとc2が登場するだけで劇的に難しくなる

ストレートフォワードに考えれば、選択肢を広げるため、c2をスコアが大きい順に使用し、c1を使用し、c0を使用し・・・という順番で良さそうに見えるが、これではWAとなる

以下のようなのが反例

(ここでは前からN枚が手札、後ろのM枚がデッキとする)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,0,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card1使用, card:2,3, score:6, turn:1
  3. card3使用, card:2,4,5, score:11, turn:0

c1のcard1より先にc2のcard2を使用すると、スコアは7にしかならない。

これは、c1でゲットしたカード内に手札のc2よりスコアの高いc2が入っていたからである。

なので無条件にc2から進めてもダメである。

ということで、c1とc2の使用タイミングを探索しようとすると、計算量が爆発する

そこで、以下のような条件を利用してDPする

  • c1とc2の使用した枚数が同じであれば、結果的にゲットしたカード(使用したものを含む)は常に同じになる
  • c1とc2の使用した枚数が同じであれば、よりスコアボーナスの大きいものを使用したほうが望ましい

ということでc1とc2の使用枚数を状態とすると、そのときのスコアが高いものだけを使用するDPが利用できる

ただし、例外があるので注意が必要である。

以下のような反例を考える。(これは上記の例のcard4のturnボーナスのみを変更したものである)

N=3, M=3

c={0,1,2,2,0,0}

s={0,6,1,5,0,0}

t={2,0,0,0,2,0}

上記の例で最適なパスは以下の通り

  1. card0使用, card:1,2, score:0, turn:2
  2. card2使用, card:1,3,4, score:1, turn:1
  3. card4使用, card:1,3, score:1, turn:2
  4. card1使用, card:3,5, score:7, turn:1
  5. card3使用, card:5, score:12, turn:0

card0,2,4,1の順で使っても、card0,1,3の順で使っても、c1とc2の使用枚数は同じであるが、0,1,3の順で使用すると残りのturn数が0となってしまい0,2,4,1の順より損である

これは、turnボーナスのカードがturn0のときに使えないという制約のためである。

従って、turnが0となる場合は、そうでない場合と区別して扱う必要がある。

これを踏まえてコーディングすると一応通る。

計算量はn=N+Mとすると、O(n^3log n)くらい?

なお公式の解説にはもっとコーナーケースを考えなくてよさそうなO(n^5)のDPが載ってました


ソースコード

続きを読む

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

2011-05-15TCO2011 Qual1

  • 250:245.84, 500:445.39, 1000:Opened, score:691.23, rank:80, rating:2099(+49)
  • 1000の通過率が低く、チャレンジ勝負のような回になってしまったがチャレンジできず

TCO2011 Qual1 250 MinimumLiars

| 14:25 | TCO2011 Qual1 250 MinimumLiars - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Qual1 250 MinimumLiars - SRM diary(Sigmar) TCO2011 Qual1 250 MinimumLiars - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

流石に全探索するだけ


ソースコード

続きを読む

TCO2011 Qual1 500 FoxListeningToMusic

| 14:25 | TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) TCO2011 Qual1 500 FoxListeningToMusic - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何となく、曲の終わるタイミングが時間tである確率をDPすれば良さそうである

書いた

サンプル合った

提出


ソースコード

続きを読む

TCO2011 Qual1 1000 SquareSeries

| 14:25 | TCO2011 Qual1 1000 SquareSeries - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Qual1 1000 SquareSeries - SRM diary(Sigmar) TCO2011 Qual1 1000 SquareSeries - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

簡単そうでややこしい

何となく、BBBBBとかWWWWWとかBWBWBWBWとかWBWBWBWBとかのパターンにしかならなさそう

ただし最初と最後だけ任意のパターンが出てきそうな気がする

しかしそれで本当に合うか分からなかったのでDPすることにした

実装が大変・・・

書ききれず・・・


ソースコード

後でプラクティスで通した

計算量を多少無駄にしても簡単に書くのがまだ少しできていない

こういうのちゃんと整理して書けるようにならないと・・・

続きを読む

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

2011-05-08Google Code Jam 2011 Qual Round

  • Qual Roundだけあって難しい問題はない

Google Code Jam 2011 Qual Round A Bot Trust

| 13:13 | Google Code Jam 2011 Qual Round A Bot Trust - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round A Bot Trust - SRM diary(Sigmar) Google Code Jam 2011 Qual Round A Bot Trust - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

シミュレーションするだけ

どうもこういうの書くのが遅くて良くない

ソースコード

続きを読む

Google Code Jam 2011 Qual Round B Magicka

| 13:13 | Google Code Jam 2011 Qual Round B Magicka - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round B Magicka - SRM diary(Sigmar) Google Code Jam 2011 Qual Round B Magicka - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

シミュレーションするだけ

どうもこういうの書くのが遅くて良くない

ソースコード

続きを読む

Google Code Jam 2011 Qual Round C Candy Splitting

| 13:14 | Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) Google Code Jam 2011 Qual Round C Candy Splitting - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

パトリックの計算方法はxorに等しい

ある2つの集合に分けたとき、各集合のxorがx1、x2となるとすると、xorの性質よりx1=x2のときx1^x2=0

従ってNOとなる条件は、全てのキャンディをxorして0にならないこと

また、NOとならない場合x1^x2=0となることから、どのような分け方をしてもx1=x2となる

なのでパトリックには一番価値の低いキャンディを1つあげれば良い


ソースコード

続きを読む

Google Code Jam 2011 Qual Round D GoroSort

| 13:14 | Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) Google Code Jam 2011 Qual Round D GoroSort - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

サンプルを見ると、1,2と3,4でそれぞれ入れ替わっていてグループ化できる

何となく位置が入れ替わっているものをグループ化してそれぞれ入れ替えてやれば良さそうである

その場合、各要素が正しい位置に行く可能性はそれぞれ要素数分の1であるため、大体一回のシャッフルで1個の位置が合うものと想定できる

従って、グループ化したときの要素数がおそらくシャッフル回数の期待値である(ただし要素数1のときを除く)

以上から、グループ化して要素数1個以外の要素数を全て足しあわせたものが解となる


と考えて解答したがAnalysisを見たところ、グループ化しなくても良く、正しい位置にない要素の数が解となるとのこと。

確かに自分の解答と答えは同じになるが、グループ化してシャッフルしなくても良いというのは少し直感的ではなかったのでなかなか面白い。


ソースコード

続きを読む

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

2011-05-04SRM505 Div1(復習)

SRM505 Div1 500 SetMultiples

| 07:41 | SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) SRM505 Div1 500 SetMultiples - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

まずA-B区間とC-D区間を分けて考えると、k=2だけ考えれば良い

(B/2以下の数は2倍するとB以下である。また、2倍してもB/2以下の数は更に2倍すればいつかはB/2~Bの区間に入る。逆にB/2よ

り大きい数は2倍するとBを超えるため必ず残す必要がある。)

なのでAはmax(A, B/2+1)、Cはmax(C, D/2+1)とする

あとは、A-B区間のうちC-D区間の約数になっているものを減算するだけである

ここでA-B区間の数を1つ1つイテレートなどすると明らかにTLEとなるため、kをイテレートすることにする

まず最初にk1=D/B, k2=(C-1)/A+1とすると、k1はBがD以下となる最大のkであり、k2はAがC以上となる最小のkである

この時点でk2<=k1だとすると、A-Bの全区間がC-Dに入ることは明白である

続いてk1<k2の場合は、k2をD/Aに置き換えて、kをk1<=k<=k2の区間でイテレートすれば良さそうである

ここであるkのときに、C-D区間に入るA-Bの最大値をhi、最小値-1をloと置く

そうすると、hi-loが必要ない数字の数ということになる

また、次のkはhiがlo以下の最大の値となるように選べば重複が発生しないため単純に解から減じていくことができる

ということで後はコーディングするだけなのであるがminとかmaxとかいっぱい出てきて非常に間違えやすい

実際プラクティスで2回もWAを出した。考え方だけでなくコーナーケースのケアもとても難しい。。。

どうも上位の人の解法を見ると別の書き方をしている人もいるのでもう少し間違えにくい解き方もありそうではある。


ソースコード

続きを読む

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

2011-05-03SRM505 Div1

  • 300:Opened, 500:Opened, score:0.0, rank:306, rating:2050(-122)
  • 向いてない問題セットだった。Easy通ったのが300人未満とか全体的にもあまりに難易度高すぎでは?

SRM505 Div1 300 RectangleArea

| 00:18 | SRM505 Div1 300 RectangleArea - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM505 Div1 300 RectangleArea - SRM diary(Sigmar) SRM505 Div1 300 RectangleArea - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

うむ意味わからん

サンプル0から類推するに、要するにある四角形の4隅のうち3隅が分かれば残りの1隅の面積分かるよと言いたいらしい

例えば、{"YNNY", "YNNN"}とかあったら、右下のNがYになると思えばいい

で・・・?

GreedyにまだYになってないNをYにするとか?で良い訳ないよなあ・・

・・・

・・・

と思ったが、よく考えるとそれでいいような気がする

"YN", "NY"みたいなのがあれば、どちらのNをYにしても同じで可換ぽい

書き始める

途中でなんかやっぱり間違ってる気がしてきた

30分経ってるしハマりそうだから500も見ておこう→数論ですぐに解法が思いつきそうもない感じだったのですぐ戻ってきた

やっぱりさっきの解法は怪しくて別の方法で解けそうな気がする

例えば"YYNN", "YYNN"とかみたいに同じ行があれば併合して一つの行にできるのではないか

それから"YYNN", "NNYY"みたいにYが一つも重複しない行は1つNをYに変えればやはり併合できるのではないか

とか色々考えていたらコーディングフェーズが終わってしまった


後で

まず1つ目の解法ですが実際GreedyにNをYに変えていくだけで良かったらしい

とりあえず書いて出しとけばよかった・・・・・・・・・・


2つ目の解法ですがやはりこちらでも解けそう

"YYNN", "NYYN"みたいに2つの行で1つでも同じ列にYがある場合は、必ず"YYYN", "YYYN"というようにYのパターンをORできる

行と列を入れ替えても同じ

ということでどんどん併合していって、最終的に各行と列にYはたかだか1個だけ残る

Nのみしかない列や行は併合できないので残す

すると{"YNNNN", "NYNNN", "NNNNN"}みたいな感じになる

Nのみの行と列はそれぞれYを1個ずつ追加しないといけないので解に行数と列数を加える(上の例では行1+列3)

Yを含む行と列は、行数(例では2)からマイナス1しただけ併合が必要なのでそれを加える

ちなみにYがひとつもない場合は行数+列数-1が答えになる

以上をまとめるとソースは以下のようになる


あとチャレンジフェーズ見た感じではすごく短い解法の人もいたので他にも何かありそうです。


ソースコード

続きを読む

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