今回は ABCDEF の 6 完(57:17)。F まで順調に解けたので、悪くはないと思う。 ただ全然 G の解法が思い当たらないなぁ。時間があったので考察ができたのは良かった。
条件分岐をミスらないように書く。慎重に見る。
普通の全探索。桁をきちんとあぶり出す。
ソートして尺取りをする。これもバグらないように。
条件に一致するように行ごとに深さ優先探索を書く。 各行のパターンを出すには next_permutation を使った。 各列に bit で abc があるのかどうかを見る。また行パターンの先頭が $R_i$ かをみる。 bit が 0 のとき、初めて入れるので $C_j$ と一致するのか見る。
まあ色々とやって無理やり解法を出した。見つけたら exit(0) で無理やり終了。
どうやら確率の遷移は右に行くごとに $(N+1)/N$ されていくようなので、これと $A_i$ を掛ける。 確率というか、回数の期待値なのかな。よくわからない。実験したら成功したので書いてしまった。
それぞれ $x$ 方向の移動と $y$ 方向の移動が $40$ 個くらいしか無いので、半分全列挙で解ける。 それ自体はそこまで難しくないが、データを合わせて、左に曲がったか右に曲がったかと言うのを きちんと復元しておく必要がある。
正方向に進んだか負方向に進んだかの bit を全列挙データに持たせておけば、正負の復元はそこまで難しくない。 そのあと、データを交互に織り交ぜて、右に行ってたのか左に行ってたのかを復元する。
分からない。$i$ のスキルだけでアチーブメントを達成すると一回考えて、 レベルを上げてもコストのほうが大きくなるような場合、レベルを上げなくてよくなる。くらいしか考えられてない。 でもこれって結局本質的な解に至るための解法でないような気がする。
二分探索も考えたが、特に式が簡単になりそうもないような気がする。どうするんだろう。
G みたいな問題は、いつか解けるようになるのか。それは後になってみないとわからないが、 Solver 順のやつで問題を解くのに詰まってきたら、他の方法も少し考えないとなとは思っている。 でもこういうのは自力でACしたいよなぁ。今回も言って 40 分くらいしか考える時間なかったし。 こういう問題を考えて解けるようにするのは、コンテスト中だけではない。何時間かかければいい。
Perf=2400 だ。久しぶりに取れた。まあ、これは結果として受け取っておくとして 単純に問題を解くのを楽しんでいきたいとは思っている。
(2023/10/28 23:06)