Entries

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

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

ACM ICPC South America Regional Contest (この記事を編集する[管理者用])

2009年10月25日05時から5時間,11問.
[ Link ]

ICPCシリーズ第2弾.
これも11問で問題数は多めだけど,簡単な問題が多い.
でも,結構楽しかった.
C以外の10問解いた.
以下時系列順.

Aを読む.問題pdfだ….下から計算していくだけっぽい.
Bを読む.シミュレーション.やるだけ.
Cを読む.何これ.無理ゲー.Aizu 2157で桁数が1000になって,1回で1だけしか回せないバージョン….
Dをサンプルだけ見て理解する.?は早い方からE,遅いのがXに当てはめてソートしてなぞれば良い.
AとBとDを書く.AC*3.
Kを読む.問題意味を理解するのに手間取った.それぞれのdivごとに,閾値1002通りのコストの増分を全部計算して,最小のところを探す.AC.
Jを読む.最初に64倍しておいて,足して64になるかチェックするだけ.AC.
Iを読む.正三角形があったら困るよね….でも,格子点の上に乗らないんじゃないかな?
まぁ,正三角形はないと思って適当にやってみた.AC.
Eを読む.ひたすら2分探索で.AC.
Fを読む.どうみてもSuffix array系です….僕には無理.
Hを読む.適当に点数が低い方を勝つようにして,ベルマンフォードっぽくバランス取れて収束するまでループする.AC.
Gを読む.サイズが決まれば,調べるべき正方形の候補はO(R+C)ぐらいじゃん.正方形サイズを2分探索するか.AC.
しょうがないからFをやる.助けてスパゲッティソース!ってことでAC.
CはDPでなんとかできないか?WA*n.
A < B < C < Dとして,区間[A,C]を回して,その後区間[B,D]を回すことは考えなくて良い.
だったらO(26*n^3)ぐらいのDPになるんじゃ….→TLE.
無理.諦めた.

Dhaka regional Semi-live (この記事を編集する[管理者用])

2009年10月24日20時から5時間,11問.
[ Link ]

UVaでのICPC regionalシリーズ今年1個目.
どっちかいうと実装系問題が多めかな?
7問解いた.
以下時系列順.

Aを読む.どうせC個しか出力しないので,キューの中身はMIN(N,C)個ぐらいだけ覚えておけばよいのでは.
Bを読む.各桁ごとに計算するだけっぽい.
Cを読む.どう見てもDP.計算量はまだ考えてない.
Dを読む.なんだこれ.余ったら一番若いの出力するだけじゃ…?
Eは図が壊れてて読めないぞ….
Fを読む.面倒な実装系.頑張ればできそう.
G, H, Iは読むの面倒そうなので,Jを読む.数学ゲーっぽい.
Aを書く.AC.
Bを書く.AC.
Dを書く.AC.
Cを書く.愚直に書いても間に合いそうだけど,bitに押し込んで頑張る.
WA.なんで?
同じ行に同じキーワードが2個以上ある場合もあるらしい….AC.
Jは,べきの数を1/Tに減らして,約数の数を数えると,T個以上0が後ろに付くようなベースの数が求まる.
ので,素因数分解してごにょごにょするだけだ.AC.
Eをpdf開いて読む.メモしながらBFSするだけだ.
いや,状態が3^16あるぞ….でも,重力のおかげで実際はそんなにないはずだし,なんとかなるのでは?
書いた.普通に通った.AC.
Iを読む.わからん.
Kを読む.NP完全に見える….頑張って探索?
メモしながら適当に探索してみる.TLE*4.諦めよう.
Gを読む.
カメラは外周のどこかに置くのが最適だよね.
じゃあ,各点が外周のどこの範囲で見えなくなるか求めてやって,尺取メソッドで良い筈.
書いた.WA.
xとy書き間違えてる.直す.送信.サーバが見つかりません.
また,UVa落ちたか….
取り敢えず,Hを読む.
3分探索で,適当に節点候補を求めてやって,DPすればよいのでは.
書く.
2番目のサンプルが合わない.
ってか,5.464 = 2.828 * 2じゃないじゃん….
ん,googleも繋がらない.
違う,プロバイダに繋がってない.
特に停止するとか連絡なかったはず.まぁ,復旧するまで待つしかないか….
1時間ぐらいぼけーっとする.
深夜0時15分,復旧せず.
せっかくだから,Hぐらい送りたい.
研究室に行けば良いのでは.
研究室到着.深夜0時40分.残り時間20分.
GがWAだったことを確認.
Hを送る.WA.
Gで誤りに気づく.ときどき見える区間と見えない区間が反転してた.直した.AC.
Hも誤りに気づいた.DAGじゃないんだから,ちゃんとダイクストラしなきゃいけないよ.
でも,残り2分では組めず.
Fも書くだけっぽかったので,1時間ぼーっとしてなきゃ,書けたかなぁ….

みるくくるみメドレー / Rirykaメドレー (この記事を編集する[管理者用])

ちょい古い動画だけど,みるくくるみメドレー(sm2235768)とRirykaメドレー(sm2247950, 2008年01月分まで).
風の継承者の虹の向こうって,くるみさんだったのか….今聞けば明らかにRirykaさんだけど当時気づいてなかった.
みるくくるみ時代は曲調幅広いけど,名前変わってから格好良い曲一筋なのがよくわかる(Still youが浮いて聞こえるし,まぁ年代的にも浮いてるが).
みるくくるみ時代も,後半になるに従って格好良い曲増えてくるなぁ….
最初に聞いた曲が,Rock On Youだったこともあって,電波系な曲もまた歌ってほしいなぁとか願ってみる.
まぁ,声が格好良いので,格好良い曲を歌うのは大歓迎.Rirykaさん格好良い歌詞も書くし….

流石に知らない曲は殆どなかったけど,夏神のみだれ髪を知らなかった,不覚過ぎる.
これかなり良い感じだぞ.
音遣い的に一瞬Elements Gardenっぽく聞こえたけど,そんなことはなくて,Angel Noteだった.ってか,不知火さんGJ.
Angel Noteの曲の提供先が微妙にマイナーなのが多くて困る….

Rirykaさんがアニソン歌ったのって,たぶん,GIRLSブラボーと,Venus Versus Virusだけだよね….
前者はAngel Noteで後者はElements Garden.
また,歌ってくれれば良いのに.てか,Angel Noteもっとアニメに曲提供すれば良いのに….
VVVのOPはとても直球な曲で凄い好きです.

色褪せた旋律がねぇぞー,と思ったら,2008年03月発売だった….

UVa 11722 - Joining with Friend (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11722

問題概要

ある電車は時間[t1,t2]の間にランダムに到着する.
もう1つの電車は時間[s1,s2]の間にランダムに到着する.
両方ともwだけ停車する場合,同時に停車してる時間がある確率を求める問題.

解法

場合分けしながら頑張って計算する.

UVa 11721 - Instant View of Big Bang (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11721

問題概要

ノード数1000,枝数2000以下の有向グラフが与えられる.
枝にコストが与えられているので,負サイクルに辿り着けるノードを列挙する問題.

解法

任意のノードに辿り着けるコストを0に設定して,枝の向きを逆向きにしてベルマンフォードをノード数ステップぐらい行う.
後,1ステップ進めて,コストが更に減少するノードは,負サイクルのノード全てと負サイクルから辿り着けるノードの一部.
後は,そのノードからDFSして全て求めれば良い.

UVa 11720 - How Many Ways (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11720

問題概要

1からNの自然数の中から,異なるK個を選んで和をNする方法の数を求める問題. Nは10^9以下,kは10以下.

解法

要するに分割数.
k!飛ばしでみると多項式になる(参考)ので,Nが10!*10ぐらいまで計算して,多項式を求める.

UVa 11719 - Gridland Airports (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11719

問題概要

R*Cのチェス盤がある.
白いマスと黒いマスをつなぐことができる.
R*C-1個繋げて,全部連結にする方法の数をmod 10^16+7で求める問題.
RとCは10^18以下ぐらい.

解法

要するに完全2分グラフの全域最小木の数を求める問題.
小さい時を適当に全探索して調べると,規則がわかる.

UVa 11718 - Fantasy of a Summation (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11718

問題概要

問題文に書かれた非効率的なプログラムの実行結果を求める問題.
適当に配列の中身を足していくプログラム.

解法

それぞれの値を何回足すかというのは,計算できるので,べき乗などを用いて計算するだけ.

UVa 11717 - Energy Saving Microcontroller (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11717

問題概要

n個のタスクがある時間に到着する.
準備ができていれば,即座にタスクをかたずける.
準備ができていなければ,準備にk秒間かかり,それから瞬時に片づける.
k秒間の間に,追加のタスクが来たら,それは無視する.
i秒間暇なら準備状態が解除される.
準備状態が解除された回数と,無視されたタスクの数を求める問題.

解法

シミュレーションするだけ.

UVa 11716 - Digital Fortress (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11716

問題概要

n^2の長さの文字列が与えられたとき,縦にn*nに並べて,横に読んだ時の文字列を求める問題.
長さがn^2でなければそれを指摘する.

解法

やるだけ.

UVa 11715 - Car (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11715

問題概要

最初,スピードがuで,時間tだけ,一定の加速度aで進むと,速度がvになって,sだけ進んだ.
適当な3つの値が与えられたとき,残り2つを求める問題.

解法

適当に式を立てて計算する.
時間を求めるときのみ2次方程式を解く必要があることがある.

UVa 11714 - Blind Sorting (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11714

問題概要

未知のn個の互いに異なる数字がある.
コスト1で,ある2つの数字に対して,どちらが大きいか知ることができる.
最悪ケースで,一番大きい数字と2番目に大きい数字を特定するのに必要な最小コストを求める問題.

解法

1番目の数字をトーナメント方式で決めたとして,2番目の数字の候補は1番目に負けたものだけ.
なので,最大の対戦回数を最も少なくするように,バランスする.
とか考えると,数学的に求まる.

UVa 11713 - Abstract Names (この記事を編集する[管理者用])

Source

IIUPC 2009 (2009-10-21) (blog)
UVa 11713

問題概要

与えられた2つの文字列が等しいかどうかを判定する問題.
ただし,母音は全て同一視する.

解法

やるだけ.

SPOJ 3580 - Company [COMPANY] (この記事を編集する[管理者用])

Source

MIT Individual Contest 2008
SPOJ 3580 [COMPANY]

問題概要

ノード数1000以下,枝数10000以下のDAGが与えられる.
a→b→cならa→cという条件は暗黙のうちに成り立つので,条件を変えないようにできるだけ枝の数を減らしてくださいという問題.

解法

できるだけ,弱いノードから枝をアドホックに追加していくことで,O(ノードの数*枝の数)でできる.

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

2009年10月21日18時から5時間,10問.
[ Link ]

簡単な問題が多めだけど,難しい問題は結構難しい.
数学色の濃い問題が多い気がした.
何とか10問全部解けた.
以下,時系列順.

Aを読む.やるだけっぽい.取り敢えず今回は先に問題を読んでいく方向で.
Bを読む.よくわからん.適当に2つに分けて分割統治とかが最適なのかな…?
Cを読む.物理.紙の上で計算するだけっぽい.
Dを読む.簡単な文字列実装問題.やるだけっぽい.
Eを読もうとして,面倒になって読めなかった.
Fを見る.ソースコードが与えられる問題,前もなかったっけ.こういうの好きだな….適当にべき乗とかで計算できそう.
なんか問題読むのが面倒になったので,コード書いていく.
Aを書く.通る.
Bを分割統治で書く.WA.
色々悩みながら,どういう場合が最適か苦しみながら考えてAC.
よくよく考えれば(気づけば),簡単な話だった….
トーナメントで1位を決めたとして,2位の候補は1位に負けた人のみ.
じゃあ,最悪ケースは1位が最も戦った回数が多い場合で,トーナメントをバランスして組めば最適….
大雑把に,だいたいn+ceil(log2(n))-2ぐらいが答え.
Cを書く.うお,2次方程式解かないと駄目っぽいな.思ったより面倒だった.でも簡単.AC.
Dを書く.やるだけ.AC.
Fを適当に書く.答え合わない.ちゃんと考えて計算する.間違ってた.書きなおす.AC.
E解いてる人多いな…,Eを読む.
なんだ,シミュレーションするだけじゃん.書く.AC.
次は,J解いてる人がいるか….読む.
確率計算.場合分けが面倒….書いた.AC.
GとHは数学ゲー.無理っぽ.
Iを読む.ベルマンフォードでいけるじゃん.
と,思ったら,つまづいた….ちょっと考えて,枝の向きを逆にすれば良いことに気づいた.AC.
数学わからねー,そして腹減った.
スーパーに食糧を買いに行く.飯を食う.これで1時間浪費.
飯食ってる間ずっと考えてたんだけど,Hは,k!ごとに飛ばしてみると多項式になってるはずなので,多項式を求めれば良いのかな….
でも,10*10*10!ぐらいの状態数でDPしないといけない….
取り敢えず,DPだけ書いて実行してみる.ローカルで1.7秒.
ついでにサブミットしたら2秒ぐらい.いける!
後は,テストケースを最初に全部読み込んで,kでソートして,とか適当な最適化して送信.AC.
Gは全然わからん.適当に小さいケースを全探索で計算してみる.
なんか綺麗な数字が出てきたぞ….規則性が簡単に見つかった.
64bit * 64bit mod 64bitのライブラリコピペで適当に書く.送信.AC.

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

2009年10月21日10時から.

Assignment

RedCoderが11/19.
しかも,RedCoderの中でも上位層が多い.
怖いけど楽しそうな部屋.
反面,YellowCoderは少なめ.

EASY

瞬殺問題.
1,11,111,1111,で割り切れるかチェックしていくだけだよ.
サブミット.

MEDIUM

最近では珍しく単純なDPだなぁ.
今いる点,今まで何個の点を通ったか,を状態にして,ここに来た時のジャンプ幅の最小値を記録しておけばよい.
と,思ったのに,なぜか,今いる点と,ここに来た時のジャンプ幅を状態にして,通ることのできる点の数の最大値をメモしている自分がいる….
まぁ,少々計算量多いけど,これでも大丈夫だよね?
サブミット.

HARD

無理ゲーっぽい臭いがぷんぷんと….
22*2^22ってメモリ足りないよな….
残り25分ぐらいあるけど諦めた.

Intermission

MEDIUMはサンプル弱かったし,実装色が濃いので結構落ちそう.
取り敢えず,コーナーっぽいテストケースを用意.

Challenge

MEDIUM,まぁ,読めないよね,うん….
ぼーっと眺めているうちに,MEDIUMに無差別爆撃っぽいのが仕掛けられて結構落ちる.
やることなくなった.

System tests

MEDIUM落ちた…,TLEじゃなくてWA.あれぇ….
ホントに最近バグなく書けないな…,なんだろう.
rateは,再びがくんと下降.

HARDは皆落ちた.やっぱり無理ゲーだったらしい.
でも,2*2^22はメモリに乗るし,bitは隣り合う2bitの組で出てくるので状態数としてはそんなに多くないらしい.
なるほど.

電気式華憐音楽集団 (この記事を編集する[管理者用])

デンカレ,Princess Party (無印)の挿入歌も歌ってたことを今更知る.
OPのIOSYSの印象が強かったからなぁ….
デンカレ,こんな曲もいけるのかー,結構幅広いよね.
ってことで,今日のTCのBGMはデンカレメドレー(sm7572554)で.
でも,やっぱりデンカレはブサイクが良く似合う….

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

アニメ11eyesのOP/EDはゲーム(PC)と同じメンツ.shortしか聞いてないけど.

OPはTatsh,彩音.
これはゲームOPの方が好きだったかなー.
てか,十分良い感じだと思うんだけど,ゲームOPが良すぎた.

EDはAsriel.
こっちは格好良いなー.良い感じだなー.ゲームEDも良かったけど.
相変わらずAsrielはいい仕事する….

片霧烈火 / fripSide / Riryka (この記事を編集する[管理者用])

2009-08-20 Thu 18:30の記事で触れたけど,Aliceの新作のOPはやっぱり烈火さんだった.
Full聞いてみたけど,2番終わりから間奏への移り方が多少強引な気が….
間奏後,サビを単純に繰り返すだけじゃなくて,捻りまくるのはShadeさんっぽい.良い感じ.
Shadeさん×烈火さんだと,烈火さんにしては,全体的に音が高い曲になるのかなー.
関係ないけど,DJ C++さんの音遣いとか時々Shadeさんっぽくてドキっとする.
でも,Shadeさんの方が断然格好良いよなぁ…,まぁ,比べる相手が悪すぎる.

アニメの真・恋姫無双はfripSideがnaoさん抜けちゃったのでOPとかどうなるのかと思ってたら,烈火さんが歌うのね.
ゲームと同じくってことか.でも,たくまるさんじゃない!
格好良いけど,ちょいとインパクトが薄いかな.

で,fripSideは新ボーカル決まってたのね.
南条愛乃さん….名前は見たことある気がするけど誰だっけ?って感じでした.(ごめんなさい)
fripSideは,とある科学の超電磁砲のOPを歌ってるみたい.
正直naoさんの方が良かった気もするけど,これはこれで有りだと思った.
歌い方の違いもあるのかもしれないけど,いつものfripSideの曲に比べて音域が狭い気がした.
fripSideの曲は音域が広いのが特徴の1つだと思うので,そういう曲も聴いてみたい.
後,NAO project!が好きだったんだけど,そういうのもこれから作るのかな…?
(それとRitaさんはもう歌わないのかな…? 音が低くて(というか1オクターブ落として歌ってて?)少し歌いにくそうな感じだったけども…)

みるくくるみ時代の曲だけど,RirykaさんのIn the DarkのFull聞いた.
相変わらず格好良いよなぁ.

UVa 11712 - Gnirut (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11712

問題概要

UVa 11711と入力と出力が逆になった問題.
AC, WA, TLE, MLEの判定が与えられるので,そういう判定になるようなチューニングマシンとテストケースを1つ作成する問題.

解法

適当にチューニングマシンとテストケースをでっちあげれば良い.

UVa 11711 - Turing (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11711

問題概要

簡易チューニングマシンが与えられる.
入力と想定出力も与えられるので,与えられたチューニングマシンで実行した結果,AC,WA,TLE,MLEのどれになるかを判定する問題.

解法

シミュレーション,実装問題.
やるだけ.

UVa 11710 - Expensive subway (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11710

問題概要

全域最小木のコストを求める問題.
連結でなければそれを指摘する.

解法

やるだけ.

UVa 11709 - Trust groups (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11709

問題概要

AはBを信頼している,などといった関係が与えられる.
幾つかのグループに分けるのだけど,グループ内の人間は全員互いに信頼し合ってなければならない.
最小で幾つのグループに分けることができるかを求める問題.

解法

強連結成分分解.

UVa 11708 - Lexicographical ranking (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11708

問題概要

20個以下のアルファベットを高々1個使ってできる文字列を辞書順でソートする.
文字列が与えられたとき,何番目か?
もしくは,数字が与えられたとき,その番号の文字列を出力する問題.

解法

実装問題.
階乗やコンビネーションを使って適当に計算する.

UVa 11707 - Pachinko (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11707

問題概要

線分が500個以下ある.
上からボールを落として,線分に当たったら,それに沿って落ちていく.
最終的に[-10,10]の穴にボールが入るかどうかを判定する問題.

解法

2次元幾何 + シミュレーション.端を全部試す系.
実際に,いろんな場所から落としてみて,シミュレーションする.

UVa 11706 - Party Night (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11706

問題概要

街人100人以下の人がいて,それぞれ会ったことがあるかどうかが与えられる.
ある2人が会ったことがあるという関係は1000個以下.
この街では2回パーティーを行い,それぞれのパーティーは複数の会場で行われた.
同じ会場にいた人は全部会ったことがあるという関係が成り立つ.
また,同じ2人が,2回とも同じ会場にはいなかった.
矛盾がないかどうかを調べる問題.

解法

街人をノード,会ったことがある関係を枝と書く.
それぞれ枝の色を塗る.それは1回目のパーティーで知り合ったか,2回目のパーティーで知り合ったかの2色.
 3ノード間に3つの枝があれば,全て同じ色でぬらなくてはいけない.
 3ノード間に2つの枝があれば,違う色でぬらなくてはいけない.
という条件から,2彩色可能かどうかという問題に落ちる.

UVa 11705 - Grasshopper (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11705

問題概要

50*50のグリッドに整数が書いてある.
書いてある整数の距離だけだけ上下左右にジャンプして,一番左上のマスに辿り着きたい.
それぞれのマスでどの方向にジャンプすれば最短で辿り着けるかを求める問題.
辿り着けないなら,それを指摘する.
ジャンプする方向が複数あれば,最も上,それでも複数あれば最も左に向かうのを優先する.

解法

最も左上のマスから逆向きにBFSするだけ.
頑張ればO(マップのサイズ)でできるが,実行時間的にはもっと愚直に書いても問題ない.

UVa 11704 - Caper pizza (この記事を編集する[管理者用])

Source

CUPCAM 2009 (2009-10-17) (blog)
UVa 11704

問題概要

原点中心,円形の円盤の上に,2種類の点がそれぞれ偶数個ずつ乗っている.
原点を通るように1回だけ直線でカットして,それぞれ2種類の点を,同じ数だけ2分割したい.
可能かどうかを判定する問題.
点の数は30000以下.

解法

点は,x軸からの角度だけを考えれば良い.
角度でソートして,後は,尺取りメソッドで少しずつ動かしながら,条件を満たすような切り方があるかどうかを探す.

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

Source

TopCoder SRM450 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

現在n個の施設と,k人の人がいる.
毎ターンの最初に,施設の数×人数の分だけお金が手に入る.
毎ターンの最終時に,施設や人を好きなだけ増やすことができる.どちらを増やすにしても1あたりpriceだけコストがかかる.
お金がtarget以上となるための最小ターン数を求める問題.
n, k, price, targetは10^12以下.

解法

n*kを計算するとオーバーフローする場合があるので,最初にn*kが明らかにtargetを超えている場合を例外処理する.
施設などに投資する場合,投資できるようになったら,できるだけ早く投資した方が良い.
ので,投資する回数が決まれば戦略は一意に定まる.
投資する回数は,O(sqrt(target))程度なので,後はシミュレーションすれば良い.
具体的には,
 現在のまま投資しなければ何ターンかかるか計算して,最適値を更新する
 もし,投資できる金がないなら,1人以上雇えるようになるまで時間を進める
 もし,投資できる金があるなら,1人だけ雇う,時間は進めない
というループで実装すれば良い.
n*kの値がtargetを超えたら終了する.

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

class StrongEconomy {
public:
ll earn(ll n, ll k, ll price, ll target) {
  ll res=target, now=0, turn=0;
  ll next, gain;
  
  if(n>target/k) return 1;
  
  for(;;){
    gain = n*k;
    next = (target-now)/gain; if((target-now)%gain) next++;
    if(res > turn+next) res = turn+next;
    if(next<=1) break;

    if(now >= price){
      if(n<k) n++; else k++;
      now -= price;
    } else {
      next = (price-now)/gain; if((price-now)%gain) next++;
      turn += next; now += gain*next;
    }
  }

  return res;
}
};

SRM450 DIV1 EASY - OrderedNim (この記事を編集する[管理者用])

Source

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

問題概要

2人でゲームをする.
基本的にはNimだけど,山に順番が付いていて,自分の山の前の山に石が残っている場合,前の山から取らなければならない.
山の石の数(1以上の大きな数字も許される自然数)が与えられたとき,先手必勝か後手必勝かを判定する問題.

解法

最初に2個以上の山に当たった人が,全部取るか,1個残すか自由に選択できるので勝つ.
全部1個だと,最後の山に当たった人が勝つ.

C++によるスパゲッティなソースコード
#include<vector>
#include<string>
using namespace std;

class OrderedNim {
public:
string winner(vector <int> layout) {
  for(int i=0;;i++){
    if(layout[i]>1 || i==layout.size()-1){
      if(i%2==0) return "Alice";
      return "Bob";
    }
  }
}
};

Appendix

Recent Articles

ブログ内検索

Ads


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