Entries

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

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

Marathon Match 59 - BookSelection (参加記録) (この記事を編集する[管理者用])

2010年04月15日02時から,2週間.

Source

Problem Statement
standings

問題概要

本棚が1つ,本がたくさん与えられる.
本棚は高さ,幅が与えられ,本には,高さ,幅,価値が与えられる.
本棚に入れれる本の価値の合計を最大化する問題.入れ方を答える.
本棚に本を入れる際には,まず高さ10の仕切りを入れなくてはいけない.
仕切りの入れる場所,入れる数は自由.
本棚の高さは240以上1200以下で,幅は2400以上6000以下.
本の高さは平均80,幅は平均200でぐらい.
本の数は,本棚の面積/(80*200)の値の1倍~3倍ぐらい.最大ケースで1350で,平均200冊ぐらい?

自分の解法

以下のアルゴリズムを制限時間の間繰り返す.
1. 本をランダムに並べ替える
2. 最初のn冊の本は,小さい順に並び変えて,greedyに本棚に入れると全部入れることができる.というようなnの最大値を2分探索で求める.
3. その時の入れ方から,各段の高さ(仕切りの位置)を決める.ただし,余っている余白は,
   その余白がある程度大きいとき,余白だけでもう1段作る
   その余白がそんなに大きくないとき,全部の段に余白を均等に割りふる.
4. 本は全部入れてない状態に戻す.
5. 一番小さい高さの段に入れる本の価値が最大になるような入れ方をDPを使って求める.
6. まだ入れてない本だけ使って,2番目に小さい高さの段に入れる本の価値が最大になるような入れ方をDPで求める.
7. 同じことを3段目,4段目,…と入れて,それが暫定解より良いなら更新する.

自分の提出したソースコードはこの記事の一番下に貼りつけておきます.

サンプルテストの結果.(提出したコードと違うかもしれません)

Example scores:
0) 3145.0
1) 3470.0
2) 8040.0
3) 1803.0
4) 2239.0
5) 2601.0
6) 2287.0
7) 2851.0
8) 1444.0
9) 4195.0
参加記録

以下時系列順のログです.

続きを読む

Beta Round #11 (参加記録) (この記事を編集する[管理者用])

2010年04月27日00時から2時間,5問.
[ Link ]

A. Increasing Sequence

要素数2000以下の整数列と正整数dが与えられる.
1回の操作で1つの要素を選んでd加えることができる.
数列をstrictly単調増加列にするための最小ステップ数を求める問題.

なんか開始と同時に繋がらなくなった.
2~3分たつと繋がってた.焦る.
うっはー,codeforcesらしくなく問題文が簡潔.素敵すぎる.
普通に前から見て,増加してなければd足していくだけ.
Accept.

B. Jumping Jack

最初,数直線上の原点に居る.
時間tでは,左右どちらかにtだけジャンプする.
xにたどり着くまでの最小時間を求めよ.
xの絶対値は10^9以下.

うひょー,問題文がわかりやすい.
今日のcodeforcesは良いなー.
で,いきなり分からない…どうするんだ?
2分探索で,大きなステップからgreedyに向かっていけば良いのではないか…?
え,なんか違う気がする.
あ,わかったかも?
取り敢えず,ずっとxの方向に向かっていって,偶数距離だけ行き過ぎたら,適当に今までのステップを反転させればたどり着けるのでは!?
行けそう.書こう.
Accept.

C. How Many Squares?

01からなる250*250以下のグリッドが与えられる.
並行か,斜め45度のサイズ2以上の1からなる正方形の数を数える問題.
ただし,正方形は,その他の1に縦横斜めで接していてはいけない.

問題わかりやすー.いいよいいよー.
接してたら駄目なので,接している一連なりの1を持ってきて,それが正方形かどうか逐次判定していけば良い.
正方形は,1の数が4*(一辺の長さ-1)なので,1の数でサイズを判定して,調べれば良い.
よし,行けそう.書くだけ.
Accept.

D. A Simple Task

ノード数19以下の無向グラフが与えられるので,単純閉路の数を求める問題.

なんか,ここまで問題文がわかりやすいとcodeforcesじゃない気がしてきた.
いつもなら,D問題から難しいが…,なんか普通にDPじゃない?
いや,よく考えるんだ…!
始点がどこか,今までどのノードを通ったか,今どのノードにいるか,でDPして,
長さnの閉路は,始点,どちら周りかで,2n回カウントされるので,それで割れば良い.
と思ったんだけど,これって,計算時間量O(n^3 2^n)だよね…,間に合わないんじゃない?
実行時間制限3秒か…どうだろう.
まぁ,取り敢えず書いてみようか.
書いてみた.答え合った.
さて,ノード数19の完全グラフを食わせてみるか.
8秒かかる…,これはたぶん駄目じゃないかな…orz
さぁ,どうしよう….
….
….
わからん.
取り敢えず,ビット演算使って小手先の高速化.
4秒ぐらいになった.たぶん駄目.
うーん….
あ,そうだ!
ノード1から始まる閉路の数をカウントしたら,ノード1を消して,ノード数を1つ減らして,ノード2から始まる閉路を数えてみたらどうだろう?
段々ノード数が減るので,計算時間は早くなるはず.
ついでに,最後に閉路長で割らなくてもいいし,些細すぎることだけど.
やってみる.
1.5秒になった!
あれ,これならいけるんじゃない?
サブミット.Accept.

E. Forward, march!

LRXからなる10^6以下の文字列が与えられる.
それにXを適当に挿入して良い.
そして,LまたはRが連続して同じ文字が2回以上現れないようにする.
そして,それを周期的に無限に長い文字列にして,それとLRLRLRLRLRLRLRLR…という文字列とどの位同じ場所に同じ文字が来ているかを調べる.
その割合の最大値を求める問題.

あれ,なんか,問題文読みにくいよ.ちょっと最後だけいつものcodeforcesっぽくなった.
これ,RLRLRLRLでも良いのかな…?
まぁ,よく解らんけど,解き方考える方が先だ.
うーん.
まず,RRとかLLの間にはXを入れよう.
後は,RとLだけ見て,LRLRL…にマッチしているかどうかを調べる.
連続してマッチしている数,連続してマッチしていない数,連続してマッチしている数,…を数列として保存.
後は,その数列の偶数番目のみの和/全体の長さ,がLRLRLR…とマッチしている割合.
と思ったけど,全部の長さが奇数の時はそうじゃないな.
奇数の時は,LRの数だけで決まる.
ても,本質的には,偶数の時だけ考えれば良いのではなかろうか?
できる操作は,全体の長さを+1して,数列に0という要素を足すこと.
もしくは,全体の長さを+2して,奇数番目のものも拾ってあげれるようにできると考えても良い?
いや,それだけじゃないな,それが最適じゃない場合もあるはず.
 3 1 5 1 6 → 1+1
だったのを
 0 3 1 5 1 6 → 3+5+6
にするとか.1は小さいので無視した方が良い場合もありそう.
んー,これ,長さ10^6もあるし,2乗じゃ時間的に駄目なんだよなぁ.
コーナーケースもありそうだし…,よくわからない.
諦めた.

Result

今回は4問目まで簡単だった.でも,5問目が難しい.
問題文が読みやすかったこともあって,4問目までスムーズに解けたので結構良い順位.

Smartmatic CONNECT IV (この記事を編集する[管理者用])

2010年04月25日02時30分から4時間,6問.
[ Link ]

なんか,最初1時半からって書いてたのに,気づけば30分延長してて,また気づけば30分延長してた.
なんか最近ケアレスミスが酷い.
どうしたものか…,問題をちゃんと読め,そして,コードを慎重に書け.
一応2時間42分ぐらいで,6問全完.
BGMをデートコースのいちゃぷりOPとゆいにゃんのすきッスSTE(ryを2曲で永遠とリピートするという素敵なことをしてみる.

A. Miles 2 Km

n=fib[i]+fib[j]+…と分解する.
1.6n と fib[i+1]+fib[j+1]+…
の差の絶対値を最小化したい.差の絶対値の最小値を求める問題.
fibはフィボナッチ数列.
nは1000以下.

DPでやるだけすぎる….
状態は,nとfib[i+1]+…で,取りうることができるかどうかのbool値の配列.
だけど,dp[1000][1600+α]ぐらいは必要なので,結構厳しい?
と思ったけど,そんなこともなくて,使えるfibは20個ぐらいしかなくて,最初に1回計算しただけで全部答えは求まるし大丈夫.
サクっと書いてサブミット.Accept.

F. Hypercube

ノード数K,枝数Mのグラフが与えられる.
Hypercubeなグラフとは以下の条件をみたすものである.
・ノード数が2^nで,各ノードは0から2^n-1の番号がつけられている
・2ノードの番号を2進数で表したとき,1桁のみ違う場合にのみ,その2ノード間に枝がはられている
与えられたグラフがHypercubeなグラフかどうかを判定する問題.
Kは2^10以下.

解いていた人がいるのでFを読む.
すっごいやるだけ.
実際に,Hypercubeなグラフを作って,枝が全部対応してるかどうか調べた.
サクっと書いて提出.Accept.

C. Optimal Cut

高さHの完全2分木が与えられる.
カットとは,ノードの集合で,始点から各葉にたどり着くまでに,カットに属するノードにちょうど1回だけぶつかるようなもの.
ノードに重みが与えられたとき,カットの重みはカットに含まれるノードの重みの和.
サイズK以下のカットで,重みが最大のものの重みを求める問題.
Hは19以下,Kは20以下.

下(葉)から順番に計算して行くDPだよね.
ノード数が2^20ぐらいあって,O(2^20 * K^2)とかになるのだけど,大丈夫だろうか….
まぁ,大丈夫に違いない,書いてみる.
サブミット,WA.
時間は全然大丈夫そうだった.が,WAってなんだ….
カットサイズがちょうどKじゃないと駄目だと思ってた.K以下で良かった!
修正.Accept.

D. Nails

二次元平面上に線分が1000個以下ある.
3本以上の線分が1点で交わっていることはないし,線分がぴったり重なっていることも無い.
線分同士の交点を釘で打つ.
どの線分とも交わっていない線分は,その線分の両端を釘で打つ.
必要な釘の数を求める問題.

解いている人が居るし,順番通りDを読む.
2次元幾何,やるだけっぽい.
ライブラリコピペ,ぽちぽち,がりがり.
書いた.提出.TLE.
明らかに交わらない線分同士の判定はちゃんと計算しないようにしてみる.TLE.
何が重いのか…,全部doubleで計算してるからか….
2つの線分の端点4点が,一直線上にある場合は考えないことにしてみる.
これで取り敢えずまだTLE食らうかWAになるか試してみる.Accept.あれ?
まぁ,いいやw

E. Escape

壁に囲まれた部屋で,何か所か穴があいていて,そこから脱出したい.
一度,上下左右の4方向の何処かに向かって移動し始めたら,方向転換できないし止まれない.
壁はぐるぐる回っている.
脱出できるまでの最短時間を求める,また,その最短時間で脱出できる最短距離を求める問題.
部屋のサイズは1000*1000以下,障害物などはない.

毎時間壁を回しながら,穴までの距離を求めて,辿り着けるかどうか判定.
回る処理を頑張って書くだけ.
サブミット.WA.
あ,方向転換できないってのを読み飛ばしていた.
さくさく修正.
サブミット.WA.
うーん?
穴の数の最大値は4000ぐらい…,配列のサイズは2000,足りてねぇorz
サブミット.Accept.

B. Books

幅30以下,高さ30以下の同じサイズの本棚が10個以下あります.
本が100冊以下あります.
奥行きは考えない,本は重ねない,横に倒さない,で,もっとも多くの面積を詰め込みたい.
最終的に,本棚で本の入ってない部分の面積を求める問題.

どう考えても無理ゲー.
適当に枝刈り探索をサブミット.TLE.
ランダム化して,適当に打ち切って,1000回ぐらいリスタートさせてみる.WA.
色々ヒューリスティックスを考えて試して(送って)みる.
12 rejectsの後, Accept.
勿論最適解が出る保証なんてないコードです.

SRM468 DIV2 HARD - Gifts (この記事を編集する[管理者用])

Source

TopCoder SRM468 DIV2 HARD (1000pt)
Problem Statement

問題概要

50*50のグリッドで,初期位置と最終位置が与えられる.
また,16個以下のアイテムの位置が与えられる.
アイテムをできるだけたくさん拾って最終位置まで制限時間内にたどり着きたい.
1マス移動するのにかかる時間は,拾ったアイテムの数 + 1だけかかる.
アイテムの上を通ってもアイテムを拾わないとか,ゴールに一度たどり着いたけど,またどこかへいくというのは可能.
拾えるアイテムの個数の最大値を求める問題.

解法

まず,初期位置,最終位置,アイテムの位置間の距離をBFSとかで求めておく.
後は,循環セールスマン問題みたいな感じでビットDPする.

C++によるスパゲッティなソースコード

続きを読む

SRM468 DIV2 EASY - RoadOrFlightEasy (この記事を編集する[管理者用])

Source

TopCoder SRM468 DIV2 EASY (250pt)
Problem Statement

問題概要

街がN+1個ある.
街iからi+1に行くのに,陸路と飛行機のどちらかで行くことができて,それぞれでかかる時間が与えられる.
飛行機に乗れるのは,K回までで,街0からNに移動する最小時間を求める問題.
Nは50以下.

解法

各区間で,飛行機を使うと,どれだけ速くなるかを調べて,それが大きい方から飛行機を使う.

C++によるスパゲッティなソースコード

続きを読む

SRM468 DIV1 HARD - MallSecurity (この記事を編集する[管理者用])

Source

TopCoder SRM468 DIV1 HARD (1000pt)
Problem Statement
SRM 468 自分の参加記録

問題概要

100ノード以下のグラフが与えられる.
各ノードはN種類に分類されていて,種類i%Nのノードと種類(i+1)%Nのノードしか枝が張られていない.
ノードを白黒のどっちかでぬるんだけど,黒いノードは隣接しててはいけない.
黒いノードの最大数を求める問題.
Nは10以上,50以下.

解法

一番ノード数の少ない種類を探して,そのノードに関しては白か黒か,全探索する.
全探索するノード数は最大でも10個.Nが10以上だから.
そうすると,残りは,奇数番目の種類のノードと偶数番目の種類のノードに分けることで2分グラフになる.
2分グラフなので,答えは ノード数 - 最大マッチング なので最大流を流すなどすれば良い.

また,制限時間いっぱい,ランダムに塗りまくって最大値を返すって方法でもシステムテストは通りました.
チャレンジされると落ちるかもしれません.
以下のコードはそれです.

C++によるスパゲッティなソースコード

続きを読む

SRM468 DIV1 MEDIUM - RoadOrFlightHard (この記事を編集する[管理者用])

Source

TopCoder SRM468 DIV1 MEDIUM (500pt)
Problem Statement
SRM 468 自分の参加記録

問題概要

街がN+1個ある.
街iからi+1に行くのに,陸路と飛行機でかかる時間が与えられる.
飛行機は,2つ以上の街を飛び越えれるが,順番に移動したのと同じ時間がかかる.
飛行機に乗れるのは,K回までで,街0からNに移動する最小時間を求める問題.
Nは400000以下,Kは40以下.

解法

DP.今何処にいるか,飛んでいるかどうか,を状態とする.
状態分メモリ確保するとメモリが足りないので,うまく使いまわす.

C++によるスパゲッティなソースコード

続きを読む

SRM468 DIV1 EASY/DIV2 MEDIUM - T9 (この記事を編集する[管理者用])

Source

TopCoder SRM468 DIV1 EASY (250pt)
TopCoder SRM468 DIV2 MEDIUM (500pt)
Problem Statement
SRM 468 自分の参加記録

問題概要

携帯電話で文字入力.
アルファベット26文字を1~9の数字に割り振っておく.
また,単語の辞書が与えられる.
単語か空文字をスペースで区切った文字を入力したい.
スペースは0で入力するとして,各単語は,対応する数字の列+#か*を何回か,という形式.
数字の列に対応する,辞書内の単語のうち,辞書順で#の回数+*の回数×5番目のものを入力したとする.
辞書と,打ったキーが与えられるので,打った文字を出力する問題.

解法

やるだけ.問題文読解+実装ゲー.

C++によるスパゲッティなソースコード

続きを読む

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

2010年04月20日20時02分から.

Assignment

部屋割りが時間内に終わらないかもしれないから,開始時間2分延長するね,ってわりには普通に終わりました.

EASY

携帯電話で文字入力.
アルファベット26文字を1~9の数字に割り振っておく.
また,単語の辞書が与えられる.
単語か空文字をスペースで区切った文字を入力したい.
スペースは0で入力するとして,各単語は,対応する数字の列+#か*を何回か,という形式.
数字の列に対応する,辞書内の単語のうち,辞書順で#の回数+*の回数×5番目のものを入力したとする.
辞書と,打ったキーが与えられるので,打った文字を出力する問題.

問題文長いよ….
でも,読みにくくはない…,が読むのに時間かかるなぁ.
なんとか理解した.実装するだけ問題.
そして,実装もそれなりに重たいなぁ….
時間かかるなぁ….
実装完了.動いた.サブミット.
invalidなキー入力のテストケース入れて,ちゃんとinvalidって返してくれることを確認する.
まぁ,これは,サンプル通れば流石に大丈夫でしょ,次行こう.

MEDIUM

街がN+1個ある.
街iからi+1に行くのに,陸路と飛行機でかかる時間が与えられる.
飛行機は,2つ以上の街を飛び越えれるが,順番に移動したのと同じ時間がかかる.
飛行機に乗れるのは,K回までで,街0からNに移動する最小時間を求める問題.
Nは400000以下,Kは40以下.

DP…!
ただし,飛行機で一気に飛ぶのはちょっと考えないといけない….
segment treeでMRQでやればOK?
いや,そんなことしなくても,今までの(各場所から今にたどり着くまでの飛行機でかかる時間)の最小値を覚えておくだけでOK!
書くだけだ.最近の500はやっぱり簡単なのにしようという傾向なのかな.
んー,もしかして,long long dp[400001][41];ってメモリ大丈夫か?
ちょっと,アリーナで試してみる.駄目だ!
long long dp[41], next[41];と配列2つ作って頑張る….
書いた.通らない.
DP表を書き出してみる….明らかにおかしい.てか最初のステップからおかしい.
乱数で作るところ,最初の項はmodとらないといけないのに,取ってなかった!
直す.通った.
N=400000, K=40で時間大丈夫か?
0.2秒ぐらい大丈夫.
じゃ,サブミット.

HARD

100ノード以下のグラフが与えられる.
各ノードはN種類に分類されていて,種類i%Nのノードと種類(i+1)%Nのノードしか枝が張られていない.
ノードを白黒のどっちかでぬるんだけど,黒いノードは隣接しててはいけない.
黒いノードの最大数を求める問題.
Nは10以上,50以下.

NP完全?
いや,グラフがループしている構造に秘密があるはずだ.
んー?
一列だけ,全探索すれば,ループじゃなくなる.
しかも,最も少ないノードの列を選べば,最大でも10個しかノードはない.
Nが無意味に10以上とか,これが原因では? ここまではあってるに違いない.
じゃ,残りはどうするか?
木になってればgreedyに塗れる…,がループあるよな….
最大流…,も違うか?
よくわからん.
残り時間がなくなってきた.
てか,UVaでこんな感じの問題あった時,ランダムに適当に塗ったら通ったよなぁ.
制限時間内だけ,ランダムに塗りまくるプログラムでも書くか….
うごごごごごご…,書いた.
通らない.
てか,ノード数が違うぜ.何か,根本的にミスってるな.
コーディングフェイズ終了2分後にくだらないミス発見して書き上がった.
これ万が一通ったら泣けるな….
てか,皆HARD提出してるな,これ簡単なの?orz

Challenge

500のMLEを狙う….
誰もいねぇ….
流石に皆最大ケースぐらいチェックしてるか.
何もできず.

System tests

250と500は通る.しかし1000解いている人が多いorz
後で試してみたら,1000はランダムでシステムテスト通る!!
これは鬱すぎる….もっと早めに諦めて方針転換してたら….
というか,グラフを折り返したら2分グラフになることぐらい気づこうよorz

UVa 11773 - King's Wish (この記事を編集する[管理者用])

Source

National Programming Contest of Bangladesh at SUST (2010-04-17) (blog)
UVa 11773

問題概要

10^12以下の正整数Kが与えられる.
K*Kの床をタイルで敷き詰めたいのだけど,タイルのサイズをW*Lとして,最適なサイズを求める問題.
最適とは,
 K > L > W を満たす
 L*Wのタイルで,K未満の正方形の床は敷き詰められない
 L-Wを最大にする.それでも複数あればLとWの大きい方

解法

要するに,LCM(L,W)=KでL-Wを最大化する問題.
 K = p1^q1 * p2^q2 * … pn^qn
と素因数分解したとき,LとWの候補は
 L = K / pi, W = pi^qi
となる.

UVa 11779 - Lost File (この記事を編集する[管理者用])

Source

National Programming Contest of Bangladesh at SUST (2010-04-17) (blog)
UVa 11779

問題概要

2ノード間に移動方法が何個あるか全部与えられるので,有向グラフを復元する問題.
ノードの数は50以下.答えがあることは保証されてる.

解法

答えが存在することから,DAGになるはずなので,トポロジカルソートする.
後は,適当にgreedyに復元すれば良い.

UVa 11778 - Graph Coloring in HSL (この記事を編集する[管理者用])

Source

National Programming Contest of Bangladesh at SUST (2010-04-17) (blog)
UVa 11778

問題概要

ノード数100以下のグラフが与えられる.
各ノードに0以上p-1以下の数字を割り振るのだけど,各ノードの数字は,そのノードと隣接するノードの和 mod pになっている.
そのような数字の割り振り方の数をmod 1000000007で求める問題.
pは素数.

解法

体Z/pZ上で連立一次方程式の解の数を求めれば良いことになる.
なので,行列のランクを求めれば良い.

UVa 11777 - Automate the Grades (この記事を編集する[管理者用])

Source

National Programming Contest of Bangladesh at SUST (2010-04-17) (blog)
UVa 11777

問題概要

試験7種類の点数が与えられる.
最後の3種類の試験は,良いもの2つの平均値を点数として,合計点が幾らかによってランクづけする問題.

解法

やるだけ.

UVa 11776 - Oh Your Royal Greediness! (この記事を編集する[管理者用])

Source

National Programming Contest of Bangladesh at SUST (2010-04-17) (blog)
UVa 11776

問題概要

区間が1000個以下与えられるので,最も多く重なっている場所の区間の数を求める問題.

解法

区間[a,b]はa-EPSで+1,b+EPSで-1するという2つのイベントとして,時間でソートして,シミュレーションして,最大値を求める.

UVa 11775 - Unique Story (この記事を編集する[管理者用])

Source

National Programming Contest of Bangladesh at SUST (2010-04-17) (blog)
UVa 11775

問題概要

映画会社が持っている資源を繋ぎあわせて映画を作る.
ただし,持っている資源を使わないことは可能だけど,順番を入れ替えることは不可能.
例えば,
 A, B, C
という資源を持っていたら,
 A, B, C, AB, AC, BC, ABC
という7種類の映画を作れる.
2種類の映画会社が持っている資源が与えられる.
お互い,両方が作れるものは重なるのが怖いので,作らない.
作られる映画の種類数を mod 1000000007で求める問題.
それぞれ持ってる資源の数は1000個以下.

解法

両方作れる物の数をDPで求める.
後は,使う使わない2^種類数から両方作れるものを引けば良い.

UVa 11774 - Doom's Day (この記事を編集する[管理者用])

Source

National Programming Contest of Bangladesh at SUST (2010-04-17) (blog)
UVa 11774

問題概要

3^n行3^m列に数字が書かれている.
row majorで数字を読んで,その数字をcollumn majorで書いていく.
何回この操作を繰り返せば,最初の数字と一致するか求める問題.
nとmは10^9以下.

解法

(n+m)/gcd(n,m)

SRM467 DIV2 HARD - MazeOnFire (この記事を編集する[管理者用])

Source

TopCoder SRM467 DIV2 HARD (1000pt)
Problem Statement

問題概要

50*50以下の迷路で,上下左右に動ける.
最初幾つかの場所で,燃えていて,時間1経つごとに,上下左右に燃え広がる.壁はつきぬけない.
生き残れる最大ターン数を求める問題.

解法

各時間ごとに,自分の居れる場所,火の場所を計算してやるとO(50^4)程度で解ける.以下のコードはこれ.
自分の初期位置,火の初期位置からBFSして,そこに辿り着く時間を求めてやることで,O(50^2)で解けると思う.(自分と火のスピードは一緒なので,逃げてる途中で火に追いつかれないというのを使う)

C++によるスパゲッティなソースコード

続きを読む

SRM467 DIV2 EASY - ShorterSuperSum (この記事を編集する[管理者用])

Source

TopCoder SRM467 DIV2 EASY (250pt)
Problem Statement

問題概要

 S(0,n) = n
 S(k,n) = S(k-1,1) + S(k-1,2) + … S(k-1,N)
なので,S(k,n)を求める問題.kは14以下,nは14以下.

解法

DPしてもメモ化無しで再帰してもOK.

C++によるスパゲッティなソースコード

続きを読む

SRM467 DIV1 MEDIUM - SuperSum (この記事を編集する[管理者用])

Source

TopCoder SRM467 DIV1 MEDIUM (500pt)
Problem Statement
SRM 467 自分の参加記録

問題概要

 S(0,n) = n
 S(k,n) = S(k-1,1) + S(k-1,2) + … S(k-1,N)
なので,S(k,n) mod 1000000007を求める問題.kは50以下,nは10^9以下.

解法

よく見れば答えは二項係数.
mod 素数で割り算の仕方を知らない場合は,bigInteger使っても回避できる.
答えに気づかない場合は,
 S(k,n) = S(k-1,n) + S(k,n-1)
と対称なので,問題のようにkを1減らすのではなく,nを1減らす式にしてやって,行列冪乗で求めるとか,
kを固定すると,nについての多項式なので,その多項式の係数を連立一次方程式で求めるとか.
以下の本番でサブミットしたコードは多項式の係数を求めたもの.

C++によるスパゲッティなソースコード

続きを読む

SRM467 DIV1 EASY/DIV2 MEDIUM - LateProfessor (この記事を編集する[管理者用])

Source

TopCoder SRM467 DIV1 EASY (250pt)
TopCoder SRM467 DIV2 MEDIUM (500pt)
Problem Statement
SRM 467 自分の参加記録

問題概要

生徒は最初は時刻0に部屋に行って,以下の行動を繰り返す.
 WaitTimeだけ部屋にいる.区間の両端の時間は部屋にいる.
 その後,WalkTimeだけ部屋に居ない.
教授は時間bestArrivalからworstArrivalまでの中で一様分布にしたがって部屋に到着する.
教授が部屋に到着した瞬間から,そのlateTime未満後までの間に生徒がいればOK.
OKじゃない確率を求める問題.

解法

bestArrival=worstArrivalのときは例外処理する.
後は愚直にシミュレーションして求めていく.

C++によるスパゲッティなソースコード

続きを読む

Beta Round #10 C問題 - Digital Root (この記事を編集する[管理者用])

Source

Codeforces Beta Round #10 C問題
Problem description
Beta Round #10の自分の参加記録

問題概要

 d(a) = a, aが9以下
 d(a) = d(sum_of_digit(a)), aが10以上
でdを定める.AとBとCが1以上N以下で
 AB != C
 d(d(A)d(B)) == d(C)
を満たすものの数を求める問題.
Nは1000000以下.

解法

d(a) = a%9なので,9種類に分割して計算する.

C言語のスパゲッティなコード

続きを読む

Beta Round #10 B問題 - Cinema Cashier (この記事を編集する[管理者用])

Source

Codeforces Beta Round #10 B問題
Problem description
Beta Round #10の自分の参加記録

問題概要

映画館でk*kの席がある.
N人の人が到着したら,できるだけ真ん中で,一並びの席を用意する.
真ん中の基準は
 各席と真ん中の席までのマンハッタン距離の和
が最も小さい.
一並びの席が存在しないなら追い返す.
何人の人が到着したかのログが与えられるので,どの席に座るのかシミュレーションする問題.
kは100以下で奇数.

解法

書くだけ.愚直に書いても計算時間的には問題ない.

C言語のスパゲッティなコード

続きを読む

Beta Round #10 A問題 - Power Consumption Calculation (この記事を編集する[管理者用])

Source

Codeforces Beta Round #10 A問題
Problem description
Beta Round #10の自分の参加記録

問題概要

操作しないとPCが3段階に省電力モードに移行して行く.
移行するまでの時間と,それぞれのモードでの1分あたりの消費電力,PCを操作していた時間のログが与えられるので,合計消費電力を求める問題.

解法

書くだけ.

C言語のスパゲッティなコード

続きを読む

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.
もうなんか意味がわからない.

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

2010年04月16日10時から.

Assignment

なんか普通の部屋.感想が出てこない.

EASY

生徒は最初は時刻0に部屋に行って,以下の行動を繰り返す.
 WaitTimeだけ部屋にいる.区間の両端の時間は部屋にいる.
 その後,WalkTimeだけ部屋に居ない.
教授は時間bestTimeからworstTimeまでの中で一様分布にしたがって部屋に到着する.
教授が部屋に到着した瞬間から,そのlateTime未満後までの間に生徒がいればOK.
OKじゃない確率を求める問題.

問題文読みにくいー.
まぁ,こういう意味だよね….
制限小さいので愚直に全部回せば良いでしょ!
書いてみる.サンプル.合わない.
サンプルを手計算….あれ,答え違うぞ.
OKの確率を求めてたよ.駄目な確率を求める問題だった.
それでも合わない….
何を勘違いしたのか,出歩るき始めてから,lateTime未満に教授が到着したらOKにしてた.
違うじゃん,逆じゃん.
直す.サンプル通った.
境界だけテストする.大丈夫っぽい.サブミット.160点とか.時間かけすぎorz

MEDIUM

 S(0,n) = n
 S(k,n) = S(k-1,1) + S(k-1,2) + … S(k-1,N)
なので,S(k,n) mod 1000000007を求める問題.kは50以下,nは10^9以下.

問題文単純だ,嬉しい.
DPできんし,行列冪乗か?
小さい部分を紙に書いてみる.
S(k,n) = S(k-1,n) + S(k,n-1)だなぁ.
でも,DPは無理.行列冪乗っぽくもない.
てか,これって,S(k,n)ってkを固定した時って,nについてのk+1次の多項式とかそんなんだよね? ∑i^kはk+1次式なんだから.
小さいところだけDPして,多項式の係数を連立一次方程式で求めてやればいいのでは?
書いてみる.
書いた.サンプルは合う.
ライブラリをintからlong longに書き直したので,見直しする.
大丈夫そう.サブミット.

HARD

連続するN文字中,違い種類の文字はD種類までしか含まれてはいけない.
そんな文字列の中で,seedと同じ長さで,seedより辞書順でkだけ遅い文字列を求めよ.
seedは50文字以下,使える文字の種類はアルファベット小文字26種類のみ,kは10^18以下.

もう残り30分ぐらいしか無い.
これは…,すごい面倒なDPなんじゃないの…?
今見てる,連続するN文字が,どことどこが同じ文字か,最初の文字は何文字目かを状態としてDP.
ちょっと手抜きして実装.
残り5分.
実行してみる.Abort.
残り2分.
実行してみる.答え合わない.制限時間に間に合ってない気がする.
諦めた.

Challenge

250は境界条件で落ちる人いるはず.
特に,自分が歩き始めると同時に先生が到着するとOKにしなければいけないところ! (後で気づいたけどこれサンプルにあったのね)
探す!
500が2つ落ちた.え?そっち??
500を見てみる.nが10^9なのにDPしてる人がいる.おいおい.
他の人を見る.500は単純に2項係数である.
k=0とかk=-1とか足して,首を45度傾けると二項係数に見えた.死にたい.
250に戻る.
これは…間違ってるんじゃないかな?…と思ってたら他の人に落とされた.
次,これも間違ってるよね!
テストケース入力中に他の人に落とされたorz
これは…間違ってるんじゃないかな?
落ちなかったorz
-25点.

System tests

チャレンジ失敗が大きく響いてる….
と思ったら自分の250落ちた.うわー,変数1つ書き間違えてる.ていうか,アドホックに修正したとき直し忘れたな.
やっぱりこういうアドホックな修正は良くない.
問題文ちゃんと読んで,頭の中整理して,一発で書きたい…,なかなか難しいけど.
チャレンジ失敗はどうでも良くなった.
まぁ,朝方のSRMなので,調子悪くて当然ですね…orz

Beta Round #10 (参加記録) (この記事を編集する[管理者用])

2010年04月16日00時45分から2時間,5問.
[ Link ]

A. Power Consumption Calculation

操作しないとPCが3段階に省電力モードに移行して行く.
移行するまでの時間と,それぞれのモードでの1分あたりの消費電力,PCを操作していた時間のログが与えられるので,合計消費電力を求める問題.

すっごい書くだけ.
今回は問題もわかりやすいし,コーディングでミスるところもない.親切っぽい.
ってことで,書いてサブミット.Accept.

B. Cinema Cashier

映画館でk*kの席がある.
N人の人が到着したら,できるだけ真ん中で,一並びの席を用意する.
真ん中の基準は問題文に与えられてる式で定める.
一並びの席が存在しないなら追い返す.
何人の人が到着したかのログが与えられるので,どの席に座るのかシミュレーションする問題.
kは100以下で奇数.

すっごい書くだけ.
サイズが小さいので,本当に愚直に実装すれば良い.
書いた.サブミット.Accept.

C. Digital Root

 d(a) = a, aが9以下
 d(a) = d(sum_of_digit(a)), aが10以上
でdを定める.AとBとCが1以上N以下で
 AB != C
 d(d(A)d(B)) == d(C)
を満たすものの数を求める問題.
Nは1000000以下.

うーん,d(a)って基本的にa mod 9じゃないの?
あ,aが0のとき違うから,なんか違うかも.
何を勘違いしたか,d(a)=sum_of_digit(a)%9で良いんじゃないかと勘違い.いや,あってるけど.
後は,それで分類して,適当にかけるだけ.
そして,適当に書いてみる.
書いた.サブミット.WA.
あれぇ…,って,%lldで出力してる.修正してサブミット.でもWA.
あれぇ…,mod 9忘れてるorz 三度目の正直Accept.

D. LCIS

1000項以下の数列が10個以下与えられるので,全部に共通する部分増加列のうち,最長のものを1つ求める問題.
各項は0以上255以下.

DPすると状態数多すぎるよなぁ….
枝刈り探索…?
ちょっと書き始めてみる.
どう見ても,状態数爆発するな.
やめた.

E. Greedy Change

紙幣の種類が400種類以下ある.
紙幣の価値が与えられたとき,
 N円の買い物した時,最小枚数の紙幣で支払う方法
 大きい金額の紙幣からgreedyに使っていく方法
で使用枚数の違う最小のNを求める問題.存在しないならそれを指摘する.
紙幣の価値は10^9以下.

うーん,無理ぽい.
最小が1円で次が3円,最大がK+1円で2番目に大きいのがK円とすると…とか変なことを考え始める.
なんか,特別な点だけ調べれば良いような気がするんだけどなぁ.
頭痛いのと,眠いのと,SRMが控えてることも合って残り1時間ぐらいあるけど寝る.

Result

2WAが凄い効いてる.酷いなぁ.
結局Dの方がEより難しかったっぽい.

SPOJ 5830 - Alternating Permutations [ALTPERM] (この記事を編集する[管理者用])

Source

Codechef Snackdown
SPOJ 5830 [ALTPERM]

問題概要

長さNの置換のうち,区間[A[2*m],A[2*m+1]]は増加列,区間[A[2*m+1],A[2*m+2]]は減少列になっているものを求める問題.
Nは20000以下,Aの要素の数Kは22以下.A[0]=1, A[K-1]=N.

解法

計算時間量O(K^3 N)のDP.ちゃんと計算量見積もればO(K^2 N)の気がする.
 dp[a][b][c] = 区間[A[a],A[b]]で,残っている数字のうち小さい方からc個はA[a], A[a]+1,..., A[a]+c-1にある状態での置換の数
として,考えている区間で,
 増えて,減って,…,減って
で終わるようなものは最大値の場所で場合分け,
 増えて,減って,…,減って,増えて
となるようなものは最小値の場所で場合分けする.
(減ってから始まるようなものは,減ると増えるを入れ替えれば答えは一緒なので考えない)

SRM401 DIV1 EASY/DIV2 MEDIUM - FIELDDiagrams (この記事を編集する[管理者用])

Source

TopCoder SRM401 DIV1 EASY (250pt)
TopCoder SRM401 DIV2 MEDIUM (500pt)
Problem Statement

問題概要

1行目がf以下, 2行目がf-1以下,k行目がf-k+1以下を満たすヤング図形の数を求める問題.
fは30以下.

解法

DPすれば良い.
なんかよく見ると答えがカタラン数なので,それを使っても良い.
カタラン数と解釈する方法の1つは最初に赤のみからなるf+1の長さの行があるとして,
上から見て行って,k行目からk+1行目に行く時,
 赤が減少した数だけ(を書いて,その後)を1つ書く
とすると,対応付けられた()の列と一対一に対応する,とかと自分は考えてみた.
wikipediaにそのもの図があった….( jpg )

C++によるスパゲッティなソースコード

続きを読む

LiveArchive 4532 - Magic Rope (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Hsinchu (Taiwan) - 2009/2010
LiveArchive 4532

問題概要

2次元平面上に4N個の点がある.
その中から,4点を,その4点を結んで出来る四角形の周の長さが最小になるように選ぶ.そして4点を取り除く.
すべての点が取り除かれるまで以上の操作を繰り返す.
できた四角形の周の長さの和を求める問題.
4点の選び方が複数ある場合は,x座標が小さい点を含むものを優先する.
Nは50以下.

解法

愚直にシミュレーションする.
四角形の対角線となる2点を選ぶと,残りの2点は一意に定まる.

LiveArchive 4529 - A Constrained Queen Game (この記事を編集する[管理者用])

Source

ACM/ICPC Asia - Hsinchu (Taiwan) - 2009/2010
LiveArchive 4529

問題概要

n*nのチェス盤に数字が書かれている.
数字は右下に行くほど大きくなる.
nクイーン問題の解の場所の数字を足してできる数のうち最大値を求める問題.
nは16以下.

解法

右下の方が大きいことを利用して枝刈り探索.

Appendix

Recent Articles

ブログ内検索

Ads


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