スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Google Code Jam Japan 2011 決勝

2011/10/08 13:00 ~ 16:00 (JST)
Google Code Jam Japan 2011 決勝の参加記録

惨敗。
反省すべきことが見えたような気がした。

Tags : プログラミング GCJJ 未解決

結果

A. small: WA, AC (0:20:39)
A. large: WA
B. small: 6WA, AC (2:43:09)
B. large: -
C. small: -
C. large: -
D. small: -
D. large: -
E. small: -
E. large: -

362 / 439(?) 位

やったこと

問題はここ

A.
{E1, E2, ..., Ek} を並べ替えて E1・E2 + E2・E3 + ... + Ek・E1 を最大化する問題だということはわりとすぐに気付いた。
でも large の解法が思いつかなかったので、とりあえず next_permutation で small を書き上げた。
添え字ミスで 1WA の後、修正して Accepted.

large が全然わからないけど、出してる人がたくさんいるので、どうせ greedy と思ってそれっぽいのを書いてみた。 ← 重罪
アルゴリズムが正しいことの証明はできなかった。 ( なぜなら正しくなかったから )
small の出力と一致したので提出した。
結果は Wrong Answer だった。

B.
数論の問題は好き。解けなかったけど。

small を解くことだけを考えた。
B = 1 のときはただのべき剰余。
B = 2 が問題。
ようは (AA)(AA) mod C を求めるということ。

A' := AA mod C とおく。これはすぐに計算できる。

(AA)(AA) mod C = A'(AA) mod C
となる。
AA が大きすぎるので、これはまだ計算できない。

次に、C が小さいことに注目する。
A'x mod C ( x : 正整数 ) はすぐに循環するはず。
ただ、必ず A'1 に戻ってくるわけではない。 ()
なので、循環周期 T ( つまり、A'T = 1 mod C となる T ) を O(C) 程度で計算することができて、
この値を使えば、おおよそ
A'(AA) mod C = A'(AA mod T) mod C
となる。 ( おおよそと言ったのは () と関係している。最初の方では値が循環していない可能性があるから。 )
この指数は小さいので、これで答えが計算できる。

反省

一番悪かったのは、根拠がないのに A large を提出したこと。
これは愚の骨頂で、落ちて当たり前といえる。
普段から、ぽっと思いついた解法をよく考えずに書いて出しているからこんなことになる。

二度とこんなことがないように、これからは証明にとことんこだわることにする。
具体的には 「アルゴリズムの正しさが証明できない解答は書かない」 という縛りをかける。少なくとも、十分熟達するまでは。
( これはあてずっぽうな解答を書かないということで、たとえば、アイデアを出すためにとりあえずコードを書いてみるなどは OK )

解答

まともに解けた問題がないので、解説が出てから解きなおします。

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。