No.411 昇順昇順ソート

Quiz

https://yukicoder.me/problems/no/411

Submit

https://yukicoder.me/submissions/341357

サンプルを理解する (N=5, K=3) K!=1の場合

f:id:peroon:20190421161636j:plain

  • 一般的であるK!=1である場合を考える
  • 下がる時に使う数字は1固定となる
  • サンプルのようにK=3のときは、下がる前にK+1〜Nまでの数字を使うかどうかの自由度がある
    • 数字の数は N - (K+1) - 1 = N-K 個
    • 今回で言えば 4, 5を1で下げる前に使うかどうかの自由度がある
    • 22通り
  • そこからは1で下がって、残りの点で上がるので1通り
  • よって一般に、2N-K

K=1の場合

  • サンプルとしてN=5, K=1を考えてみよう
  • 今回は 2, 3, 4 で下がることができる
  • 2で下がる時、下がる前に3, 4, 5のいずれかが存在する必要がある
    • 下がる前に3だけ使ってもいいし、3, 4, 5すべてを使ってもいい。3, 4, 5全てを使わないのだけはダメ
    • よって、余事象より、上記の組み合わせは23 - 1
  • 3で下がる時、下がる前に4, 5のいずれかが...(以下同様)
    • 組み合わせは 22 - 1
  • 4で下がる時、〃
    • 組み合わせは 21 - 1
  • これらの和が答えで、7 + 3 + 1 = 11 が答え。
  • 一般に、2N-1 - N となる

f:id:peroon:20190421165054j:plain

構文解析

Quiz

https://yukicoder.me/problems/no/49

Submit

https://yukicoder.me/submissions/340022

参考

経緯

  • たとえば 1234+5678
  • 最初の数字1234は読めたとして、+も読めたとして、5678はまだ読んでいないので+を評価(解決・計算)することができず「おや、これは見た目より大変そうだぞ?」と思っていたところ、上記の構文解析の説明を読むことができた
  • とてもスマートに解決していてすごい

他の問題

No.701 ひとりしりとり

Quiz

https://yukicoder.me/problems/no/701

Submit

https://yukicoder.me/submissions/339984

解法

  • a????a をN-1回出力し、最後はanで締める
  • ????の部分は26進数で列挙すれば衝突しない
  • 264 > 100000なので ???? は長さ4で十分

学び

  • N=1000などの大きい時にサーバ側でWAになっていた
  • 大きい値でもエラーにならず回ることを確認してから提出しよう

No.74 貯金箱の退屈

Quiz

https://yukicoder.me/problems/no/74

Submit

https://yukicoder.me/submissions/339953

解法

  • 1枚だけでflipできるコインを調べておく
  • 2枚flipのとき
    • a, bを一緒にflipできるなら、Union Findでunite(a, b)しておく
    • 「一緒にflipできるグループ」ごとにまとまることになる
  • それを全てのコインについて回した後は、いくつかの木がある
  • 木ごとに、全部表にできるかチェックする
    • 木の中で、裏の枚数が偶数ならOK (2枚ごとflipできるため)
    • 裏の枚数が奇数であっても、木の中に「1枚だけでflipできるコイン」があるならOK

感想

  • Union Findの応用という感じで楽しかった

No.416 旅行会社

Quiz

https://yukicoder.me/problems/no/416

Submit

https://yukicoder.me/submissions/339563

解法

  • 破壊される辺以外を張っておく
  • 破壊クエリを逆から読みながらその辺を復活させていく
  • 木がつながったかはUnion Findで管理する
  • 辺を繋げる前に、今回の接続で初めて「点1とつながっている木」「点1とつながっていない木」が接続されるなら、それは破壊で通れなくなった日である
  • 「点1とつながっていない木」が隔離される日がわかったので、「点1とつながっていない木」のノード全てをdfsで走査して、日にちを書き込む

参考にしたもの

  • 公式解法
  • はむこさん

サンプル1

f:id:peroon:20190418115508j:plain

セグメント木 再訪

Quiz

https://atcoder.jp/contests/arc033/tasks/arc033_3

Submit

https://atcoder.jp/contests/arc033/submissions/5012167

解法

  • 「X番目の値」をlog(200000)くらいの高速で見つける必要がある
  • セグメント木を使う
  • 各値のカウントを持っていて、[0, 指定の値) までのカウントの和を返すように作る
  • それができれば二分探索を用いて「X番目の値が何か」が求められる

資料

感想

  • 4ヶ月前くらいにセグメント木は1度作っていたが、苦労して書いた印象
  • 今回はそれを少し改良して使っただけだが、理解のUPを感じる

今後の課題

  • 遅延評価セグメント木