http://m-judge.maximum.vc/contest_front.cgi?cid=31 A ラッキーマンですか 尺取メソッドでサックリ書く。AC B 幾何 3点から円を計算するライブラリが無いので後回し C どう見てもDP 書いた。答えが合わない。「超える」の部分を「以上」と解釈したらあった…

LayCurseさんとかtsukunoさんが居る部屋。 250 グラフが条件を満たしているか判定する問題 50^4くらいかかっても大丈夫な筈なんでa,b,c,dを全探索 書いた。50^5になったけど気にしない。 450 条件を満たす石の置換はどのくらいあるか？ マークされた場所と石…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4880 問題 一部が読み取れず、左右も分からないバーコードの入力を与えるので、存在し得る数値の列を答えよ。 解法 メモ化dfsで解く。ただし、9個解を見つけた場合は探索を打ち切る。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4877 問題 長さnの数値で各桁が非減少列になっている物の個数を求めよ。 1 解法 DP。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4873 問題 HとTから構成される文字列を与えるのでTTT,TTH,THT,THH,HTT,HTH,HHT,HHHの個数を求めよ。 文字列の長さ=40 解法 やるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4031 問題 最大dの遅延が生じるネットワーク上で長さnのビット列の送信を行う。送信するビット列を与えるので送信される可能性のあるビット列の個数とその最小値、最大値を答えよ。 1 0 …

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4030 問題 頂点数n、辺数mの有向グラフを与えるので複数の閉路を作り、辺の重みの合計を最大化しろ。 1 m 解法 ベルマンフォードを行い負閉路(今回は正閉路)を見つけ、負閉路に最大流の…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4026 問題 曲のフレーズとその曲を覚えられていたかを与えるので最も難しいメロディーを答えよ。メロディーとは長さkの曲のsubstringである。メロディーの難しさとは(覚えられていた曲の…

Emkさんとかがいる部屋。 250 数列の問題か。 n=20くらいなら全探索かなと思ったけど50もあるんか。 とりあえず解は常に存在するっぽい。 greedy?ちょっと違う気がするな。 k-1まで最適な場合にk番目の数値を入れることを考える。 Iの場合はkを入れるだけ。D…

ちょっとEfficient Graph-Based Image Segmentation*1のセグメント化で3色だけでなくもっと次元(例えば深度マップとか)を増やしたいんで練習用に書いてみた。 前処理の平滑化の方法はめんどくさいんでガウシアンフィルタを使った。sigmaを0にしても、本家の…

kirita君と一緒の部屋。 250 色を塗る問題。 どう見てもやるだけじゃん。 書いた。提出した。 500 ボールを転がすらしい。 ぶつからずにすり抜けるんか。 サンプルがおかしいと思ったら。全部同じ速度なんか。 じゃあ2SATか。というか前似たような問題が250…