ARC109-C, D

C++ competitive programming

久々に出ました。ARCなので解けて1~2問。
面倒なので今後は ∈は e と書くことにしようかなぁ。
(集合の記号などは簡単に出せないので面倒この上ない) ブログ書くのも久々なんだけどちょっと時間空くとHatena書きにくくて仕方ない
断っておくと、正確性よりもとりあえずやる/続けられれば続けることを重視することにしたので、変な文があればコードみるなり他の人の解法を見るなり視野に入れてほしい
なるべく誰が見ても分かるように、みたいなやる気はもうないので。

ARC109:atcoder.jp

A:

A - Hands

まとめ？

  • 面倒そうな問題
  • グラフと解釈できるだろうからDFSやBFSでも解けそう
  • *FSは面倒だしそれなしで解けるだろうから手元に図を書いて考えて解いた

解く

  • まず問題文から a==b || a== b+1 のときは 答えが x
  • 次 a < b と a > b + 1 のケースをそれぞれ考える
  • どちらのケースでも 定数 C ( e Z ) を使って a = b + C と捉えると x, y, c の式で2経路のコストが算出できる のでそれをコードにする

submitted : https://atcoder.jp/contests/arc109/submissions/18455018

B:

B - log

まとめ？

  • 1WA 1AC
  • 式考えないとだめっぽいので書くものと書かれるものを用意する
  • 二分探索久々過ぎて思いつくのも実装もちょっと時間かかった
  • (1)の式で n+1 => n のミスがあって 1 WA
  • 何気に点じゃなく範囲を求める2分探索のほうが需要ありそうなのに書いたこと少ないかも…？

解く
問題文読んだ感じでは

  • 長い方から n 本選ぶ（ つまり 2～n+1 ）
  • n+1 の木をバラしていくつの木の代わりをできるのか/節約できるのか考えれば良さそう
  • 余り部分は捨てても良いのでn+1で考えて良い
    ( 捨ててダメでも余った分 R だけ 短い木をバラす対象とすればいいだろうし問題なさそう)
  • 買わずに済む木の本数が多い方が良いので、木が短い方から貪欲に選べば良さそう

木を何本節約できるか出す

  • より短い木の分からn+1の木を伐り分けていくと考えると n+1 - x * (x+1)/2 >= 0 が成り立つ最大のxが分かればいい？
  • 適当にループ回してx 探すと TLEで死ぬっぽい
  • 線形探索で探すとまずそうなので二分探索してみるか
    x * (x+1)/2 <= n+1 < x+1*(x+2)/2が成り立つ x を見つければいい？(1)

出せたらn+1-x 出力しておしまい

submitted : https://atcoder.jp/contests/arc109/submissions/18467543