最終更新: 2024-07-12T00:35+0900
いつもの前置き：提出先は AtCoder だけど問題は AtCoder の作成ではなく JOI で、だけど競プロカテゴリを意図して AtCoder タグを付けています。
しんどかった。BC 問題を読むのは気が向いたときにして、A 問題についてだけ書く。
４種類の論理演算(! & ^ |)と、かっこと、ある値を境にして真偽が切り替わる関数から成る式の値について、クエリに答える問題。式の長さが 1M 文字以下で、クエリとして与えられる値の数が 200K 個以下。つまりどちらもとてもでかい。
クエリを昇順に並び替えたら、入力値との比較で真偽が決まる関数というのは、一度だけ false から true に値が切り替わる関数になる。更新頻度が (関数の数)×(クエリの数) から (関数の数) に減る。
以上の２つのアイデアというか願望に基づいて最初に書いたのが次の提出
関数を class で置き換えて、そのクラスに演算子を定義して、式全体の評価を eval で行うお手軽な実装。
eval であるか *.rb ファイルを実行しているかに関係なく、大きな式を評価しようとすると Ruby は黙って異常終了する。式の形によっては終了する前に nesting too deep (SyntaxError) というエラーが出ることもある。p 1^1^1^1^1^...^1 という 1 か 0 を表示するスクリプトをコピペで膨らませて実行すると、Ruby のバージョンと Windows でのスタックサイズに左右されるんだろうけど、手元では 7 KiB を超える前に何も出力されなくなった。
両極端の例を挙げると、1+2+3+4+5+6+7 という式を [+ [+ [+ [+ [+ [+ 1 2] 3] 4] 5] 6] 7] と解釈するとき、(1+(2+(3+(4+(5+(6+7)))))) という式を [+ 1 [+ 2 [+ 3 [+ 4 [+ 5 [+ 6 7]]]]]] と解釈するとき、階層が直線的に増えていく。
中置記法とかっこの存在が式の扱いを難しくしている。
変換アルゴリズムがうまく書けなかったので、検索してトップに出てきた「逆ポーランド記法入門２｜中置記法から逆ポーランド記法への変換」というページを参考にした。
うまく書けなかった部分、求めていた答えがまさに「演算子を全てpopして」と与えられていて喜んだのだけど、あとになって答えが合わない原因が「全て」にあることがわかった。上のページで扱っている四則演算のように、演算子の優先順位が１位と２位の２つだけなら「全て」で正しい。それより多いなら、「これから入れようとする演算子よりも優先順位が高い演算子を pop できる限り全て」が正しい。日本語の説明と Python の実装例に齟齬はなかったので、日本語だけの問題ではないみたい。その一部分を除けば文章だけでアルゴリズムの全体像がイメージできるわかりやすい説明ではあった。
これで RE は解消するけど TLE はなくならない。むしろ eval を呼び出してインタープリタに丸投げすることができないぶん遅くなる。
例えば [1]^[2]^[3]^[4]^[5] という１つの式があって、クエリが 10 だったとする。最初は全ての関数が false で、クエリの昇順に true に切り替えていく。10 が最小のクエリなら、1 から 10 までの関数を順番に true に切り替えていくのだけど、その過程でこの式は false>true>false>true>false>true と値をチカチカ切り替えていく。もしこの式の全体が別の式の一部分であるなら、それら外側の式も同時に連鎖的に値を切り替えていくことになる。
更新の伝播を階層ごとに一旦ためておいて、深い階層から足並みを揃えて各項につき１度だけ値を更新しようとした。その過程で更新と更新が重なって更新が消えることも期待できる。ただまあ、これは根本的な解決策ではなく、効果がある入力もあるかもね、というレベルの対策にすぎなかった。TLE はなくならなかった。
演算子の優先順位を考慮して、| ^ & の順番で、もっとも真ん中にある演算子で分割する。
たとえば [1]&[2]&[3]&[4]&[5]&[6] という式なら [& ([1]&[2]&[3]) ([4]&[5]&[6])] と分割する。
たとえば [1]&[2]&[3]&[4]|[5]|[6] という式なら [| ([1]&[2]&[3]&[4]) ([5]|[6])] と分割する。
ところでこの分割は同一階層内でしかできないので、[1]&([2]&[3]&[4]&[5]&[6]) の分割結果は [& ([1]) ([2]&[3]&[4]&[5]&[6])] になる。かっこを無視して分割してしまうとあとでどうくっつけていいかわからないので。
かっこに制約されるということで、更新が影響する範囲を対数レベルに抑えて TLE を解消する助けにはならなかった。
なぜか抵抗があって考えないようにしていたのだけど、TLE 続きでなりふりかまっていられなくなったので、結合法則を使う。実は対策３でももう使っている。
「なぜか」っていうか、左結合だと問題に明記されていたから、それを無視するのはずるであると、理性ではなく感情が訴えるのだ。答えが合いさえすれば何をしてもいいという教育は受けていない。たぶんそういう理由。問題の解釈が曖昧にならないように出題者が左結合だと定義するのはわかる。交換して答えが変わらないのを見抜いて利用するのが解答者だというのもわかる。だけど無意識が抵抗している。まあいいや。
中置記法の式はかっこがあってややこしいので逆ポーランド記法の式を操作する。
たとえば 1+2+3+4+5+6 を逆ポーランド記法に書き換えると、1 2 + 3 + 4 + 5 + 6 + になるのだけど、演算順序をいじって 1 2 3 4 5 6 + + + + + に書き換えたい。
そうすると何が嬉しいか。演算子に由来する階層を取り去って [+ ([1]) ([2]) ([3]) ([4]) ([5]) ([6])] と解釈することが容易になる。次にこれを６項演算として扱うこともできるし、２項演算のまま引数列を半分半分にしていくこともできる、半分半分にするということは、セグメント木のようにきれいで効率的な階層が作れるということ。
正しい方向に向かっていることを予感させるけど、１パスでやろうとして十分にマージできなかった。
たとえば次の式の書き換えを考える。1 2 + 3 + 4 5 6 + + +。参照範囲が限定できるので予め連続する演算子を結合しておくと便利。1 2 + 3 + 4 5 6 +++ になった。左から読んでいって最初の + 演算子に出合うとき、右の要素が被演算子(3)でその次の要素が + 演算子なら、順番を入れ替えて 1 2 3 ++ 4 5 6 +++ にできる。しかしこれ以上の結合ができない。被演算子もまとめておくとひとつ飛ばすだけで +++ にアクセスできる？ だけど 4 という項は 2 2 * という演算子を含む３項として存在していることもありますね。
対策４とやりたいことは同じなんだけど、今度はうまくできた。演算子に行き当たったとき、スタックから取り出した２つの値(a, b)を即座に [op a b] としてスタックに戻すのではなく、a、b が単独の値か何らかの演算の結果なのかを調べて可能ならマージして、できるだけ階層を増やさないようにした。そしてそれが最後でもなく、スタックから取り出されてまたマージされることもある。
これの 92 行目から 107 行目のあたり。
2K オーバーの長大なスクリプトになってしまった。絶対もっと短く賢く書けるはずでしょ。