404.1

同じ日に二件書くというのもいかがなものか。BigIntegerの問題が出ると有利とされているJavaですが、今回はJavaのライブラリを使うと正解できない(と思われている)問題が出ました。500から始めて、250に逃げて、500をやっぱりやるという感じ。途中で頭の切り替えができたのは良かったと思う。

250

ある数字の列から、隣接する二つの数の和の下一桁を使うことで、一つ短い数字の列を再帰的に作っていくことでできる三角形状の数字配列を、各数字のうち一桁だけ分かっている状態から復元せよ、という問題。

最初は適当な順番で復元できる、程度の問題だと思っていて、分からない場所すべてについて調べて一つずつ埋める、という処理にしてしまった。(この問題を解くことはできる。)

実際にやるべきは、下から順に、分かっている数字から分からない部分を復元していけばいいだけ。一番下の行は数字一つで、一桁だけ与えられるという制約より、分かっている。その上の行は2文字で、1文字分かっているからそれ以外のもう一文字は下の行から分かる。というのを延々とやるだけ。英語はちゃんと読みましょう。

500

ある整数配列のうち、長さKの区間を二つ重ならないように選んだときに、各区間の要素の和の差分が最小になるようなKと、その差分を求めよ、という問題。配列長は3000程度。

取り敢えずすべての可能な区間の開始位置と長さから、その区間の要素の和を得るようなテーブルを作成する。C++なら、各区間長について、開始位置jについて可能な開始位置iの要素を覚えておいて、そのうち開始位置jの要素に近いもの二つを拾ってくる、という処理をループするだけ。(そういうデータ構造がリーズナブルな速度で得られる。)

一方Javaユーザはというと、TreeSetのような同様の機能を持つようなライブラリはあるものの、汎用性を高めた実装のために、結構処理が重い。(使い方が悪かったと思うのだけれど、普通にすべてのi,jのペアについて計算するよりも大分遅かった。)

仕方がないので、各行の要素をソートして、区間長の差分のうち、最小になり得る値を、各区間長について計算しておいて、それが小さくなるものから順に、実現可能性を調べていく、という処理を行ってみた。実際には元の整数配列でうまくいかない例を作れるのだけれど、この問題では整数配列は線形合同法(?)で作っているので、この処理でうまくいく。(少なくともSYSTEMのTESTは通る。)

950

なんだか知らないけれど最大流の問題だそうです。時間5分くらいしかなかったし、英語が長かったのでやめてしまった。こういうのがサックリ書けるようになると、レーティングは伸びるんでしょうねぇ。