D - Number of Amidakuji abc113_d

Quiz

https://atcoder.jp/contests/abc113/tasks/abc113_d

Submit

https://atcoder.jp/contests/abc113/submissions/4307703

線の引き方はフィボナッチで求まる

f:id:peroon:20190218041415j:plain

  • 例えば4本の場合、線の引き方はfib(5) = 5通りある
  • N本の場合、fib(N+1)通り

例えば左に折れる場合の線の引き方

  • 線を引く場所は1通り
  • その左右1本ずつは線を引けないので1通り
  • 残りのサイドは自由に引いてよいのでfibを使う

f:id:peroon:20190218041452j:plain

D - Static Sushi arc096_b

Quiz

https://atcoder.jp/contests/abc095/tasks/arc096_b

Submit

https://atcoder.jp/contests/abc095/submissions/4307178

Note

  • 解説AC
  • B側に進んで折り返してAまで行く場合をO(N)で解くコードを書く
  • A側で折り返す場合の方は、データを反転させて対応
    • 合計コスト = 2 x O(N)

学び

  • B側で折り返すと固定してコードを書き、もう片方の場合は入力を加工するなどしてコードを再利用する
  • 良い方のスコアをとる

f:id:peroon:20190218021017j:plain

C - Monsters Battle Royale (abc118_c)

Quiz

https://atcoder.jp/contests/abc118/tasks/abc118_c

Submit

https://atcoder.jp/contests/abc118/submissions/4285563

Note

  • できるだけ小さいモンスターを作るゲーム
  • 1番小さいモンスターのサイズで各モンスターのサイズはmodを取って良い
  • 同じサイズのモンスターが複数いても意味がない
    • setに入れる
  • set内のモンスターで削りあって互いに小さくし続ければ良い

イメージ

f:id:peroon:20190216230507j:plain