Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

One more National Programming Contest 2010 (この記事を編集する[管理者用])

2010年09月04日18時から7時間30分,12問.
[ Link ]

サーバートラブルで最初1時間30分ほど繋がりにくい状態が続いて,時間が6時間から7.5時間にのびた.
BとE以外の10問解いた.
以下解いた順番.

・問題G
やるだけ.コストの小さい方から買って行けば良い.
と思ったらWA.みんな通ってないみたいなので放置してたら,そのうちrejudgeされた.
・問題J
やるだけ.2重ループ+実際にGCDを求める.
・問題D
やるだけ.多倍長整数を使ってごりごり書いた.
末尾の0を削り忘れたり色々して嵌ってた.
・問題F
最初DAGであることを見落としてた.
DAGだとわかったら最小費用流を流すだけ.
・問題H
ビットDP.
for(j=i;j>=0;j=(j-1)&i)を初めて使ってみた.
サイズがちょっと大きいので,枝刈らないと微妙かと思ったけど,何もせずに間に合った.
・問題A
ゲーム.メモ化して探索する.
・問題K
最初に愚直に1ケースあたりO(NK)のDPを書いてTLEもらって放置してた問題.
2文字の組で見てあげて,同じ文字の組がa個,違う文字の組がb個あるとしたら,
0~aまでのループと0~bまでの2重ループで組み合わせの数を計算すれば解けるはず.
実際には,0~bまでのループは,残りの変えて良い文字の数を状態に加えてDPして,全テストケースで使いまわした.
するとテストケースの数がTとして全ケース合計でO(TN+KN)で解ける.
・問題I
なんだかんだで2時間かかった.最初は問題を読み間違えてた.
普通にDPするだけなんだけど,ループがあるので
 dp[n][0] = x (dp[n][1] + 1) + s
 dp[n][1] = x dp[n][0] + t
を解いてあげて解決する.
ここで手をぬこうとするとオーダーが上がってTLEになる.というか,なった.
・問題L
バイナリサーチで求めた.
・問題C
DP + 経路復元するだけのはずなんだけどWAをもらう.
なんでかなと色々調べてたら,どうやら,行頭に無駄なスペースが入ってるらしい.
ので取り除くとPresentation Error.
どうやら余分に空白を出力しなければいけないらしい….
・問題E (通してない)
たぶん毎行の遷移行列を書いてあげてかけていくだけ.
ブロックがない場所は遷移行列が同じなので,その部分は高速冪乗してまとめて処理する.
最後20分でとりあえず書いたけどバグって動かず.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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