Programming Contest

最近、Div1の底辺で迷走中のtatsyです。 今日は久しぶりにSRMの解説をやりたいと思います。 今回はEasyとMiddleの2問を解説します。問題のカテゴリとしては、 Easy (単純計算) Middle (幾何) です。 それでは、見ていきましょう。 Easy (250点) この問題は、あらかじめターンごとに進める歩数の決まった状況下で一番遠くに行ける場所はどこかを探す問題です。 ある数Nが与えられて、Nターンにわたりiターン目にはi ...

今日はひさしぶりにSRMにでました。 Easyの問題は見るからに二分探索で絶対あってると思って書いた解法がなぜか例3を通してくれず、結果1問もできませんでした。 いや、間違っていたのは非常に単純で、単にソートをするときにStrengthとCountを対応させるのを忘れてただけなんですが。 こんなイージー・ミスをしてついにDiv2に落ちてしまいました。はぁ、なにやってんだろ自分。 気を取り直して、今日も解説 ...

こんにちはtatsyです。 昨日はGCJ2013のRound2でした。いや、1問もできなかったですけど。 気を取り直して、解いた問題の中から難しめと思われる問題をリストアップしておこうと思います。 どちらかというと個人的な備忘録的内容です。 幅優先・深さ優先 AOJ0190 Eleven Puzzle 幅優先ないし反復深化深さ優先探索で解いてやればいいのはすぐ分かるのですが、全状態を真面目に探索すると計算量が多すぎて解けません。 フロー POJ 2175 Evacuation Plan 蟻 ...

少し遅くなりましたが、今回のSRM579も解説をしていきたいと思います。 今回はEasyとMiddleを解説します。僕はどちらもSystem Testで落ちましたが。 この記事に書かれているコードはちゃんと通るコードなので、そこはご心配なく。 Easy (250点) この問題はウィンドウとバッファがあるテキストエディタを扱う問題です。 あなたが文字を打っていくとバッファに文字がたまっていき、Enterを押すとウィンド ...

今日はTopCoderのSRMでしたね。 本日2回目のDiv1でしたが、Easyが解けて喜んでいたら、Challengeで軽く落とされるという・・・ では、私が間違えた点も含めてEasyのみ解説します。 Easy (250点) この問題は、最大50×50サイズのフィールドの各マスにGoose（がちょう）とDack（アヒル）がある条件の下で存在することが分かっている時、Gooseの数として考えられる場合の数を求めな ...

本日行われたGCJ2013のRound1Aですが、無事通過してRound2に進めました。 僕の成績としては A-Small, A-Large B-Small, C-Small の早解きで500位くらいという感じです。 C-Largeはちょっとやり方不明なのですが、それ以外の部分を解説してきたいと思います。 A. Bullseye この問題はカラスよけの目玉みたいなものを書いていくという問題です。与えられている条件は、 初期状態では半径rの白色の円が描かれている その外側に黒いリングと白い ...

こんにちは。 前回は苦杯をなめたSRMですが、今回はHard以外通して青に昇格しました。Hardは剰余を取るのを忘れるという凡ミスでテストケースが通らず時間切れ。あと少し早く気付ければ・・・。 さて解説に行きたいと思いますが、今回の問題はMiddleが簡単なグラフ探索を用いる以外はEasyもHardも割とごり押しで解けました。では、実際に問題ごとに解説していきたいと思います。 Easy (256点) この問題は天 ...

こんにちは。 以前からずっとやろうと思っていてできていなかったTopCoderに先日はじめて参加してみました。事前に574回のを見ていったのですが、雰囲気楽勝そう？とか思ったら、本番全然できなくて泣きそうになりました。 自己分析してみると574回はグラフ探索系の問題が中心で僕が得意なのが多かったのですが、575回は深さ優先探索中心の問題でぱっと解法が思いつきませんでした。まだまだ精進が足りないようです ...

第5回の今回は「Numerical System」という問題です。いつものように参考ページは以下の通りです。 「ACM/ICPC国内予選突破の手引き」 「AOJの問題ページ」 この問題はm,c,x,iという文字をローマ数字のように使い、それでいて2-9の数字を各桁の数を表すのに使う表記法(MCXI記法)を扱う問題です。 方針は立てるまでもなくMCXI記法と普通の数字との間の変換を行えばよいということです。力 ...

第4回の今回も少し飛びまして「Get Many Persimmon Trees」という問題を解説したいと思います。参考ページは以下の通り。 「ACM/ICPC国内予選突破の手引き」 「AOJの問題ページ」 さてこの問題では次のような条件が与えられています。 W×Hのフィールドに柿の木 (Persimmon Tree) が何本か生えている そのフィールド内に大きさS×Tの領地がもらえることになった 柿の木の数が最大になるような領地の取り方が知りたい この問題も効率よくやろ ...