naoya_t@hatenablog

いわゆるチラシノウラであります

〈AGC埋め〉700点問題(AGC 004 C, 005 C, 010 C, 012 B)

ARCの700が全部埋まったので次はAGCの700を埋める

11/23(金祝)

AGC 004 C - AND Grid

作戦1:
  • 赤:最初全部塗る
  • 青:最初文字のところだけ塗る

で、赤を消しながら、赤を分断しないように最小全域木的に青を繋いでいく

→うまく実装できない…

作戦2
  • 赤:最初全部塗る
  • 青:下から(ないし上から)櫛のように1列おきに刺していく。文字がなければその部分の赤を消す。

文字の部分の紫で繋がっているから赤は分断されないのでは

→3ケースほどWAが出てる

作戦3
  • 赤:一番上の行を塗る。そして上から櫛のように1列おきに塗っていく。
  • 青:一番下の行を塗る。そして下から櫛のように1列おきに(赤と交互になるように)刺していく。
  • 文字の部分は赤青双方塗る

これで赤も青もそれぞれ連結で、かつ文字の部分だけ紫になるはず

→WAを二回ほど食らった(2ケースWA出てる)

一番上と一番下の行を端から端まで塗っていなくて、ちゃんと櫛が繋がっていなかった。
(しつこくWAを食らった2ケース (1_01, 1_03) を見てみたら赤が連結になっていなかった)

修正して
→AC
https://beta.atcoder.jp/contests/agc004/submissions/3643789

解説を読んだ

解説では左から右からだった以外は同じ

DDCC2019予選 D問題

naoyat.hatenablog.jp

11/24(土)

AGC 005 C - Tree Restoring (700)

  • とりま a[] をソート
  • shortest = min(a[])になるノードをrootと考えればいいかな。
    • 左の深さ=右の深さ=shortest, あるいは 左=shortest, 右=shortest-1 みたいな感じ
    • あるいは頂上を2つ取って左右ともにshortest-1とか
  • longest = max(a[])になるノードは2つ以上あるはず
    • 中途半端な位置のノードだと、自分から見た最遠ノードから見て自分が最遠とは限らなかったりするが、少なくとも1つ、最遠ペアになるノード組があるはず
  • longest+1個のノードを1本に並べた木?を考える
    • これでshortest..longestがすべてカバーされる
  • 各ノードから見た最遠距離を求めて、この1本木でその距離がいくつずつカバーできるか数える
    • a[] から距離ごとに消費していく
  • a[] に足りない距離があるならImpossible
  • a[] の側で余る距離がある場合
    • (最遠までの距離がk)のノードが余るなら、(最遠からk-1)のノードにそれを生やせばいい
    • (最短距離のノード)は増やせないので余ってたらImpossible

→WA(1) 33:16
https://beta.atcoder.jp/contests/agc005/submissions/3651820
3ケースだけWAが出てる...

(最短距離のノード)は1じゃなくてshortestで見ないと駄目じゃん
直して
→AC 37:01 (+1penalty)
https://beta.atcoder.jp/contests/agc005/submissions/3651832

自力AC嬉しい(けど700点問題としては易しくない?)

どうでもいいけど、コード中に出てくる sqn は sine qua non(ラテン語「必要不可欠の」)の略。必須条件。

解説読んだ
  • dist(a,b)が木の直径となる時、パスa-b上の頂点について考える
  • 任意のpについて、max(dist(p,1),dist(p,2),...,dist(p,N))=max(dist(p,a),dist(p,b)) が言える

あとは大体同じ。

11/26(月)

AGC 010 C - Cleaning

適当なノード(一番degreeの大きいやつでいいかな)をrootにして、leaf→root方向にまとめていく。

あるノードの数をf、下から来たやつの合計をgとする。
gの中でb組のペアを作ると、gから2bを、fからbを消費し、親ノードへはf-b(=aとする)だけ上げることになる。

  • a+b=f, a+2b=g
    • ∴b=g-f, a=f-b
    • a≧0,b≧0な解がなければNO
  • 親に上げるaも含めて、下から来たやつの最大値が過半数を超えているとペアを組めないのでNO

これをrootまでまとめて行って、rootでa==0かどうかが答え。

→WA
https://beta.atcoder.jp/contests/agc010/submissions/3672206
1ケースだけWAだ
あああ
N=2の場合死ぬじゃん
if (N==2) return A[0] == A[1]; を追加して
→AC
https://beta.atcoder.jp/contests/agc010/submissions/3672234

50分弱かかったけど自力でAC取れた。

解説読んだ

日本語のほうの min(max c_i, Σc_i/2) というのは合わないのでは?
英語のほうは分かる

11/27(火)

AGC 012 B - Splatter Painting (700)

作戦1
  • 操作は時系列的に後のものを先に(Q番目から1番目へ)
    • BFSで塗っていく
    • 訪問済み(=0以外の色でペイント済み)のノードに来たら止まる

これだとサンプル1は合うけどサンプル2が既に合わない…

一度愚直なシミュレーションを書いてみた(ノートに手書きでもやってみた)

例えば、あるノードをrootとして、9個ずつ子ノードをもつ深さ5の木を考えたとき。
M=9^5+9^4+9^3+9^2+9^1+9^0=66430本の辺があり、M+1個の頂点があるわけだけど、
どのノードからも距離10で全ての頂点に到達できてしまうので、
この愚直解だとO(N^2)かかっちゃうんだよね...

作戦2
  • 操作は時系列的に後のものを先に(Q番目から1番目へ)
    • BFSで塗っていくのは同じ
  • 各ノードを訪れた時に、残り距離いくつで訪れたかを記録しておきたい
    • 訪問済みの場合(塗らない)
      • 今の残り距離以上の値で訪問済みなら(塗らずに)止まる
      • 今の残り距離未満の値で訪問済みなら(塗らずに)さらに進む

これで、同じノードを10回以上出発することがないということが保証できる。
最悪ケースとして、各ノードを10回出発することがあるとする。
10(=max(d))×Σ(各ノードからの行き先の数)のオーダーになるわけだけど
辺の数がM(≦1e5)と分かっているのでΣ(各ノードからの行き先の数)=2M が成り立つ。
なので高々20×M回の出発となり、計算量的には余裕のはず。

→AC
https://beta.atcoder.jp/contests/agc012/submissions/3676312
自力で解けた…(けど1時間半かかっちゃっててアウトです)

あるノードを残り距離いくつで訪問したかを 00111111 みたいなビットマスクで書いてるけど距離を表す整数1つでも良かったかな。

解説読んだ

DPで解いてる…

dp(v,d) を「頂点vから距離d以内にある頂点たちの色を塗る」という操作が行われた(操作を逆順に見たときの)最初の時点、とする

最終的な頂点の色は dp(v,0) から何番目の操作によって色が塗られたかを知ることで求められる。

とな。色ではなく操作番号を記録してるのか(それは最初考えたけど自分の解法だとそこまでする必要がなかった)。

英語の方も見てみたけど、こちらは func(v,d) のメモ化再帰で解いてるw