今日解いた競プロの問題。

ARC152-B: 自力AC。こういうのがある程度すんなり解けるようになっているので、ARCの問題傾向に少しずつ慣れてきているかもしれない。

単純な往復を考え、横軸を時間、縦軸を位置にとってグラフを書くと、三角波のようなジグザグなグラフになる。2人が往復を行うので、位相のずれたジグザグが2つ描かれることになる。

ここからが問題。問題の条件から、位置がどれかしらの$a_i$となる場所でしかグラフは交差できず、待ち合わせを行う必要がある。また、t=0においてどちらのグラフの位置もどれかしらの$a_i$でなければならない。1周期で最も待ち合わせの時間を少なくできるような位相の設定方法を求めたい。

まず、t=0では両者とも同じ位置で良い。1周期あたり必ず2回すれ違うので、その内の1回は端点にしてしまえば考えるのが楽になる。これで損をすることはない。これは二人とも同じ休憩所から出発してそれぞれ東と西へ歩くことに相当する。

あと考える必要があるのは「どこを出発地点にするか」と「どこですれ違うか」だけだ。それぞれの位置を$a_i$、$a_j$とおくと、これは図を書いてみれば分かるが、かかる秒数は$2\max(a_i+a_j,2L-a_i-a_j)$になる。従って$i,j$の組み合わせを全探索すれば$O(N^2)$で解ける。

これではTLEなので高速化する。$a_i$を固定したとき、上の式が最小になるのは$a_j=L-a_i$となるときなので、各$a_i$に対して$|L-a_i-a_j|$が最小になる$a_j$を二分探索や尺取り法で探せば$O(N\log N)$もしくは$O(N)$で解ける。これでこの問題が解けた。

---

大学で講義に出損ねて凹んでいる。時間割が変則的になっていたり直前に授業連絡が来ているのを把握しておらず、気付いた時には遅かった。

メールだと重要な連絡をちょいちょい見落としてしまうのはなぜだろう。いつでも見返せる必要があるような重要なメッセージとその場限りの重要でないメッセージが混交してしまうのが問題なのかもしれない。ちゃんと整理していればそういうことは起きないのだろうが、そんなに楽しい作業ではないし、コストが高い。

---

最近集中力が本当にひどくなってきて、気が付くと同じサイトを何度も見ていたり、日常語彙がスッと出てこないことがあったりしてやばいなと思ったので脳トレを再開した。やらないよかマシだろう。

あと何やればいいか。読書とかも良いイメージがあるが、本によっては今一つ頭を使ってる感が出ない。頭をちゃんと回すという意味では、簡単すぎるやつや理解が厳しいやつを避けるのが良いと思うのだが、そういう本を見つけ出すのは難しい。

登場人物に共感できる小説、問題意識の共有できる論説文などを選ぶのもいいかもしれない。ただ、最近何かを調べたい欲求みたいなのが薄れており、その方面のやり方も厳しい。

色々頭をすっきりさせる方法を考えた結果、とりあえず散らかっている部屋を片付けることにした。洗濯物の山をしまったら多少気分が晴れた。