Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

2010年01月04日21時から.

Assignment

今回は,250-500-1000の標準的問題セットか.
UTPCの優勝者と同じ部屋.

EASY

ところどころ?になってる文字列,hh:mm GMTopという形式で与えられるので,考えうる現在時刻を標準時に直した時,辞書順最小のものを答える問題.

Theシリーズきたー.登場人物も見覚えがあるぜ.
で,問題はめんどくさいなー.
でも,実装するだけだよな….どうやって実装しよう.
愚直に文字列,全パターン書き出して,マッチするのをチェックしていこう….
書いた.サブミット.
問題文に明確に書かれ過ぎてるけど,GMT-0がないのはチャレンジポイントだよね?

MEDIUM

六角格子で7マスある.
1~2Nまでの整数を2回以上使わないように適当にいれて,隣合うマスの差はNにならないようにする方法は何通りか?
回転して一致するのは同じとみなす.

DP?
うーん,DPでいけそう,書いてみよう.
がりがり.
答え合わないな….
デバッグ中.
もっとデバッグ.
もっともっとデバッグ.
ようやくあった….これはサンプル動けば大丈夫だろう….
いや,150の時の答え*6がオーバーフローしてないかチェックしないとダメだ!
してない.じゃ,大丈夫.サブミット.
コード書きながら考えると時間掛かっちゃうという典型的な罠に嵌った問題でした.
まぁ,あえてその罠に飛び込んだんだけど.

HARD

18*18の升目のところどころに駒がいる.
1ターンで1つの駒を指定して,1マスだけ上下左右に動かせる.
最初,i行目にk個の駒があったら,最終状態ではi列目にk個の駒がいなければいけない.
最小手数でいける最終状態のうち,辞書順最小のものを求めよ.

18だから,2^18くさい.本当か?
うーん,なんか,そういう方針だと思いつかないぞ.
取り敢えず,辞書順最小は置いといて,最小手数を求めるのはどうするんだ…?
フローじゃね?
うん,最小費用流で最小手数は求まるよね.
じゃ,1マスずつ確定させながら,n*n回だけ最小費用流を流せば良いんじゃないか?
書いてみる.
書けた.500で手間取ってたので残り5分ぐらいしかない….
もういいや,取り敢えず,サブミット.
計算時間あやしいよな…,最大ケースでテストしてみよう.
TLEだったorz
チャレンジ防止に,自明な場合は即座に解を返すことにしてリサブミット.残り10秒.
誰かに50点プレゼント….

Challenge

部屋内で,1000は自分以外提出してない.500はたぶん落ちないだろう.250のGMT-0狙い.
探す,いたっぽい,投げる成功.
後は他の人に取られた.
やっぱり,皆そこは狙うよなー.
地味に,自分の1000は落とされずに,しかも2回も防衛してる,おいおい….

System tests

EASYもMEDIUMも通った.良かった良かった.
結局HARDは提出した人のコード見ると皆,最小費用流してたけど,皆落ちました.
どうやるんだろう?最適化して速くすれば通るとかそういうレベルなのかな?
まだ確定してないけどRateは多分上がるはず.ていうか,皆Challenge強いな….

2010-01-04 23:15追記

writerが想像と違った!
これは騙されるだろう….
まぁ,確かに,らしくない問題セットだなーとはちょっと思ってたけど….

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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