JOI問５問６を解説しつつ理解する記事

題名のとおりです。

やってみましょう。
※問題文はJOI公式サイト参照

問５

とりあえずメインは座標圧縮です。
数えるときに累積和（imos法）使ったり、オーダー的に全く問題ないので愚直にやったりするところがわかれるぐらいでとりあえず座標圧縮さえできていればできるのかな・・・（出来ない勢だった）

で、座標圧縮。
正直理解した今ではなんでこんなものがわからないんだろうとか思ってました。で、原因考えてみたの。。。
そしたら結論はこうでした。

蟻本の例題が理解に適した単純問題でない！！！！

というよりあんまり今回の問５みたいな問題が無かったからでしょうがね、まぁようするに蟻本の例題と比べたら圧倒的に理解しやすい座標圧縮というわけです。
方法は簡単で

座標をx,y,zごとにわけてソート（この時ソート前の値は必ず持っておく。mapを利用するのが一番楽）
ソート順に番号をつける

これだけです。

今回はここから足せばいいだけなので、累積和（imos法）で工夫してやってもいいしそうでなくても座標の種類がたかだか2*N個しかないことからO(N^4)ぐらいで単純に当てはまる領域に足していってもいいです（見た感じ後者のほうが圧倒的に簡単）

足したらあとは元の座標で計算しなおします。今回の場合は番号に対応する座標をあらかじめもっておき、k個以上が存在する領域の体積を足していけばいいわけです。

さて、実は普通に簡単だったのでさらっと理解しながら解説していったわけですが、今回snukeさんとkagamizさんのコードを比較して、これをするにあたって実装上注意しなければいけないことが見つかったのでそれも最後に紹介します。
それは座標圧縮に関してはvectorとmapを有効活用しなければならないということです。
snukeさんは単純な配列、kagamizさんはSTLを使っていたわけですが、単純な配列もメモリという観点ではいいかもしれませんが、問題がkagamizさんの解法に比べて難化している印象をうけました。
実際vectorとmapを使えば配列のサイズ、値の持ち方、その他もろもろのことを気にしなくて済むので単純なコードですっきりと実装できています。

とりあえず大きな値をアドレスに使いたい配列→mapを使おうという発想は座標圧縮だけでなく必ず身に着けておきたい発想ですね。

問６

問６はbitDPです。問題の解法のポイントとしては「６つ前までの移動手順を覚えておけばそれ以上戻ることはないので充分」ということを見抜くことなのですが、ではこれをどうbitDPで覚えておくか、これが巡回セールスマンみたいな状態が二通りしかないようなbitDPしかやったことないような僕とかbitDPまったくやったことない人にとっては大きな問題になるでしょう。
今回は座標上の移動なので一回の移動で４つのパターンがありえます。でもこれはコードを見てみたら単純な話でした。

すなわち、一回の移動を2bitで表せばいいということです。持っておくのは6つ前までの移動手順なので合計12bitとなり、充分bitDPできるサイズになります。

・・・あとはまぁsnukeさんが言っているようにメモ化再帰にすれば実装でこまることは無いでしょう。多分。
bitDPってそもそもなによって人は僕も昔解説とか書いてる気がしなくも無いですし、ネット上にも蟻本にも解説はたくさんあるので自分で探してみてください。