TwitterでGravity Industriesという会社の話が流れてきた。紹介していたのは延々世界の面白ニュースを紹介するだけの面白くなさそうなアカウントだったが、紹介されていた会社自体は面白そうだった。
SF的未来像で「空中移動」はよく出てくるが、実際の現実ではなかなか出てこない。ドローンとかは結構実用化されてきたが。重力に持続的に抗うのはなんだかんだ結構なエネルギーが必要で、移動を目的とすると車輪のコスパになかなか叶わないからだろう。
この動画を見ると人が背に背負える程度の燃料で、それなりの時間人を浮かし続けることが出来ているように見える。なかなか夢のある動画だと思う。
昼頃まで寝てしまった。
スプラトゥーンをした。
ガチマ 2勝1敗
ナワバリ 1勝3敗
散歩をした。近いけれど普段あまり行かない大通りに向かった。
本当に店とかが無く、車が通りやすい大きい道があるだけなので、それで行かなくなったのだと思い出した。
今日解いた競プロの問題。
ARC148-B: もしも全てdならば操作をしないのが良い。pが1つでも入っている場合、そのpを回転すれば少なくとも元のSよりは辞書順で前になるので操作をするのが最適になる。
辞書式順序は前の文字が支配的なので、pが1つ以上入っている場合、少なくとも最初のpはdにしたい。ということは最初のpは[L,R]の範囲に入れなければならない。Lを最初のpの位置に固定し、Rを全探索すれば最適解が求まる。これは$O(N^2)$だが、N≦5000なので解ける。
Lを最初のpの位置に固定してしまっても構わないことのふわっとした証明としては、まず先頭のdの数は最大化しなければいけないはずだと考えられる。ということはすでに先頭に並んでいるdを削る意味はない。例えばもしdd(ddp???ppp)→dd(ddd???dpp)といった感じの操作をするとしたら、Lを右にずらしてdddd(p???ppp)→dddd(ddd???d)としても損をすることがないからだ。
Categories: 未分類