ABC163バチャ参戦

競プロ

「ABC163は日曜日夜にちゃんと出るぞ!」と思っていたら寝過ごしました。アホですね。

「は～～こんなんどうやって手ぇ付けろっちゅうんねん」っていう問題たまにあるじゃないですか。そういう問題の解答を思いつくまでの脳内実況あってほしいなって僕いつも思ってるんです。そういうわけでこの記事を書いてます。誰かに役に立つといいね。

A - Circle Pond

  • 円周=2×半径×円周率 ちょっと誤差が怖いけど、πを長めに直書きして、setprecision(12)して小数点以下12桁ぐらい出力しておけばまあ大丈夫でしょう

(一回提出時の言語選択をミスって1CE食らいました。みんなは気をつけような。)

atcoder.jp

B - Homework

  • 結局宿題全部やるのには\displaystyle{A _ {1}+\cdots+A _ {M}}日かかるので、これがNより大きければ無理ね
  • 空いた日はNから引けばいいか

atcoder.jp

C - management

  • 木じゃん で「社員番号1以外には上司がいる」ってことは社員1が根ね
  • 直属の上司が木で言う親で、直属の部下は木で言う子だね いつもみたいに自作の木のクラス持ってきて構築すれば...
  • や、求めるだけでいいのね なら自分が出てきた回数が子の数ってことでvectorでカウンタ持っとけばおｋ

atcoder.jp

D - Sum of Large Numbers

  • すげえでかい数字来たな
  • とりあえずk個だけ取った時の和の個数はどうなるかな?
    一番小さい和が\displaystyle{\sum _ {i=0}^ {k-1}(10^ {100}+i)=k\times 10^ {100}+\frac{1}{2}k(k-1)}で、
    一番大きい和が\displaystyle{\sum _ {i=N-k+1}^ {N}(10^ {100}+i)=k\times 10^ {100}+\frac{1}{2}k(2N-k+1)}か
    でもってこの間の数は全部とれる(昔似たパターン見たからパッて出た)から、\frac{1}{2}k(2N-k+1)-\frac{1}{2}k(k-1) (☆)通りね。
  • これは10^ {100}が大きすぎて、kでの和の範囲とk+1での和の範囲がかぶることは絶対ないね(kは高々10^ 5程度なので二乗しても10^ 10)
    ということは(☆)を素直にk=K～N+1で足していけばよさそう

atcoder.jp

E - Active Infants

  • え、これ一回読んだけど、手でやる方法すらわからん、どうすりゃいいんだこれ 大きい数字を遠くにやった方がいいことしかわからん

  • 先にF読んじゃお～～(Fへ)

F - path pass i

  • 「色kの頂点を一度以上通るような単純パスの数」、だったら逆に「一度も通らない単純パスの数」を求めたいね
  • 単純パスって結局、はじめと終わりで一通りになっちゃう ということは単純パスの数って結局、端点になりうる頂点の数から求められる まずはそれが求めたいね
  • まず線状の場合は?

  • (ぐじゃぐじゃ～ってしてるやつらは同じ色)ぐじゃぐじゃの間に4つ頂点があるから、4C3+4で10通り

  • この場合は?...ぐじゃぐじゃの間には色なし頂点が6つ...6C2+6で21通り、この「6」を楽に求めたいなあ
  • この6は「一番上のぐじゃぐじゃの部分木の要素数」から、「それ以外のぐじゃぐじゃの部分木の大きさ」の和+1を引けば出るな

  • いやいやそこまで話は単純じゃないぞ!...例えばこういうとき↓は外側の青の分だけ引かなきゃいけない

  • これはどう判別させればいいだろう...今のパターンは「一方のぐじゃぐじゃが、もう一方のぐじゃぐじゃの孫になってる」パターンか...
  • これはもしかして、「同じ色のやつらを木にして、直属の子の分だけ引く」でいいのではないだろうか
    つまり頂点vの(全体の木での)部分木のサイズ数をs _ vとすると、頂点vでの求める数 = s _ v -1-\sum (s _ {自分の色の木での子})っぽい

  • こうなったらBFSで色ごとの木を作ろう
  • まずは全体の根からのBFS 頂点vの「色ごと木」での親は?...自分と一緒の色で、一番最後に来た頂点
    ->色ごとにstackを作ればいいのでは?
  • こういうBFSにするか:
    • 木の配列vector coltree(N),vector colstack(N),部分木の大きさを保存するvector subtree(N)を用意
    • void bfs(v){
    • LL mycol = vの色
    • 色ごとの木coltree[mycol]に新しい頂点を追加
    • 親はcolstack[mycol].top()
    • (全体の木での)子にbfsを回し、加えてsubtree[v]を求める
    • LL d = subtree[v]-1-subtree[色ごとの木でのvの子]として、ans[mycol] += dC2+d

    これで終わりや!

  • ダメでした。こういうパターンでこの計算すると、一番上のぐちゃぐちゃを通ることを許してしまいます

ということは、各頂点vについて、

  • 全体木での各子頂点chについて、

    • LL d = subtree[ch]
    • chに含まれ、かつvの属する色ごとの木でのvの子頂点tchについて、d -= subtree[tch]
    • ans[mycol] += dC2+d

みたいなことをしないといけない

  • (ここで実装が死にました。最悪な実装をしています。同じことをしていてもっとまともなコードはじき上げます) atcoder.jp

E - Active Infants(再)

  • 例1を見てみる:A = {1,3,4,2}
  • 大きい活発度のやつから遠くに移していきたいよね...例えば4を0番目、3を3番目、1を2番目、2を1番目に送るとどうなる?最大になってくれた
  • 例2も見てみる:A = {5,5,6,1,1,1}
  • 大きい奴から順に、遠く遠くに移してみる:{1,1,1,5,5,6}
    でもこれだと合計57,残念1足りない
  • これ最大パターンはなんだろう...初めに6を一番左に移したらできた、{6,1,1,1,5,5}らしい
  • 大きいのから移していくとしたら、確かに左か右のどちらかに移していくのがベストだな
  • これでとりあえずN!通りから2N通りになった...?(当然まだ足りない)
  • 活発度たちを、元の場所を持たせたまま昇順に並べ替えます 後ろの方から動かします
    するとn番目を見るときは、端から埋めていくので左右合わせてn個が埋まっているはず この左右の埋め方はn通りぐらい
    ->n=0～N-1でDPしても、出てくる状態はN×N程度しかなさそう
  • 一度求めた状態はmapで持っとくことにしよう(どうせlog Nが付くぐらいなので)
  • すると次のようなdpができそう:
    LL dp(LL n,LL s,LL e){ 左が0～s,右がe～N-1埋まった状態で(活発度降順で)n番目を動かすときのmax
    ①n番目をs+1番目に動かす場合
    今までdp(n+1,s+1,e)をしていなかったら、やってmapに記憶しておく
    この結果+(n番目を動かした分の利益)
    ②n番目をe-1番目に動かす場合
    今までdp(n+1,s,e-1)をしていなかったら、やってmapに記憶しておく
    この結果+(n番目を動かした分の利益)=d2
    d1とd2のおっきい方返す
    }
  • 通りました うれしいね

atcoder.jp

〆

これやる意味あるんですかね まあ気が向く間やればいいさ