20190602_AGC034/

README

AGC034 感想

1完8ペナ、1900位弱という地獄。

転倒数を勉強するきっかけになっただけ参加した価値が合ったと思いたい。

• A問題
  • 条件をいろいろ考えて場合分けするわけだけど、整理が甘かった。
  • こういうのは厳しいものから前においていく、というのが正しいやり方なのだろうか？
  • 石が2個連続する部分のチェックを、WA出してからなのではなく、最初から分けてやりたかった。
  • 自分が思いついた条件はどれも詰めが甘かったので、最初に浮かんだやつは2重に考え直すぐらいしないとダメなのかもしれない。
• B問題
  • "BC" を "D" と見ると話がシンプルになる、というのを見抜けなかった。
  • 典型: 転倒数
    • これを知らなかったのがそもそも準備不足な気がするし、そもそもAで時間を使いすぎたこともあるので、とりあえずは転倒数の勉強から始める。
    • 転倒数
    • 色々と応用できそう。
  • 典型: 変わらない部分に注目する
    • これぐらいの考察は必要だった。
      • というかしたけど整理する時間が足りなかった気もするが。。

---

転倒数について

参考:

https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion https://qiita.com/wisteria0410ss/items/296e0daa9e967ca71ed6

とりあえずは簡単な例の理解にとどめておく。 （本来、「転倒」という概念は数学的にもっと広範なものらしい。）

数列の転倒数、バブルソート

長さNの数列を考えると、取りうる2数のペアは n*(n-1)/2 通り（N個のものから2つを選ぶ組み合わせ）存在するが、そのうち、

「正しい順序に鳴っていないペアの数」のことを転倒数と呼ぶ。

これは、隣り合う2数の交換を繰り返すことでソートするバブルソートに置いて、その必要な最小回数と一致する。

これを求めるには、

• 自分より右にある、自分より小さな数の個数を、全要素求めて足し合わせる。
• 自分より左にある、自分より大きな数の個数を、全要素求めて足し合わせる。

をすればよい。

しかし、普通にやると O(N^2) となってしまい、低速。

BITを使うと O(NlogN) で求められるらしい。

今回のB問題

今回は O(N) で求められるが、これは実質的に、数が2種類のみの数列における転倒数を考えているから（のはず）。

。。ということは、限られた少数種類のものの列ならば転倒数をほとんど同じ要領で高速に計算できる？

文字列などをひっくり返す操作があったら、転倒数に思いを馳せるのは悪くないかもしれない。