Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM446 DIV1 (この記事を編集する[管理者用])

2009年08月09日01時から.

Links
Match Overview
Match Editorial
Summary of Japanese (otinn.com)
参加記録 (blog)

右を向く,左を向く,前に一歩進むというコマンド列が与えられるので,
図に書かれたようなルービックキューブ上をその通りに歩く.
最後にいるマスの色を求める問題.

色が対称に入っているので,最後に座標をmod 3するだけで良い.

ノード数50以下で枝にはコストが設定されている.
t*stepsPerSecond (t=1,2,...,timeLimit) ステップでノード0から1に移動したい.
コストの和を最大化する問題.
timeLimitは10^9以下,stepsPerSecondは100以下.

行列をstepsPerSecond乗して,stepsPerSecondステップを1ステップと見立てたグラフを作る.
後は,コスト0でループできるようにして,その行列をtimeLimit乗したら答えが出てくる.

一部分色が塗られていないルービックキューブがある.
色が塗られていない部分を,閉ループに分割する仕方の数をmod 1000000007で求める問題.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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