はい、では今日もさっそく行ってみましょう。 今日のEasyのみ解説します。 Easy (250点) この問題は横一列のマス目がいくつかあって、そこに右にしか動けない駒と左にしか動けない駒がいくつか置いてあります。 その駒を動かして初期配置beginから目的配置targetに変更できるかどうかを答えます。 まず、注意したいのが駒の順番は入れ替わらないということです。 ですから、beginとtargetの両方で左から順に ...

今回のSRMはEasyでなかなかのChallenge祭りになっていました。 僕も何とか参加して100点稼ぎました。肝心の解答の方は他の人にChallengeされてしまいましたが、レートが上がったので良しとします。 今回の問題はEasyが貪欲法、Mediumがグラフの問題です。それでは、さっそく解説します。 Easy (250点) この問題は与えられた文字列をある方法にしたがって変更して回文になるようにするというも ...

こんにちは。tatsyです。 なんとも分かりづらいタイトルですが、この記事ではある配列が与えられたときに、各要素に対して自分より右(もしくは左)にある自分より大きいもののうち一番近いものを割り当てる問題を解きます。 やっぱり分かりづらい・・・つまり、例を示すなら、右にある自分より小さい数を見つけるとして、 入力: [4, 2, 3, 5, 1] 出力: [2, 1, 1, 1, -1] みたいになります。一番右の1は自分より小さい数がもう右にないので- ...

最近、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を押すとウィンド ...

2013年9月24日 update こんにちは。今日は久しぶりに画像処理のプログラムをアップしたいと思います。 今回紹介するプログラムは、2011年にSIGGRAPHで発表された Gastal and Oliveira, “Domain Transform for Edge-Aware Image and Video Processing”, ACM Trans, Graph, 30 (4), pp.69:1-69:11, 2011. という論文の手法です。 少し画像処理を勉強したことがある人なら、バイラテラル・フィルタという名前を聞いたことがある人も多いと思います。バイラテラル・フィルタは画像全体をぼ ...

今日は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の白色の円が描かれている その外側に黒いリングと白い ...