*Topcoder SRM 504.5 DIV1

.5 って何ぞ? と思いつつ、仮眠せず参加。微妙に眠かったけど、途中から冴えてきた。

250 TheNumbersWithLuckyLastDigit

む? さっぱり方針が立たない。DFS的に探索すればいいだろうけど、普通にやったらTLEするのは確実だし。でも、一瞬で提出してる人がいるところを見ると、簡単な方法があるんだろうなぁ…… 

ある程度大きな数では、各要素の上の方の位に足せばいいから、答えはそんなに大きくならないハズ。でも、答えについて探査できるのか?小さいケース Ruby で全部調べてパターンを見つけるか? うーん、やる気がでない……

などと考えているうちに、なんとなく、n - 4i - 7j の1の位が4か7になるようにすればいい気がしてきた(証明なし)。i, j を 0 から 100 までの範囲で動かしてみる。テストケース通った。どうでもいいや、提出。

550 TheJackpotDivOne

絵を書いて考えていると、何サイクルか回した後は、{x, x, x, x, x} みたいに揃って、次に、{x + 1, x, x, x, x} になって……{x + 1, x + 1, x + 1, x + 1, x + 1} となる気がしてきた。この部分を一気に計算して、あとはシミュレートすればよさそう。

シミュレート部分を書く。げ? 10^18 * 47 > 2^64 で、long long がオーバーフローするじゃないか! long double にしてみる。最後のテストケースが通らない。どうやら誤差で、平均が 12.0 となるべき所でも 11.9999… みたいになる様子。したがって、本当は 13 にしたいのに、12 になるように money を配ってしまう。適当に EPS を挟んだら通った。提出。

Challenge phase

250 に対して全探索してるのをつぶすコード、550 で平均の計算がオーバーフローするやつ(最大ケース)を用意。

250、早解き組は大体私と同じ解法。遅い組は、答えをハードコーディング。全探索はいない。

550、みんな Java の BigInteger でやってる。それが無難なのは分かるけど、BigInteger は見た目が嫌い。演算子オーバーロードがないとか…… long long で足してるコードを1つ発見、最大ケース突っ込む。失敗。よく見ると、全ての要素が同じ値かをチェックするコードの位置が私と違った。{10^18, 10^18, 10^18, ...} じゃ無理だ。{10^18, 10^18 - 1, 10^18 - 2, 10^18 - 3, ...} みたいなのを突っ込む。Challenge 成功!

結果と考察

1422→1453。250通った、Challenge 1つ失敗1つ成功、550 落ちた。long double でもダメだったっぽい。せっかく方針あってたし、オーバーフローにも気づいてたのに残念。

[追記] 550 のオーバーフロー対策については、komiyam さんの日記に多倍長演算を使わないすばらしい解法が載っていた。これはうまい! http://d.hatena.ne.jp/komiyam/20110518/1305667237