Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-08-31SRM516 Div1

  • 250:208.32(+100), 500:WA, score:308.32, rank:120, rating:2150(+20)
  • 500でまたしても残念すぎるミス。もったいなさすぎる。

SRM516 Div1 250 NetworkXOneTimePad

| 22:16 | SRM516 Div1 250 NetworkXOneTimePad - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM516 Div1 250 NetworkXOneTimePad - SRM diary(Sigmar) SRM516 Div1 250 NetworkXOneTimePad - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

適当に平文と暗号文をXORして鍵の候補を出せばいいのでは

答え合わない

鍵の候補の出し方が間違ってた

直した

合った

提出

時間かかりすぎ・・・


チャレンジで鍵の候補を出すだけ出して、全部の暗号文を生成できるか全くチェックしてない人がいたので2人落とした。ラッキー。


どうでも良いが同じ鍵を何回も使ってるので全然one timeじゃない気がした


ソースコード

続きを読む

SRM516 Div1 500 RowsOrdering

| 22:16 | SRM516 Div1 500 RowsOrdering - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM516 Div1 500 RowsOrdering - SRM diary(Sigmar) SRM516 Div1 500 RowsOrdering - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

問題文むずい

何とか理解した

いかにもオーバーフローしそうなもの同士をmod取らずに比較せよとあるので、多分実際にindexの和を計算して比較するのは無理なんだろう

ということはGreedyとかであろうか。1桁決めればあとは全部決まるとか?

決まらない。むしろ逆だと気づいた。ある桁のpermutationを決めても、他の桁のpermutationに全く影響しない。

ということはそれぞれ独立に計算すればOK

書くのはあまり難しくなかった。10分ちょいくらい。

できた。オーバーフローしてないか確認。大丈夫。提出

再度見直す。大丈夫そう。


チャレンジフェーズ終わったところでPetr氏のコードを見ると、ほとんど同じだがびみょーーーーに違う

最後のSortの順番が逆である。比較関数がgreaterでなければならないのに、lessになっている。

まじか。そこはよく確認したはずだが・・・。

よく確認したつもりで間違った回答をしていたようだ。終わった。なぜ間違った結論に至ったのか全く分からない。

痛すぎる・・・


ソースコード

修正済み

続きを読む

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

2011-08-27KISSの原則

KISSの原則

| 14:34 | KISSの原則 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - KISSの原則 - SRM diary(Sigmar) KISSの原則 - SRM diary(Sigmar) のブックマークコメント

KISSの原則といって、プログラムは単純であることが望ましいと言われるが、基本的に大賛成である。

確かに、コンテストにおいても工夫することでよりシンプルな考え方で解けるものや、考え方によってコーディングがシンプルになる問題がある。

特に、場合分けが多くコーナーケースでWAしそうな場合や、コーディングが大量・複雑になるような場合には、何かしら単純化を図ったほうがいいことが多いと思う。

しかしこれがなかなか難しくて、単純化する方法に容易には気づかないことが多い。

苦労して解いたあとに他人のコードを見て、こんな簡単にできたんだ、みたいに思うこともしばしばある。

ということで、過去に解いた問題を振り返りながら、どうすれば問題を単純化できるのか、色々考えてみたい。


とりあえずは分かりやすい例として、以下考え方によって解くのが楽になる問題の一例です。


Codeforces 78 Div1 A.Help Victoria the Wise

Problem Statement

6面のサイコロがある。1面につき1つgemを取り付けることができる。gemが6つ渡されるので、取り付け方が何通りあるか答えよ。

ただし、gemはまったく同一のものが複数渡される可能性があり、回転して同一になるつけ方は同じ取り付け方とみなす。

gemの種類は最大6種類。

gemの種類は6文字の文字列で与えられる。同じ文字は同一のgem。

例:入力=BOOOOB、解=2

制約:1問2秒以内


数学的に解けそうですが、これはプログラミングコンテストの問題であるというところが1つのポイントです。


以下、僕の考える解答例です。

続きを読む

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

2011-08-21SRM515 Div1

  • 250:231.20, 550:188.58, score:419.78, rank:50, rating:2130(+87)
  • 550再提出してしまったが何とかPass。70点くらいもったいないことした。

SRM515 Div1 250 RotatedClock

| 13:57 | SRM515 Div1 250 RotatedClock - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM515 Div1 250 RotatedClock - SRM diary(Sigmar) SRM515 Div1 250 RotatedClock - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

適当にイテレーションすればOK

問題読解でみんな時間がかかっていた模様?


ソースコード

続きを読む

SRM515 Div1 550 NewItemShop

| 13:57 | SRM515 Div1 550 NewItemShop - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM515 Div1 550 NewItemShop - SRM diary(Sigmar) SRM515 Div1 550 NewItemShop - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

1時間に来るのは最大1人だよとわざわざっぽく書いてあるのでこれが重要なんだろう(英語的にすこし読み取りにくいが・・)

2箇所以上来る可能性があるのは最大12人になるから、2^12でビットDPとかかな

書いてみた

結構バグっていてデバッグに時間を取られてしまったができた

何か別に考え方は難しくないような・・・どの辺が550なんだろう

提出

あれ、ルーム内誰も出してない。なぜに・・

もう1回見直す。13人以上いるときのビットの更新方法が間違っていることに気づく。しまった・・

直して再提出。今度は大丈夫そう。出す前にもっとちゃんと見なおさないとダメだ

サンプルには13人以上いるものがないので、これはチャレンジポイントになるかもしれない。


と思ったが、自分以外は全員mapを使ったDP/メモ化だったので突っ込みどころがなかった

mapで計算量大丈夫なのかという気もするが、なかなか見積もりが難しく落とせるか判断つかない

チャレンジフェーズが始まった瞬間550が2人落とされたんだけど、絨毯爆撃しているわけでもなかったのでどういう判断で突撃したのか

不思議・・・


ソースコード

続きを読む

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

2011-08-10SRM514 Div1

  • 250:203.74(+100), 600:Opened, score:303.74, rank:52, rating:2043(+87)
  • 魔法少女・・・

SRM514 Div1 250 MagicalGirlLevelOneDivOne

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

Problem Statement

解答方針

どう見ても探索できそうにないので一発で求める方法を考える

ちょっと試してみると、nが偶数の場合は、右下、右上、左下みたいな3手でn-2のときと同じ動きができる。ということはn==0で上下左右4方向に1歩動くことが可能なので偶数のnがあれば絶対たどり着ける。

じゃあ奇数はどうかというと、(x+y)%2が常に同じところにしか行けないので、それで判定する。同じようにn-2のときと同じ動きができるので、少なくとも斜め4方向には進めるから(x+y)%2が0ならYES。そうでなければNO。

(x+y)%2の判定はちょっと知識問題チックだなと思った。

ところでxやyはマイナスがありうるので、(x+y)%2がとりうる値は実は-1,0,1の3つある。サンプルは-1になるものがないのでチャレンジポイントになる。x%2==y%2という判定をしている人を2人落とした(何とコーディングフェーズの上位2人がそのような凡ミスを・・)。ラッキーでした。


ソースコード

続きを読む

SRM514 Div1 600 MagicalGirlLevelTwoDivOne

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

Problem Statement

解答方針

oddかどうかの判定なので、まず偶奇だけ覚えればいい

ということで全部0,1に変換する

さらにn, mが最大10しかないのがポイント

c~c+m-1までのparityは1でなければならないが、c+1~c+mまでのparityも同様に1でなければならない

従ってcとc+mの偶奇は等しい。ということは、01に変換した行は、必ずm個ごとに循環する繰り返しパターンとなる。

縦についても同様。なので、m列分の縦のparityを記憶するDPが可能。


で方針はすぐ立ったけどコーディングに45分かけてもデバッグしきれなかった。

何か繰り返しパターンをビット化したのだけども、右端にはみ出す部分の処理がうまく行かなかった。

もうちょっとコーディングがまともにできるようになりたい・・・・・


ソースコード

続きを読む

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