Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM458 DIV1 参加記録 (この記事を編集する[管理者用])

2010年01月15日01時から.

Assignment

今回は,250-450-900の変則的問題セット.
450や900が簡単なんじゃなくて,250が難しいんじゃないの?
ちょっと酷い部屋.(褒め言葉的な意味で)

EASY

12個以下のボールがある.
衝突したら,向きが変わる.速度は1で一定.
最初の場所が与えられたとき,それぞれのボールが最初のどちら向きに移動してるか分からないとき,時間Tまでにボールが衝突する回数の期待値を求める問題.

2^12通りを全部やるんだろうなぁ….
シミュレーションするの?そんな馬鹿な….
簡単なはずだ.
…よくわからなくなったので,悩んでいる暇があったらシミュレーション書こう….
書いた,サブミット.

MEDIUM

コインの価値は,自分より1つ価値の整数倍でなければいけない.
コインの価値を自由に決めれるとき,50個以下の品物を買うために必要なコインの数の最小値を求めよ.
品物の値段は100000以下.

わからん,方針が立たない….
400点台とかでサブミットしている人がいるなあ…,やっぱり450点だけあって閃けば一瞬何だろうか?
取り敢えず,全探索でもしてみれば?
最初のコインの価値を決めて,そのコイン以下の価値の品物は買い方決まるので,最も高い品物より高いコインを作った時点で打ち切り.
素数倍だけ作っていけば良いよね….
取り敢えず,書いてみたけども…,サンプルも通るけども….
ランダム最大を作って走らせると当然のごとくTLE.
うーん?
価値kのコインを作ったら,全ての品物の価値をkで割って,余りは1のコインで買わなくてはいけない!これを繰り返す.
こういう探索なら終わるんじゃないの?
書いてみた.ランダム最大で0.1秒ぐらい,大丈夫そう.サブミット.
サブミット後,少し考えると,この探索メモ化できる,ってかDPじゃん….
でも,間に合いそうだし,これでいいや.

HARD

0以上,10^18以下の4つの整数,a, b, c, dが与えられたとき,
 Nの約数で,4で割った余りが0のものがちょうどa個
 Nの約数で,4で割った余りが1のものがちょうどb個
 Nの約数で,4で割った余りが2のものがちょうどc個
 Nの約数で,4で割った余りが3のものがちょうどd個
となるようなNが存在するかどうかを判定してください.
ただし,これを50^4回やってください.

素因数分解したとき…,を考えて,a, b, c, dの間に成り立たないといけない条件を書きだして,それを愚直に実装すれば良い?
うーん…,書きだす,書きだす.
こんなもんじゃね?→サブミット.
やっぱりこの条件も必要だった→リサブミット.
この条件間違ってるよ→リサブミット.
結局合ってるのか良くわからんまま時間切れ.

Challenge

450のTLE狙いかなぁ?
と思って開いてみる.
900が怒濤の勢いで落とされていく…,そりゃそうだ,そっち考えておけばよかった.自分のも落とされた.
1人だけ残った人の900を読んでちゃんと考える.
なるほど…,合ってそうだ….
結局落とせそうなのは見つからず.

System tests

EASYとMEDIUM通った…,良かった.
ってか,同じ部屋の人は1つもシステムで落ちてる人はいなかった….
そして,終わってから気づく,あれ,サンプル58じゃん….
Rateは横ばい.

EASYで,すれ違えば良いことに気づかなかったのがおかしい….
てか同じ問題2回位解いただろ,蟻の問題だよ!
全体的に駄目駄目な結果でした.
が,問題自体がとても面白かったので,楽しかったー.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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