Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-06-27TCO2010 Round2

凡ミスで500を落とし敗退しました・・・

TCO2010 Round2 250 SnowPlow

| 20:26 | TCO2010 Round2 250 SnowPlow - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Round2 250 SnowPlow - SRM diary(Sigmar) TCO2010 Round2 250 SnowPlow - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→状態を更新しながらBFS?にしては計算量が多すぎるし、随分難しいな・・・うーん・・・

→他の人の状況を確認

→240点台で出してる人がいる。実は簡単なのかな。

→1分で1レーンしか掃除できないので、最低でも全てのエッジをレーン数分往復しないといけない

→逆に、単純にツリーと考えてツリーを辿るだけで、どんな順番でも最小時間で掃除できそうだ

→ということは、ノード0から到達できないノードがある場合に-1、そうでない場合レーン数の和*2が解か

→書く→サンプル合わない

→到達できないノードがエッジを持っていなければ到達する必要がない。親切なサンプルだ。

→書き直す→サンプル通る

→これで大丈夫か・・・例外は・・・ない!提出

→500へ


チャレンジフェーズ

→特に撃墜ポイント思いつかず


システムテスト

→問題なくPassed


以下、ソースです。

BFSで連結性の判定をしたけど、Union-Findのほうが簡単だったかな。


(6.27 21:50追記)

Union-Findで書いてみました。

Union-Findのライブラリはコピーするだけなので、手で書く量が少ないUnion-Findのほうが安全な気がします。

続きを読む

TCO2010 Round2 500 RepresentableNumbers

| 20:26 | TCO2010 Round2 500 RepresentableNumbers - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Round2 500 RepresentableNumbers - SRM diary(Sigmar) TCO2010 Round2 500 RepresentableNumbers - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→少なくとも100000000は解の条件を満たす(representable numberとなる)ので、最大100000000までXから順番に解となるか判定して、解でなければXを1増やす。解の条件を満たす数字はかなり多そうなので、多分計算量は問題ないだろう。これで、あるXが解の条件を満たすかを判定する問題になる。

→判定は1桁ずつGreedyっぽくできそうではあるが・・・例外が多そう。。やりたくないですね。。

→うーん・・・とはいえ、他の方法も思いつかない・・十分に気をつけながら実装するしかないかな。

→まず、奇数同士の和は偶数になるので、最下位が奇数だとNG

→最下位以外は・・前の桁からの桁上がり(キャリー)があれば奇数、なければ偶数となる

→キャリーが発生する条件は・・・前の桁が2以上ならキャリーを発生させるもさせないも可能、0か1だとキャリーが必ず発生する。

→では、ある桁が0か1のときに、次の桁が偶数ならNG、それ以外のパターンはOKかな

→書く→サンプル合わない

→1000の場合、実際はOKだが今の判定方法だとNGですな・・これはリーディングゼロが含まれていてもtotally oddとなることを考慮しなかったのが原因みたい

→では、上記判定方法でNGとなったとき、残った数字がtotally oddとなる場合はOKとする。

→書き直す→サンプル通る

→こういう例外処理が多い問題は非常に不安だ・・・他の例外は・・うーん・・どう考えてもこれで全部だな

→提出

→1000はどうせ解けないだろうからもう一度500を確認しておこう

→・・・やっぱりどの場合でも問題ない。大丈夫だ。


チャレンジフェーズ

→お、これ間違ってる気がする。突撃!

→失敗。。なぜだ・・・。あ、、ちゃんと例外処理してる。。見落としてた・・・

→あ、この人間違ってそう・・・

→確認してる間に撃墜される

→1失敗で-25ポイント。結構みんな落ちてたなあ。。


システムテスト

→Failed

→ええーーなんで・・・

→あ・・・キャリー発生フラグを0,1以外のときOFFに戻す文が抜けてる

→酷い・・・アルゴリズムの検証にのみ注力して、プログラムの検証が疎かになっていた・・

→今度から、しっかり見直さないと・・それにしても、1文抜けるだけで天と地の差ですね。


以下、修正したソースです。

続きを読む

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

2010-06-20TCO2010 Round1

250だけ解いて辛うじてRound2に進みました・・

レーティングは微減ですが1問パスしただけでも少し持ち直した気がします

TCO2010 Round1 250 EqualizeStrings

| 16:24 | TCO2010 Round1 250 EqualizeStrings - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Round1 250 EqualizeStrings - SRM diary(Sigmar) TCO2010 Round1 250 EqualizeStrings - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→1文字ずつGreedyで良さそう

→とりあえずs[i]とt[i]で小さい方を使えば良いのでは

→違う、サンプルを見るとs[i]とt[i]が遠いときは'a'にすべきみたい

→条件を考える・・・s[i]とt[i]の距離が13未満なら2つのうち小さい方を使う、13以上なら'a'を使う、で良いようだ

→書く→サンプル通る

→簡単すぎる・・・本当に大丈夫か?

→例外ケースは・・・ありそうにない・・

→提出!500へ


チャレンジフェーズ

→あまり落とせそうなパターンが思いつかない

→落とされてる人もいるけど・・明らかに間違った書き方をしてる人みたいだ


システムテスト

→Passed


以下、ソースです

続きを読む

TCO2010 Round1 500 TwoRegisters

| 16:24 | TCO2010 Round1 500 TwoRegisters - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Round1 500 TwoRegisters - SRM diary(Sigmar) TCO2010 Round1 500 TwoRegisters - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

DP

→状態数が、100万*100万

→無理そう

→難しい・・・・とりあえずBFSで小さい値の解を列挙してみよう

→書く→サンプル通る

→ダメだ、何の法則性も見えない・・・・でも、解はそんなには長くならないみたい。フィボナッチ数列に近いので、100万でも高々30程度かな。

→どちらにせよBFSでは解けない。どうしよう・・・グラフ?でもない・・・行列?無理だな・・何も効率化できない。何か枝刈りができるのか・・・分からない・・

→何これ。こんなの解けるの?(一時間くらい色々唸る)


→とりあえず、何となくXとYの最終値から逆順に計算するのも考えてみようかな

→あれ?なぜか枝分かれができない

→あ・・そうか・・大きいほうから小さい方を減算する以外の方法がないから、分岐しない。

→すごく不思議な感じがするけど、Treeだったんですね。。これで全探索できそう

→書いた→答えが合わない

→あ、YがXより大きいときにXとYの値をスワップしてたから何か答えの文字列がおかしくなってる

→直らない~~~

→終了


チャレンジフェーズ

→BFSしてる人はいないかな~~

→一人だけいたけど、撃墜済み・・

何もできず


終了後

とりあえずスワップのおかしかったところを直す

TLEしますね。。100万*100万だから当然ですね。

→とりあえず100万でも最大30程度の長さになると想定されるので、40を超えることはないだろう。40を超えると探索をやめることにする。

→これで40*100万で最大4000万回くらいの計算量になったけど・・・まだTLEする

→string.insertを4000万回やっているのがまずいみたい。insertしないように書き換える。

→100万で1秒以内になった。


これまでにも、逆順に計算してみるという問題は何度も出てきているのに、試さなかったのは失敗でした。逆順で意味があるか分からなくても、少し考えてみることが必要そうです。


以下、終了後に書いたソースです。一応システムテストは通ります。

長さ40以下になる確証は何もないので、他の人がやっているようにまずは長さ最小になるX,Yの値を全部求めてから文字列比較を行うのが確実のようです。

続きを読む

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

2010-06-19SRM473 Div1

特殊ケースで250がWA、500がTLEしレーティング-178と惨憺たる結果に・・・

ノーゲームになったSRM471から悪い流れが続いています・・・

特殊ケースにしっかり対応できるかどうかで、正答率が全く変わってくるので、しっかりケースを洗い出せるようにしないといけないですね。

SRM473 Div1 250 SequenceOfCommands

| 15:56 | SRM473 Div1 250 SequenceOfCommands - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM473 Div1 250 SequenceOfCommands - SRM diary(Sigmar) SRM473 Div1 250 SequenceOfCommands - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→シミュレーションかな・・・面倒くさいな・・・

→実は1周終わった時点で初期状態と同じ向きを向いていたらunboundedで良いのではないか(←間違い)

→書く→サンプル通る→提出→500の問題に行く

・・・(中略)

→終了5分前に見直す

→まずい、間違っている・・・Sが1つも出てこない場合に明らかに間違った答えを返すことに気づく

→直す、submit→else文が抜けてる→直す、submit・・・できず時間切れ

→よく見たらまだ間違ってる。1周で原点に戻ってくるものは全てboundedだ。シミュレーションしないと解けない。終わった・・・


チャレンジフェーズ

→みなさん、シミュレーションで解いてますね。撃墜できません。

→撃墜されました。終わった・・・


以下、終了後ちゃんと書き直したコードです。

1周後の状態で判定してますが4周後に原点に戻るかの判定でも良いですね。

続きを読む

SRM473 Div1 500 RightTriangle

| 15:56 | SRM473 Div1 500 RightTriangle - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM473 Div1 500 RightTriangle - SRM diary(Sigmar) SRM473 Div1 500 RightTriangle - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→えーと、直角三角形の外心は斜辺の中点になるので・・・ある点と円の反対側の点がredなら、points-2を加えれば良いかな?

→えらく簡単だな・・・

→書く→サンプル通る

→一応適当にランダムなケースを入れてみようかな

→特に問題なし

→提出→1000の問題に行く


1000の問題はよく分からない。時間がなくなったので諦め。


チャレンジフェーズ

→速攻で撃墜される。

→ええええ!?何で・・・

→チャットで誰か話していたけど、ワーストケースの作り方が誤っていた

→a,b,cが全部0のときが、ワーストケース。確かに。何でこんなことに気付かなかったのか・・・


確かに500にしては簡単すぎたし、ワーストケースもあまり考えていませんでした。

でも、入力ケースを作成する部分がトラップっていうのはどうなの、という気もします。それも含めて問題だということなんだろうけど・・・


入力ケースの作成を二分探索に直したら通りました。

続きを読む

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

2010-06-06Google Code Jam 2010 Round 2

BのS/LとCのSを解いて31点2h10mで645位でした。

Round3には進めず・・・あと30分早く解ければ次に進めましたが、遅すぎてダメダメでした。

  • 問題A→実装がきつそう
  • 問題B→Smallの点が高く難しそう
  • 問題C→Smallはただのシミュレーションぽい

ということで問題Cから取り掛かりました。

Google Code Jam 2010 Round 2 C Bacteria

| 00:16 | Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) Google Code Jam 2010 Round 2 C Bacteria - SRM diary(Sigmar) のブックマークコメント

バクテリアの増殖と死滅の過程をシミュレーションします。

上と左の両方にバクテリアがいないと増殖しないので、初期状態の右端バクテリアより右側及び下端バクテリアより下側にバクテリアが増殖することはありません。

ということで、Smallでは100*100の範囲内でバクテリアの増殖・死滅をシミュレーションすればよいです。

15分くらいでしこしこと書きましたが、あまりにもミスが多く、デバッグでさらに15分くらい消耗・・・

ダメすぎたので、間違えたところを書き留めておくことにします。

  • 増殖の条件が、左か上のどちらかにバクテリアがいるだけで増えるようになっていた
  • gridの次の状態をgrid2として記録していたが、繰り返し時にgrid2をgridにコピーし忘れていた
  • 最初のバクテリアの個体数を計算する際に、重複しているところを2重に数えていた(問題文に注意としてわざわざ書いてあるのに・・・)

3個目のミスについては、シミュレーションの終了条件を個体数管理によって実現しようとしましたが、そもそもシミュレーションの過程で必ずグリッド全体をスキャンするので、個体数管理は必要なかった・・・

当たり前の確認をきちんとしていないからこうなるんですかね。。

  • if文はよく内容を確認する
  • 問題文の注意点は実行前に再確認する
  • 不必要に複雑なことをしようとしていないか確認する

提出したソースは以下のとおりです。

続きを読む

Google Code Jam 2010 Round 2 B World Cup 2010

| 00:16 | Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) Google Code Jam 2010 Round 2 B World Cup 2010 - SRM diary(Sigmar) のブックマークコメント

みなさんの提出状況を見ると、BのS/Lの提出率が高かったため、Cの終了後Bに取り掛かりました。

この問題については、以下のような仮定をした上で進めます。

  • 各々のチームが勝ち進むかどうか分からないので、すべてのチームが決勝まで進むと仮定する必要があります。
  • 見逃していい数というのは分かりにくいので、決勝までのうち、見なければいけない試合数に変換します。

Smallについては、Greedyな戦略で解けそうでした。

チーム0から順に、決勝から順に見なければいけない試合数分チケットを購入します。

チーム0の必要分を購入したら、チーム1でまた決勝から必要分購入していきます。(もちろん、既に購入してある分は除きます)

これだけで最小費用でチケットを購入できると思います。(試してませんが)


すぐに書けそうでしたが、Largeの提出率が高いので、こちらもやり方を考えてみました。

LargeはDPになりそうです。

チーム0から始めて、必要な試合数分(P-M[i])だけチケットを購入します。

C(n,k)をnからk個選ぶ組み合わせ数とすると、C(P,(P-M[i]))通りの購入方法があります。

次に、チーム1では、チーム0で購入したチケットに加えて、さらに必要なチケットだけを購入します。(これも、チーム0での購入状況に従って何通りか購入方法ができます)

というのをdfsでチーム2^P-1まで続けていき、コストが最小になるものを解とします。


現在のチケットの購入状況のうち、次のチームに対して意味のあるチケットかどうかを判断して状態を更新していくところが少しややこしく、実装に不安がありましたが、恐らくLargeを解かねば通過は難しいと考え、SmallはスルーしてLargeに挑むことにしました。

実際に書いてみると、思ったよりも状態の更新は難しくなく、むしろ計算量を減らす部分で苦労しました。

n個のうちk個を選ぶ組み合わせについて、

  • for文で1<<n通り回して、</li>
  • ビット数がkになる場合以外continue

という方針で書いたのですが・・・

  • 前回の購入時に既にk個を超えたチケットを購入している

という場合に、うまく動きませんでした。(これも、最初正しい答えが出ず原因解明に苦労しました)

とりあえず、

  • ビット数k未満のときcontinue

と変更してみましたが、特定の入力ケースにおいて計算量が爆発的に増え、TLEしてしまいました。

よく考えると既にk個以上のチケットが購入されている場合、これ以上チケットを買う必要はないので、

  • 前回の購入時に既にk個以上チケットを購入している場合、これ以上チケットを購入しないという例外処理をする

で問題なく動きました。

このあたりでビット演算でかなりごちゃごちゃして混乱してしまい、時間を浪費してしまい、結局1時間半近くかかってしまいました。

なんとか、うまくビットDPを混乱せずに書けるようになりたいですが・・・

練習するしかないでしょうか。


あとで、解説や他の人の解答を見ると、決勝のチケットからdfsで購入/非購入を試していけば良かったようです。

このほうがコードも簡単だし、計算量も少なくなりそうです。

一度解けそうな方法が見つかると、他の方法を探そうという意志がかなり弱くなってしまうため、解法が妙に複雑そうな場合は気をつけて別解を考えてみるようにしたいです・・・

以下、提出したソースです。solve関数が本体です。

続きを読む

Google Code Jam 2010 Round 2 A Elegant Diamond

| 00:16 | Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) Google Code Jam 2010 Round 2 A Elegant Diamond - SRM diary(Sigmar) のブックマークコメント

残り30分となってしまいましたが、この時点で550位くらいで、おそらくもう一問解かないと通過できないだろうという状態でした。

問題Aについては実装が難しそうでしたが、既に問題の内容は把握済みでしたので、これをやるしかないと思い、進めました。


やり方として、せっかく綺麗なダイアの形で与えられた入力をわざわざvector <int>に直してしまい、非常に処理が煩雑になってしまいました。。。

stringのまま読み込めば良かった・・・不必要にメモリ効率を良くしようとする悪いくせが出てしまいました。

30分では全く間に合わず、残念ながら私のGoogle Code Jam 2010はここで終わってしまいました。

他にも色々アルゴリズム的に判定処理を間違えたりしていたので、どちらにしてもダメでした。

今の私の実力ではこれでベストを尽くしたという感じです。

これ以上進むためには、妙なミスを減らすこと、コーディングを早くすること、そのためにさらに訓練を積み重ねることがまず必要なようです。

以下、コンテスト終了後に書いたコードです。solve関数が本体です。stringでの読み込みに直してあります。

check関数の中で同じチェックを2度するなど冗長な部分がありますが、このほうが早く書けると思うのでそのままにしてあります。

続きを読む

Google Code Jam 2010 Round 2 D Grazing Google Goats

| 00:17 | Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) Google Code Jam 2010 Round 2 D Grazing Google Goats - SRM diary(Sigmar) のブックマークコメント

コンテスト中は読むこともできませんでしたが、後で読んでみるとSmallは2円の重なる面積を求めるだけのようなので、簡単そうでした。

ということで解いてみましたが、意外と扇形の面積の求め方で場合分けなどが必要になってきて、時間がかかってしまいました。(40分くらい)

もっと簡単に書けるみたいなので、幾何に関する勉強が必要です。

以下、ソースです。solve関数が本体です。

続きを読む

コーディング時の注意点1

| 00:17 | コーディング時の注意点1 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - コーディング時の注意点1 - SRM diary(Sigmar) コーディング時の注意点1 - SRM diary(Sigmar) のブックマークコメント

Google Code Jam 2010 Round2の反省点

  • コーディング前
    • 問題文が長い場合、注意点を書き出す
    • 解法が妙に複雑な場合はより簡単な別解がないか考えてみる
    • 計算量に問題ない限り、可読性、書きやすさを重視したデータ構造を利用する
  • コーディング中
    • if文はよく内容を確認する
    • 不必要に複雑なことをしようとしていないか確認する
  • コーディング後
    • 問題文の注意点は実行前に再確認する
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100606