AtCoder Regular Contest 049 - アルゴリズマーの備忘録

WAするんじゃないかとヒヤヒヤしながらの提出だった…３完。18位と史上初の20位以内に入り込めました。

文字列SのA,B,C,D番目の前に"を追加せよ。

やるだけ。substrなんて高等技術はないのでループ回します。

N人の人が１箇所に集まる。(x1,y1)にある人がいて、(x,y)に移動するとき、c*max(|x1-x|,|y1-y|)秒かかる。最小何秒で１箇所に集まれるか。

仮にt秒で集まれたら絶対t+1秒でも集まれる。ということで２分探索。

(x,y)にいて、t秒で行ける範囲は(x+t,y+t),(x-t,y+t),(x+t,y-t),(x-t,y-t)の正方形の範囲内。これをレイヤーを重ねるようにしていき、最後まで残ればOK、途中で新しいレイヤーと重なる部分がなくなるならNG。

なんかこんな処理のやつ、左から順に棒が上下にスライドしてるのを止めて、右までつなぐゲームに似てるな…

N頂点の有向グラフがある。N個の頂点に色を付けていくが、A個の組(x,y)が与えられ、頂点xiを塗るときはyiが塗られた後でないといけない。B個の組(u,v)が与えられ、頂点uiを塗るときは頂点viが塗られていてはいけない。最大何頂点に色を塗れるか。

※最初に書いた文章があまりに酷かったので後日書き直しています。

まず、問題文に「有向グラフ」と書いてありますが、問題文を読むと有向グラフである必要性が最初全く無いように感じました。

取り敢えず分かることをまとめると、

といった感じです。

ここで、上のルールで塗る順番を有向グラフにしたとき、有向辺の入ってない点から何頂点を訪れることが出来るか、が答えになる、と言い換えられます。

また、ルールBではuを塗ることを諦めることでvは自由に塗ることが出来ます。つまり、ルールBの各条件でuを諦めるか、諦めないかで全探索します。

以上から、ルールBの全探索をしながら最大何頂点を訪れることが出来るか、を更新していくことで答えが得られます。

最近Mayaを始めました。スパコン出たいけど、競プロやる時間が減っているので、適度にやらないと…