SRM332 に挑戦。2006 年、最後の SRM になります。
250 点問題。Greedy ですね。落ち着けばとけます。
550 点問題。2 次元平面上で水平の線分(セグメント)がいくつか与えられます。このセグメントに垂直のセグメントを好きなだけ足して、最大のポリゴンを作成して、その辺の数を返しなさい。という問題です。
単純に考えてそのまま強引に解いてしまいました。ワーストケースでのタイムアウトが気になりましたが大丈夫だったようです。
950 点問題.Open しませんでした。
System Test の結果です. ( Room Statistics )
550 点問題の RestoringPolygon をシステムテストで落とされた人が続出 ( 309 人中、提出が 144、正解が 16 と正解率が 11%ほど )したため、 全体的に点数が低めでした。 950 点問題のほうが、550 点問題より正解者が多い。。。
なぜか同じルーム内には Red Coder がいなかったため、ルーム内ではトップのポイント。レーティングは 1532->1678 と上昇しました。
2006 年も終了。この時点での Stats を記録として残しておきます。
今年のはじめはレーティングが 1630 で、今は 1678 ですのであんまり変わってません。
まだまだ Red Coder へは遠い道のりです。。
TopCoder に参加するときはこれまでのところ Java をずっと使用していますが、 TopCoder 以外の個人的な場面では Java を使用することはすっかりなくなり、大抵の場合 Python を使用しています。でもあいかわらず、TopCoder のアルゴリズム・マッチで使用できる言語は、 Java、C#、C++、VB の 4 つだけで Python は採用されそうもありません。他言語とのスピード差がその理由だそうです。アルゴリズム・マッチで走らせるプログラムは外との I/O がまったくなくほぼ CPU だけに全体の処理時間が依存してしまうので、どうしてもスピード差が顕著になってしまうわけですね。そうはいっても、今年の Google Code Jam では Python は採用されたわけだが。。。
と思っていたら、TopCoder のマラソン・マッチでは Python がいつのまにか使用言語として採用されています。アルゴリズム・マッチと異なり、マラソン・マッチはコンテストの性質上、処理時間をあまり気にする必要がないので Python を加えたそうです。じっくり未解決の難問に取り組むマラソン・マッチもやってみたいところだが、さすがにアルゴリズム部門と比べて時間がそれなりにとられそうなのでしばらくは見送り。