脳log[2021-12-22～]

最終更新: 2022-01-03T13:27+0900

♪ [AtCoder] JOIG 2021 過去問／F 問題 デジタルアート (Digital Art)

D と E についてはここに書いた>20211206。A,B,C については ABC-C までの難易度帯という感じで特に何ということもなく解けたので書いていない。最後に F 問題が残っていた。

 考え方

色ごとにその色を完全に覆い隠せる矩形を考える。矩形は左上座標と右下座標で特徴付けられる。面積 S を超えない範囲でどのような矩形を選べばできるだけ多くの色を隠せるだろうか。

 制約

グリッドの一辺は最大 1000 なので、グリッド上の点は最大 100 万個。いくら面積 S を超えない範囲でできるだけ大きな矩形のみを考えるとしても、グリッドから２点を選ぶ組み合わせは１メガ×１メガに近い数になる。これは制限時間１秒で扱える数ではない。

色数の上限が 256 に抑えられている。256 の３乗は約 1600 万だから、Ruby の場合、定数倍が 1/2 とかなら３乗がなんとかなるかな、という雰囲気。

 どうやる？

二次元累積和であるとか「Range Set Query」が思い浮かんだけど、どうにも(知っている)定型の処理に当てはまらない。

矩形の左上座標と右下座標を探索することが許されるなら、色を、その色を囲う左上座標と右下座標のそれぞれでソートしておくことで、うまく探索してマッチングして数を数えられると思う。

色を特徴付ける矩形の左上角と右下角の組み合わせを選ぶ 256 の２乗通りでは答えを漏らすのでよろしくないが、４辺を選ぶ 256 の４乗通りは許されない。困った。

 どうした

矩形の縦の長さを固定して横方向に尺取りをした。

 提出 #27751046 (75/100 点 / TLE×9)

最後の小課題９のケースもいくつか通ってるので惜しいのかと思ったけど、実は遅いケースは 10 秒とかそこらかかっていた。

４重ループです。上辺について 256 通り。底辺について 256 通り。右辺と左辺について尺取りが 256×2 ステップ。その最深部で矩形に出入りする色が 256 個。だめじゃん。

 提出 #27751294 (TLE×9)

定数倍の改善。Array#minmax の呼び出し回数を節約した。650 ms が 350 ms になるレベル。

 提出 #27752007 (TLE×9)

定数倍の改善。上辺と底辺に関する第一第二ループを Array#repeated_combination(2) で横着せずに、尺取りっぽく遷移して重複する処理を減らした。550 ms が 450 ms になることもあるし、変わらないこともある、という変化。

 提出 #27772767 (TLE×1)

ついに来た！ TLE は残り１ケース。

改善したのはやっぱり定数倍だけど、上辺に対する底辺の選び方を、尺取りの幅でグループ化して最も高さが大きくなるものに代表させることで、尺取りの回数が大幅に減った。

もうひとつ。ループをイテレータではなく while 文で書き直すことで Ruby の場合かなり速くなるんだけど、それに加えて、答えの候補を求めるループの途中で暫定的な答えにアクセスできるようになったのも大きかった。それにより答えを更新する可能性がない場合に最内ループをスキップすることができた>or ain.size<=max。

 提出 #27797091 (100 点 / 935 ms)

これも定数倍の改善。インチキをした。底辺を尺取りの幅でグループ化する部分が

i1s = I1s.group_by{|i1| i1<i0 ? 0 : [S/(i1-i0+1),W].min }

だったところを、次のようにした。

I1s.shift while I1s[0]<i0
i1s = I1s.chunk{|i1| [S&1|S/(i1-i0+1),W].min }.map{|_,as| as[-1] }

S&1| ってなんですかね？

とにもかくにも、(１差の偶数と奇数を同一視することで)４重ループのうちの２番目のループの回数が節約できたのはとっても効いた。

想定解法は３乗もしくは３乗＋logとかのもっとスマートなアルゴリズムを使っているのだろうか。それとも Ruby は想定外だからさっさと Crystal や C++ で出し直すべき案件だったのだろうか。3 MiB オーバーの入力ファイルを読み込むのにも、つまりはスクリプトの１行目の処理を終えるまでにということだけど、１秒しかない時間のそれなりの割合を使っているのだよね。

 デジタルアート解説 (PDF)

想定解法は上辺と底辺を固定しての尺取りだった。やり方は間違っていなかった。その計算量が O(HW+A^3) だというのがわかっていなかった。実際は A^3 でできていたのか、それとも何かおかしなことをして A^4 にしてしまっていたのか、どっちだろう。

ちょっとおかしなことをしていた。AC 提出の最内ループのこの部分。

	ain.reject!{|wj0| wj0<=j1 }

尺取りから出て行く色を見つける部分で、尺取りの中にある色の全体を都度スキャンしていた。

尺取りの右がある座標に至ったときに入る色と、尺取りの左がある座標に至ったときに出る色は、それぞれの合計が最大で 256 個であり、一度の尺取りを通して合わせても 512 個という定数にしかならない。ある座標で入る色と出る色をそれぞれリストしておいて、ある座標に至ったときにそれらの色が尺取りの中にあるかどうかを確かめるべきだった。

このように>joig2021_f.rb27。あるいは最初に TLE をもらった提出 #27751046 のように>20211210p01.05。

だけどたぶんこれは TLE になる(OS が違うけどローカルで測定している)。定数倍の影響が大きすぎるのではないか。最後の TLE をクリアしたとどめの一手だって、尺取りのステップ数を随時削減することによる定数倍の改善だった(S&1| だけでは足りなかったのだ)。やはり Ruby で満点を取ることは想定されていないと思う。

日本情報オリンピック 第2回女性部門（JOIG 2021/2022） から「情報オリンピックに初めて参加する方は、出題形式・勉強法・講習会などに関する情報をまとめた「情報オリンピックの勉強法」をご覧ください」とリンクされていた(JOIの)ページから。

JOI 本選

本選は 2 月に実施されていて、4 時間で 5 問に取り組みます。上位者は春合宿に招待されます。

本選では二次予選と比べて難しいアルゴリズムの知識や、そのアルゴリズムを与えられた課題に適用させるための高度な発想力が問われます。

JOI 春季トレーニング合宿 (春合宿)

春合宿は IOI 日本代表を決めるための代表選抜会です。3 月に実施されていて、4 日間連続で毎日 5 時間の競技に取り組みます。上位 4 人は IOI 日本代表として派遣されることになります。

なお、春合宿で使えるプログラミング言語は C++ のみです

情報オリンピックの勉強法｜高校生以下限定のプログラミングコンテストに参加しよう！ - 情報オリンピック日本委員会

本選の後に春合宿があり、「なお、春合宿で使えるプログラミング言語は C++ のみです。」 そうなのね。