Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

[C56]

ついにターゲットですか・・・おめでとうございます!><

[C57]

ありがとうございます!
  • 2010-07-11 09:16
  • rsujskf
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1403-f0289ff2
この記事にトラックバックする(FC2ブログユーザー)

Open 2010 Algorithm Round 3 参加記録 (この記事を編集する[管理者用])

2010年07月11日01時02分から.

Assignment

Round 3にもなると,赤と黄色しかいない部屋になったりするのかぁ.
でも,まだ,赤の比率の方が低い.

EASY

2~maxNumの間にある素数をエラトステネスの篩で求めようとしたとき,一番最後に消される合成数を求める問題.
maxNumは20億以下.

うーん,Round 3とか,普段より難しいはずだし,慎重にじっくりやれ.
合成数だけど,素因数分解したとき,最小の素数が最も大きいもの.
その中で,相方の素数が最も大きいものを返せば良い.(!?)
エラトステネスの篩で,√20億ぐらいまで素数作って,2乗がmaxNumを超えない最大の素数を持ってきて,
もう1個の素数は,適当に,かけてmaxNumを超えないように最大のを取ってくる.
サンプル合う.サブミット.
ちょっと,見直す…,サンプルに境界ケースがない.
怖いなぁ…,等号忘れてないかなぁ….
いろいろテストする,大丈夫そう.
summaryみると,resubmitしてる人がいる.サンプルに境界無いからなぁ.
ん…,petrがresubmitしてる?…,え,そういう問題じゃなくてなんかへんなケースあるのか?
うーん,わからない,でも,多分合ってるでしょ,次の問題行こう.

MEDIUM

50人以下の人の初期位置と,それぞれの目的位置が与えられる.
それぞれはワープできて,別の人と同じ位置に一瞬で移動できる.
ただし,ワープは,順番にやらないと駄目で,2人の位置を入れ替えることは出来ない.
ただ,ワープする間隔はどんなに短くても良い.
全員歩く速度は1.
全員が目的地につくまでの最小時間を求める問題.

EASYはシンプルだったのに,こっちは問題文長いよ….
うーん,わからんけど,二分探索の香り.
テレポートは取り敢えず,一番最初にすれば良いよね.その後,移動できるんだから….
時間Tが与えられて,その時間で全員が目的地に付けるかどうかを判定する方法を考えよう.
テレポートせずに移動できる人の集合を決めて,その他の人は,動かなかった人の場所にテレポートして移動できるようになるか調べる.
これでいいのでは….
書いてみる.
サンプルが合わない.
あー,そうか.
テレポートせずに辿りつける人の集合から初めて,その他の人は,すでに辿り着くことが出来る人の初期位置にテレポートして,辿りつけるなら,辿りつける人の集合に入れる.
これを繰り返せば良いのでは.
うー,1個だけサンプル合わない.
ちゃんとサンプルの例を紙に書いて検証してみる.
なんと!
テレポートしなくてもいい人がテレポートしないと上手くいかない!
こんな感じもあるのか….
うーん?
もしかして,これって….
全員の初期位置が移動してないか,どこか1箇所以上,初期位置を使わない場所があれば,全員自由な位置から出発できるのでは….
証明できるか?
証明できた.
書く.
使わない場所でループ回して,各々の人が,一番近い場所からスタートすれば良い.
(後で思えば,それだと2分探索要らなかったのでは…)
サンプル通った.サブミット.

HARD

アルファベットと数字からなるN文字の文字列のうち以下の条件を満たす物の数をmod 1000000009で求める問題.
 小文字アルファベットを少なくてもL文字含む
 大文字アルファベットを少なくてもU文字含む
 数字を少なくてもD文字含む
Nは200000以下.

あれ?簡単じゃないの?こんなのすぐ計算できそうだけど.
しかも,O(N)でもOK.
あ,コンビネーション計算したいから,N小さめなのかな….
えーと,O(N)が許されるんだから,小文字アルファベットの文字数で場合分けしよう….
いや,対称性考えると,数字の文字数で場合分けしようか….
えっと,後は,
 E = C(n,st) + C(n,st+1) + ... + C(n,ed)
みたいなのをO(1)で計算できれば良い….
できないじゃん….
うわー.
いや,前の結果が使えるのでは…?
前計算したのは,
 D = C(n-1,st) + C(n-1,st+1) + ... + C(n-1,ed-1)
だから,コンビネーションの漸化式使うと…
 E = 2*D + C(n-1,st-1) + C(C-1,ed)
となる!
できた.
書く.
合わない….
あれぇ….
添字が1個違った….
サンプル合った.
サブミット.

Intermission

そういえば,250って,素数の積でいいの?
良さそうだけど….
証明してみよう….
あれ,….証明できなくないか….
ってか,8のとき,答え8だよ…!?
自分のコードを試してみる,6が返ってくる,死んだ.
あー,結構良い順位だったのに….

Challenge

250で他に素数の積に限定してる人いないかな…?
いた!撃墜.
この人も,素数×素数を返している.と思ったら素数判定が妙な素数判定でちゃんとしていた.失敗.
素数×素数っぽい.撃墜.
以下略.
9成功1失敗で+425点…,ぇ.

System tests

MEDIUMとHARDは通った.
部屋の人は,ちゃんと判定してる人も,素数×素数に限定してる人がいると思ってなかったらしく,チャレンジして無かった.
部屋割りが良かったなぁ….
ってことで,人生2度目の勝利.

コメント

[C56]

ついにターゲットですか・・・おめでとうございます!><

[C57]

ありがとうございます!
  • 2010-07-11 09:16
  • rsujskf
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1403-f0289ff2
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。