AtCoder Regular Contest 049 C - ぬりまーす
頂点が有向グラフである意味がない…
問題概要
(リンク)http://arc049.contest.atcoder.jp/tasks/arc049_c
- N頂点の有向グラフがある
- 頂点に色を塗る
- その際以下の制約つける
- 頂点xに色をぬるとき、頂点yに色が塗られていなければならない
- 頂点uに色を塗るとき、 既に頂点vに色が塗られていてはいけない
- 適切な順番で色を塗った時、最大いくつ色を塗られるか
解法
制約をグラフで表現する。
- ひとつ目の制約はy→xというエッジ
- ふたつ目の制約は
- u → vというエッジ
- あるいはuを通行不可 (塗らない) とする
ふたつ目の制約は最大10個しかないので「u → vというエッジ」、「uを通行不可とする」を総当りする。
作成したグラフを強連結成分分解すると、強連結成分として2つ以上のノードがある場合、そのノードには辿りつけない。
例えばu←→vのようなエッジが貼ってあれば、お互いを塗るためにお互いが先に塗られていなければいけないためである。
また、通行不可としたノードから辿り着けるノードは通行不可である。
AtCoder Beginner Contest 040 D - 道路の老朽化対策について
問題概要
(リンク)http://abc040.contest.atcoder.jp/tasks/abc040_d
- y_i年に作られた道は都市a_iと都市b_iを結ぶ
- 住民jはv_jに住んでいてw_j以前に作られた道を通りたくない
- 全ての住人が移動できる都市の数を求める
解法
- UnionFindを使う
- 少し拡張してUnionの個数を数えられるようにする
- 全ての住人に対して1からUnionFindを使うとTLEとなる
- v_jが降順となるようにクエリを並べ替える
- w_jが降順となるように道を並べ替える
- こうすることで重複した処理を行わずにすむ
- O(max(N log N, Q log Q, Q+M log α(N) ) ) ？ (わからん) (間に合うということはわかる)
AtCoder Beginner Contest 040 B - □□□□□
ABCのBなのに、難しいと感じた人が多かった問題。 1回REでWAを出してしまった。
問題概要
(リンク)http://abc040.contest.atcoder.jp/tasks/abc040_b
n枚のタイルを敷き詰めて、長方形を作る。
その時、短辺と長辺の差 + 余ったタイルが最小になるようにする。
解法
愚直に実装する。
短辺と長辺の組み合わせをすべて試す。
O(sqrt(n))
ans = min (ans, abs(短辺-長辺) + n % (短辺×長辺))
なぜ難しい
短辺と長辺の差に着目すると、1辺をnのルートに近づければいいのでO(1)で求められそうな気がする。
その方向で考えをすすめるとハマる。
あと、短辺と長辺を全て考える時、調べる範囲を適当にすると短辺×長辺が0になる時、余りが計算できずREになった。
AtCoder Regular Contest 55 C - ABCAC
問題概要
文字列Sに対して
S=A+B+C+A+C
となるような部分文字列A, B, Cがいくつ考えうる数え上げる。
解法
部分点
- AとCの文字数を決める
- O(N2)
- 条件を満たすかはローリングハッシュでO(1)
満点
- SをABCとACに分ける境目を探索する
- その際、Z algorithmを使ってAとして考えうる文字列で最長のもの、Cとして考えうる文字列で最長のものを求める
- 上記の値から、境目で分けた場合に考えうるA, B, Cの数を計算する
