Shift vs. CapsLock（Atcoder）
t6o_o6t.icon
貪欲法？
例えばCapsLockがOffのときで、Aを押す場合
CapsLock（Zms） + aを押す（X ms）
一度CapsLockを押すというのは、その後のShiftを一掃できるということ
CapsLockを押したほうが早くなるケースがある
CapsLockを押す + 文字を入力（+Shift） + CapsLockを押す
これが、Shiftのみにする場合よりも遅いときとは
ある区間でCapsLockはOFF、大文字の個数を$ a、小文字の個数を$ bとする
CapsLockありのとき
$ Z + (a + b)X + bY
Shiftのとき
$ (a + b)X + aY
つまり、CapsLockのほうが早くなるのは、 $ Z + bY \lt aYのとき
CapsLockをどこでオンにし、オフにするのかを考える問題だ、これは
CapsLockの方が早くなる区間が途中から来る可能性もある？
今回制約上、難しい探索をさせようとしているわけではなさそうだが
どう区間を取るかが問題
有利に区間を取る方法があるのだろうか？
aaAaAaaAAAAaAaaAaAAaaaAAAAA
CapsLockという操作は対称ではない
aaA
ここだけを見ると、CapsLockが速い条件は$ Z+2Y < X
aaAaA
ここを見ると、CapsLockを押していない場合、CapsLockが速い条件は$ Z+3Y<2X
CapsLockを押している場合はこの条件式が逆転する
$ Z+3X<2Y
AAaAの場合
なぜ例題の順番が最短なのか
検証したいこと
前から見ていくのが最短か？
X = 1, Y = 3, Z = 3
AAaA
A
大文字1個。
$ Z < Y
$ 3 < 3は成り立たないから、CapsLockはしないほうがいい
AA
大文字2個。
$ Z < 2Y
$ 3 < 6は成り立つから、CapsLockしたほうがよい
AAa
大文字2個、小文字1個
$ Z + Y < 2Y
$ 3 < 3は成り立たないから、CapsLockしないほうがよい
AAaA
大文字3個、小文字1個
$ Z + Y < 3Y
CapsLockしたほうがよい
先頭から、
1. CapsLockする
2. aを押す
3. aを押す
4. Shift+a
5. a
A, AaA
Aの区間
CapsLockしないほうがよい
AaAの区間
したほうがよい
なるほど、区間を定める際には条件式を評価するが、これはメモできる
区間に含まれる大文字と小文字の数が定まれば一定
順番は無関係
文字列に対して、CapsLockのON/OFF状態の区間を与えると、かかる時間は一意に定まる
特定区間について、時間は以下の式になる
CapsLockしたときの時間は、以下のように求まる
と思ったが、式を共通で良い
したがって1つめ
特定区間に存在する大文字と小文字それぞれのカウントを最小時間で取得できる
区間における大文字小文字の出現回数をセグメント木に格納する
2つめ
CapsLockがONになる区間で探索を行う。
どの区間をCapsLockをONにすべきか
区間1（OFF）
AAaA
区間2（ON）
AaaaA
これはaAAAaに置き換えて良い
区間3（OFF）
...
数値化すると部分和を使える？
OFF区間
AAaaaaAAA
これは110000111
Shiftを押す文字を1とする
ON区間
反転させる。
001111000
時間計算
$ X × n + Y ×m + Z
全体区間
AAaaaaaAAAaaaAaA
部分和配列
Y
2Y
X+2Y
...
5X+2Y
[1:5]を取る
Aaaa
部分和
1の1つ前ははY
5の1つ前は3X+2Y
区間和
3X+Y
反転するには
無理だな
セグメント木にする。
AAaaaaaAAAAaaa
セグメント
区間内のAの個数を格納する。
区間の探索
$ O(n^2)になる
$ \mathrm{len}(S) \le 3×10^5だった
$ 9×10^{10}、間に合わない
今回良かった点
セグメント木を用いる発想が膨らむようになった
できなかった点
しかし、慣れる前は色々考察してしまうと思う。たとえば、XがYよりも極端に小さいときは、'a' と 'A' の変わり目で CapsLock キーを押すといいんだろうなとか。
まさに。
動的計画法を手札として使えていないということだから、まずは順番通り、動的計画法から理解するのがよいだろう。
次回課題
蟻本を元に、動的計画法を学習する。