今日解いた競プロの問題。
ARC150-B: 昨日の夜から考え続けてやっとACした。ARCの問題傾向慣れなすぎ。
問題文の状況を数式にすると$B+Y=n(A+X)$みたいな感じになる。XとYのどちらかを固定して考えたいが、Xを固定してYを考える方が楽っぽい。
YをXで表すと$Y=-B+n(A+X)$になる。Xが固定ならYは最小化したい。$Y\geq 0$という条件から考えると$Y=(-B)%(A+X)$が最適になる。これで$X+Y=X+(-B)%(A+X)$という風に目的の数を$X$の関数として表せたので、$X$を変化させて$X+Y$の最小値を求める。
グラフを書いてみると分かるが、$(-B)%(A+X)$は部分的に見ると単調増加で時々がくっと下がるようなグラフとなる。この下がった瞬間だけを拾っていくと良さそうな気がする。
この下がった瞬間は数式的にはなんなのかというと、$Y=(-B)+n(A+X)$と表したときにこのnが下がる瞬間である。$A+X=B$のとき必ず$Y=0$かつ$n=1$であって、これより$A+X$を大きくしてもnが下がることはないので、$A+X\leq B$と計算すべき範囲を制限できる。
さらに下がる瞬間を数式的に考える。正直これの厳密な議論は自信がないのだが、$Y=0$と置くと良い感じに考察できる。離散の世界だと下がる瞬間でも必ずしも$Y=0$にはならないが、連続の世界のmodを考えると下がる瞬間で必ず$Y=0$になる。これを捉えるということになる。連続の世界といってもmodである以上$n$は離散値をとる。$Y$や$A+X$を連続値として置いた場合という話である。
$Y=0=(-B)+n(A+X)$
$B=n(A+X)$
このように変形すると、$n\leq\sqrt{B}$もしくは$A+X\leq\sqrt{B}$のどちらかが必ず成り立っていることが分かる。$n$も$A+X$も実際には離散値なので、この$\lfloor\sqrt{B}\rfloor$通りの$n$と$A+X$を$X\geq 0$に気を付けつつ全探索すれば良い。コーナーケースとして、下がった瞬間ではないが$X=0$が答えになる場合もあるのでそこだけ注意。これで1ケース辺り$O(\sqrt{B})$で解けた。
負の値のmod、割る数側を変えるmod、連続の世界のmodと応用的なmodの取り扱いをいやというほど要求された。
Maixduinoの実験を進める。K210とESP32のSPIがどうも安定しなかったが、なんか色々いじってみたら安定した。何が決定打だったのか、昨日の不具合は一体何が原因だったのか結局分からなかった。
K210のIO8とESP32のENピンが繋がっており、リセットをかけられるようだったのでK210のプログラム実行時にESP32をリセットするようにした。具体的には
- LOWにする
- 500ms待つ
- HIGHにする
- 800ms待つ
- IO8を入力ピンにしてHI-Zにする
単に下げてまた上げるという普通のリセット処理だ。500ms、800msという数字はここから取ってきている。というかここの処理をまんま参考にしている。
最後にHI-Zにしているのは、USBシリアルからESP32にリセットをかけられるようにするためだ。Maixduino基板において、ESP32のENピンは以下の3つに手綱を握られている。
- K210のIO8ピン
- CH552(USBシリアル変換器として動作)の出力するシリアルRSTピン
- 10kΩ抵抗によるプルアップ
K210が自分の手綱を離さなければシリアルからのリセットはできない。ESP32に書き込もうとして出来ないことに気付いて問題が発覚した。ちゃんと最後にHI-ZにすることでESP32に書き込めるようになった。
秋葉原に行った。秋月が18:00で閉まっていた。前は18:30までやってたのに。
筋トレをやった。今日は腕立て。前回の筋肉痛がまだ治まりきってないが、完全に治るまで待つ必要はないという話を前に聞いたので決行。一応前回よりも同じことを楽にやれてる感触があった。
Categories: 未分類