Sugarel in Love 木の直径ではだめです

Quiz

https://csacademy.com/contest/fii-code-2019-round-1/task/Sugarel-in-Love/statement/

Submit

  • なし

問題

  • disjointなパスの和の最大値

サンプル1

f:id:peroon:20190221204256j:plain

問題の読み間違い

  • バスに乗って長い時間一緒にいたいから、乗り換えはせずにパスは1本だと思い込んでいた
  • なので木の直径を求めたが 23 となりサンプルの解答に合わない
  • コードを書いてdfsを2回したが、このサンプルなら手で直径を求めた方が、すぐに違うと気づけた
  • disjointなpathのセットのコストの和だと気づくと、英文のpathsにsが付いていることにも気づける

学び

  • コードを書いて方針が違うことを確かめるのは高く付く
  • 複数形のsはちゃんと読む

D - Deforestation (nikkei2019_final_d) 🎍

Quiz

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d

Submit

https://atcoder.jp/contests/nikkei2019-final/submissions/4334442

解法

注意点

  • setから消していくとき、L〜Rの値がそれぞれsetにあるか判定すると、全体でO(N2)になってTLE
  • setでfindではなくlower_boundを使う
  • setで消しつつiterator++すれば、iteratorの移動は全体でO(N)回で済む

学び

  • setでのlower_bound, iterator++

C. Palindromic Matrix

Quiz

https://codeforces.com/contest/1118/problem/C

Submit

https://codeforces.com/contest/1118/submission/50243260

解法

  • Nが偶数のとき
    • 各値のカウントが4の倍数なら解ける。対称に置くだけ
  • Nが奇数の時
    • 4個以上ある値を4隅に割り当てる
    • 残りから十字(中央除く)に割り当てる
    • 最後の1つを中央に割り当てる

f:id:peroon:20190220225553j:plain

感想

  • 難しくはないが実装が重い
  • もっと上手く書けないか

似ている問題

https://atcoder.jp/contests/code-festival-2017-quala/tasks/code_festival_2017_quala_c

Coffee and Coursework D1, D2 ☕

Quiz

Submit

解法

  • d日で解けるかを二分探索
  • カフェイン列は大きい順にソートしておき、各日の早いうちに飲む
    • 同じ日の中で後に飲んだカフェインの「効きが弱くなる」
    • 強いカフェインを1日の後半で飲むと減衰の影響を受けてしまう
    • 一方、弱いカフェインを後半で飲むとmax(A[i], 0) なので減衰の影響を受けないため

その他

  • d日に分割したときの「効く」総カフェイン量、累積和とかで高速化が必要と思っていたけれど不要だった
  • 二分探索しているので総計算量がO(N logN)のため

レート

  • 少し下がって1400ちょい
  • コンテスト内に解けるべき問題だった

D - 閉路 abc014_4

Quiz

https://atcoder.jp/contests/abc014/tasks/abc014_4

Submit

https://atcoder.jp/contests/abc014/submissions/4325911

解法

  • どこかをrootにしてdfsでdepthを測っておく
  • LCA (Lowest Common Ancestor)が高速に求まれば、depthの差から閉路の長さは求まる
  • ダブリングで高速に親を辿れるように準備しておく

同じ深さになるまで片方を登らせる

f:id:peroon:20190220040028j:plain

  • depthの差のビットを見れば使うべきジャンプが分かる
  • ジャンプ:2k個上の親までO(1)でたどること

その後、LCSの直前まで上がる

  • LCSまで距離が50あるとしたら、32ジャンプ、16ジャンプ.. と詰めていく
  • 64ジャンプでは飛び越えてしまう(親が同じになる)ので飛ばない

蟻本

  • p274あたりにLCAとダブリングの解説がある

C. Magic Ship (Educational Codeforces Round 60)

Quiz

https://codeforces.com/contest/1117/problem/C

Submit

https://codeforces.com/contest/1117/submission/50138888

解法

  • 二分探索
  • 日数を固定(daysとする)したとき、まず流され、そのあと移動する
  • 流された後の位置とゴールのマンハッタン距離 <= days ならたどり着ける
  • 流されるシミュレーションは累積和で高速に求めればよい

Note

  • テスト5を見ると答えがかなり大きい
  • 二分探索するときのright=1e11では小さすぎて通らず、1e14で通った
  • 答えが最大になる場合を考えてみよう
    • y = 109
    • n = 100000
    • s = "DDD... (1つだけU) ... DDD"
    • この場合、1周して1だけ近づけるので、たどり着ける日は1014日後
    • なのでそれよりも大きい値で行けるか判定し、行けないなら-1と判定すればいい

学び

  • 流されてから移動することで各操作を分離することができる
  • 各問題を見たとき、二分探索で解けないかチェックしてみる

2年ぶりくらいにcodeforcesに練習でトライ。AC

Quiz

https://codeforces.com/contest/1107/problem/A

Submit

https://codeforces.com/contest/1107/submission/50076744

Note

  • cfはテストケース全部見せてくれるっぽい
  • コンテストが終了しているからだろう

感想

  • 正しく英語が読めているかどうか、という壁がある
  • AtCoderで日本語ででも読み間違えることがある
  • とはいえ、サンプルと問題を読み比べていけば分かりそう

なぜコドフォ?

cf 出た

  • https://codeforces.com/contest/1117
  • 2問AC そこまでは4500人が解けている
  • 3問目が解ければ900人以内。解けなかった・・・
  • AtCoderは終了後にすぐ解説pdfが公開されるのがありがたい
  • cfの場合はTwitterで解法をツイートしてくれる人が複数人いるのでそれがヒントになる
  • AtCoderの問題を解ききってからcfに注力する順番が良いだろう