Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

National Programming Contest of Bangladesh at SUST (この記事を編集する[管理者用])

2010年04月17日18時から5時間,9問.
[ Link ]

なんか全然通らない.これは酷い.

取り敢えず,Iを読む.
2点間のノードに移動方法が何個あるか全部与えられるので,有向グラフを復元する問題.
答えがあるのは保証されてる.
答えがあるならDAGなわけで,トポロジカルソートしてからgreedyに生成すれば良い.Accept.
DとFとGが解かれてるので,それからやる.
Dは答え見る限りGCDで割って足せば良さそう.提出.Accept.
Fは問題文がよくわからなかったので,Gを見る.
Gは点数求めてA,B,Cとかランク付けするだけの問題.やるだけ.Accept.
Fを読むと,1000個以下区間が与えられて,もっとも重なってるところは何個重なっているか?って問題っぽい.
ソートしてなぞるだけ.Accept.
適当にEを見る.
両者とも作れるのをDPで求めて,全体から引くだけ.
がりがり書く.Accept.
残り4時間強.ここまで5 Acceptで最終結果も5 Accept.
Cをやる.
問題文見る限り,10^12以下のKが与えられるので,GCD(A,B)=1でAB=Kとなるもののうち,
 Bが1以上,A-Bが最大
のものを求めよ,と書いてあるような気がする.
でも,問題文が曖昧でよく分からない.
Kをp1^q1 * p2^q2 * …と素因数分解して,一番小さいpk^qkをBにすればいいんじゃないの?
なにか素数のベキの時は答えは無しで.
そんな感じで19 WA.
B問題.
面倒な六角格子をグラフに直したら探索問題っぽい.
20ステップがりがり探索してみるとTLE.
両側探索してみる.TLE.
そんなこんなで7 TLE.
H問題.
mod pで連立一次方程式の解の数を求めれば良いのだよね.
じゃ,行列のランク求めれば一発なのでは.
って感じで,7 WA.
もうなんか意味がわからない.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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