ARC 097 F Monochrome Cat

問題

N頂点からなり、各頂点が黒または白である木が与えられる。
好きな頂点から出発して、

  • 今いる頂点の色を反転させる
  • 隣接する頂点に移動して、移動先の色を反転させる

の二つの操作を好きなだけ行える。全部の頂点の色を黒にするのにかかる操作の回数の最小値を求めよ。終了時にはどこにいてもいい。
https://beta.atcoder.jp/contests/arc097/tasks/arc097_d

制約条件

N≦10^5

続きを読む

ARC 097

ボケ防止にまったり勢でプロコン復帰します。

C

sの異なる連続する部分文字列のうち辞書順でK番目に小さいものを出力せよ。

  • 最初から結構難しそう。制約がないと結構面倒な問題じゃなかったっけか。
  • substringを全部列挙してsetに入れる → O(N^3logN)とかになり間に合わない。
  • Kが小さいらしい。長さ1〜Kの文字列は全部異なるから、各iについてs[i..i+K]まで列挙すれば十分
  • AC. 最初の問題に7分以上かかる。相当考察力が落ちている。

D

順列pとn個のタプル(xi, yi)が与えられる。順列に大してxi番目とyi番目を入れ替える操作が何度でもできるとき、pi = iとなるiの個数を最大化せよ。

  • (1, 3), (3, 4)が与えられていたら1, 3, 4番目は自由に入れ替えられる
  • 各連結成分ごとに要素をまとめて、成分内でマッチングすればよさそう
  • 二つの単調増加列のマッチングだから尺取りで書けばいい
  • AC.

E

1〜Nまでの数字が書かれた白いボールと黒いボール合わせて2N個が一列に並んでいる。
隣り合うボールを入れ替えて、白いボールだけを見たときにソートされていて、かつ、黒いボールだけを見たときにソートされている状態にしたい。必要な操作の回数の最小値を求めよ。

  • バブルソートの交換回数の拡張みたいな奴。バブルソートのときってどうするんだっけ。
  • Binary Indexed Treeで転置のペアの個数を数えるだっけ → 今回は転置を数えても最終状態が一意に定まらないし上手くいかなそう
  • バブルソートの交換回数って分割統治みたいなアルゴリズムもあったような。忘れた。
  • 普通のバブルソートの交換回数は、愚直に求めるには当然O(N^2)でバブルソートを実際にシミュレーションすればいい。
  • 今回、最終状態が一通りじゃないからシミュレーションすら無理だ。
  • 白いボールの位置を決めたらコストは求まりそう → DPなんかなこれ。
  • dp[白いボールを使った個数][黒いボールを使った個数] := その時点の操作の回数 とすると?
  • いけそう、書いてみる。
  • 遷移が上手く書けない。bitか何かでコストを高速に求めないといけない。
  • 思考がごちゃごちゃする。遷移を整理してみる。
  • 白をi個、黒をj個使った状態で白のi+1を使うとき
  • 列の白i+1の前にあるボールのうち、白の番号がiより大、黒の番号がjより大のものの個数が高速に求まればいい。
  • 最初に前計算すればいいか。
  • 送信。RE. 配列を2NじゃなくてNで取ってた。
  • 再送信してAC.
  • 手間取りすぎー。順位表見ると、この時点で48位。どの程度なのか全然わからない。
  • 昔のTopCoderだったら微妙。ARCはそれより参加人数少なそうだし(要出典)アレかも。

F

木が与えられる。頂点は白または黒。好きな頂点から出発して、今いる頂点の色を反転させる、または隣接する頂点に移動して、移動先の色を反転させる、の二つの操作を好きなだけ行える。全部の頂点の色を黒にするのにかかる操作の回数の最小値は?終了時にはどこにいてもいい。

  • 残り1時間。
  • 全部の頂点を回る必要はなさそう → 白と白のパス上の頂点だけ考えればいい
  • 木の黒のリーフは落とせるだけ落として考える。
  • 白の頂点が木のリーフにしかないとき、オイラーツアーが最適解?
  • そうじゃないとき、なんか移動を節約できる。。。どう節約できるんだろう。
  • 各辺て何回通る? → 高々2回でよさそう
  • 内点の白のたびに2節約できる? → いや全然嘘
  • 次数によってオイラーツアーした後の色がかわるやんけ。リーフしかないときはオイラーツアーするだけが最適解も嘘だ。
  • 時間切れ。

ICPC2017 Asia Regional Tsukuba J String Puzzle

問題

長さnの文字列がありその一部の情報が以下のどれかの形式で与えられる。

  • x文字目がcである
  • l文字目からr文字目がh文字目からと等しい


このときq個のクエリ、x文字目が何の文字であるか、あるいは与えられた情報からではわからないかを答えよ。

制約条件

n≦10^9
アルファベットは英小文字
情報とクエリは1000以下ずつ
それぞれの文字iについて、i文字目とj文字目が等しい(j < j)であるような関係は高々一つしか与えられない。

続きを読む

ICPC2017 Asia Regional Tsukuba I Starting a Scenic Railroad Service

Hは解説みて通しはしたけど解法の意味がわからない。

問題

n人の乗客がいてそれぞれ駅s[i]からt[i]まで電車に乗る。
全員が座るためには各人が席を指定できないとき、最小でいくつの座席が必要であるか、
また各人が自由に席を指定できるとき最小でいくつの座席が必要であるか求めよ。


また、乗客Aが駅1から2乗客Bが駅2から3まで乗るとき座席は1つで足りる。

制約条件

n≦10万

続きを読む

ICPC2017 Asia Regional Tsukuba G Rendezvous on a Tetrahedron

問題

全ての辺の長さが1の正四面体ABCDの頂点Aから二つの点p, qが与えられた向きに与えられた長さだけ進む。
点は正四面体の辺を通過するとき、辺と進む向きの角度が変化しないように進む。


移動後に二つの点が同じ面の中にいるかを判定せよ。

制約条件

移動後に点がギリギリ辺や頂点のそばにいるケースがない

続きを読む

ICPC2017 Asia Regional Tsukuba F Pizza Delivery

問題

重み付きの有向グラフが与えられる。i番目の辺の向きを反転させたとき、1番から2番の頂点への最短路が

  • 短くなる
  • 変化しない
  • 長くなる

のいずれであるかをそれぞれ出力せよ。

制約条件

グラフの辺と頂点≦10万
辺の重みは正整数で10万以下

続きを読む