naoya_t@hatenablog

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

AtCoder Regular Contest 099

6/23 21:00〜22:40
2完(oox-)219位
1741→1780 (+39; パフォ2051)
f:id:n4_t:20180623234950p:plain:w400

C - Minimization (300)

  • 必ず1が含まれるし、1に揃えることになる
  • 1が含まれる長さKを最初に叩いて、あとはその左右に連鎖していく
  • 最初にある1は長さKの端で叩くべき?いやそんなことない。全体で叩く数が最小になるようにすれば良い
    • ceil( (N-K)/(K-1) ) みたいな

→AC 6'11''
https://beta.atcoder.jp/contests/arc099/submissions/2719385

D - Snuke Numbers (500)

実験ゲー

  • nと、n/S(n)をdoubleで計算したものを並べて表示して規則性を探る
    • ジグザグしながら増加していく感じ。もうちょい詳しく
  • 大きいほうからカウントダウンして、そこまででの最小になるnを列挙してみる
    • 1,2,3,4,5,6,7,8,9
    • 19,29,39,...,99 // {1-9}9
    • 199,299,...,1899,1999 // {1-19}99
    • 2999,3999,...,28999,29999 // {2-29}9999
    • 39999,49999,...,389999,399999 // {3-39}9999
    • ...

みたいになってるみたい

  • {9-99}9999999999 の後が怪しい

1e15からカウントダウンしてどうなってるか探る。(どうせ末尾は999999999だと思うし1000000000とかでデクリメントしながら)

  • 1e15までの範囲で793個とかある(←本当は792個)… 実験で出てきた数字を埋め込んで先頭N件表示するか

→WA(1)
あれー

  • 見えてきたパターンに従って数を生成するようにプログラムを書いてみたら、埋め込んだ数列と違うところがある
  • 10000000とか入ってる…あ、最初にカウントダウンしたときにそこから始めて、それがそこまでの最小値だから入っちゃってた

というわけで10000000を抜いて(それに気づくために15分30秒+1ペナルティ、で合計20分30秒ロストしつつ)
→AC
[https://beta.atcoder.jp/contests/arc099/submissions/2727798

E - Independence (700)

  • もしもグラフが全結合だったら、M==N(N-1)/2なわけだけど、この場合は任意の二分割を許すので合計が一番少ないところで(半分ずつかな)
  • 全結合でない場合、「繋がっていない辺」が必ずあるのでそれを全部検出しておいて(補グラフ)、それらの辺の両端が{高}と{橋}にそれぞれ(どちらかがどちらかに)別々に属することになるので、それまでにどちらかに入れたやつとの間で全結合しているかをチェックしてから投入
  • どちらにもまだ入れていない頂点はどうする?これ以外の辺は必ず繋がっているんだよね(ここまでで登場していないということは全ての頂点と繋がっているはず)。半分ずつになるようにならして分けたらいい?

ってところまで
→WA(2)
https://beta.atcoder.jp/contests/arc099/submissions/2733338

解説読んだ

はい
補グラフにさらに辺を生やして完全二部グラフ(biclique)が作れるか否かという問題、というところまでは分かってた、けどそれがちゃんと書けなくてWA出した
あとINT_MAX入れるべき所に0xffffffff書いてた(これじゃあ-1じゃん)
【もうちょい頑張る】
あー、「繋がっていない辺」を振り分けていく時に「それまでにどちらかに入れたやつとの間で全結合しているか」では駄目なんだ(なぜならその結合は切断可能だから)…
なので、「繋がっていない辺」(補グラフ上での「辺」)を繋がってる同士でグループ分けして、各グループの白黒反転させたパターンも見ながら組み合わせていってN/2に一番近いやつが勝ちなのね(あーだからDPって言ってるのか)
書き直して
→AC
https://beta.atcoder.jp/contests/arc099/submissions/2738347

個人的ハマりどころ解説

(二部グラフの両サイドを白組・黒組とする)
補グラフにおける辺(元のグラフの「繋がっていない辺」)は白組と黒組を繋ぐ風にしか置けなくて、必ずどちらかの端がどちらかの組に繋がって、そしてそれは既存の辺でクリークを形成するという制約から1通りに定まる、みたいな仮定(最後のが嘘)を信じてしまったので「各組に分配済みの頂点との既存の辺で全結合できるか否か」で組を選んで貪欲に振り分けていって、テストケースは(たまたま)合うけどWAが出るしおかしいなあ、と悩んでいた。

さらに、残った頂点は白組のみんなとも黒組のみんなとも全結合してるから好きな方に入れればいいしN/2に近づくように分配すればいいよね、なんでDPが必要なの?という頭で解説を読んでいて、それ故に「連結成分分解」て何を分解するの?「連結成分」てどれのこと?と分からなくなってしまっていた。

「既存の辺を捨てていく」というより「補グラフで辺を付け加えていく」という観点で見るべきだった。

教訓
  • 補グラフにするときはちゃんと補グラフにする(元のグラフを逆転した論理をその都度考えてるとバグる)
    • 元のグラフで「ある」=補グラフで「ない」and「追加してよい」
    • 元のグラフに「ない」=補グラフに「ある」but「消せない」

F - Eating Symbols Hard (1200)

開いてない