Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

ZOJ Monthly, September 2010 (この記事を編集する[管理者用])

2010年09月04日13時から5時間,10問.
[ Link ]

同じ日の18時からUVaであるコンテストの前哨戦みたいな感じで参加.
6問解いた.
以下解いた順番.

・問題J
小さい値だけメモ化しても大丈夫かと思ったけどテストケースの数が多くてTLE.
ちゃんと,素因数分解して,指数の値にのみ,しかも順番によらないので,それをソートしてメモ化したら通った.
・問題A
T字みたいな感じになるので,ノードkから3点のノードまでの距離の和を全部求めて,kを動かして最小値を取れば良い.
ノード数500なのでワーシャルフロイドして大丈夫か少し悩んだけど大丈夫だった.
クエリの数が少なかったので,毎回3点からダイクストラする方が良かった気もする.
・問題H
やるだけ.
閏年で追加されたのは別計算.後は12年での日付は分かっているので,それをまとめて処理する.
132年で1単位に思っても良かったかもしれない.
最初の日付の方が時間的に後のことがあるという,超古典的な引掛けに1回やられた….
・問題F
やるだけ.これはやるだけ.
・問題G
時間ごとに遷移行列を求めてやって,かけていく.
高々,周期がLCM(1,2,3,4,5,6)なので,tが大きい時は高速冪乗を使う.
行列のサイズが微妙に大きめだけど,答えはlong longに収まり,modを取ったりしなくていいので十分間に合う.
最初,行列をかける方向が逆でちょっとはまった.
この問題を解いてる人が地味に少ないのが謎.
・問題B
最初,不可能な場合があるとか,実は大してステップ数必要ないんじゃないか,と思ってはまってた.
よく考えると,ハノイの塔みたいな感じ.
再帰的にスコアの小さい人を動かすために,その上のスコアの人をどこに動かせばいいかってのを書いていく.
が,愚直に1ステップずつ動かすとTLEなので,adhocにメモ化した.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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