読者です 読者をやめる 読者になる 読者になる

AtCoder Regular Contest 049

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

A - "強調"

問題概要

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

http://arc049.contest.atcoder.jp/tasks/arc049_a

解説

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

http://arc049.contest.atcoder.jp/submissions/665592

B - 高橋ノルム君

問題概要

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

http://arc049.contest.atcoder.jp/tasks/arc049_b

解説

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

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

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

http://arc049.contest.atcoder.jp/submissions/666159

C - ぬりまーす

問題概要

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

http://arc049.contest.atcoder.jp/tasks/arc049_c

解説

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

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

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

  • ルールAではy→xの順にしか色を塗れない。

  • ルールBでは2つとも塗るならu→vの順にしか塗れない。

といった感じです。

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

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

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

http://arc049.contest.atcoder.jp/submissions/666609

感想

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