Single Round Match 399
いま15分間のチャレンジフェーズなんだけど、人のC++のコードをみて間違いを指摘できるレベルじゃないので暇。Gyazoをインストールしてみた。
ところで対戦用のJavaプログラムからコピペできないのは僕の環境が悪いのか、コピペできないように何かしてあるのかどっちなんだろう。MacBookで参加している人に聞けばいいのかな。←追記：やっぱりできないものらしい。
-
-
-
- -
-
-
チャレンジフェーズ終了。ソースコードをさらしてみよう。
まず一問目、環状線のような輪っかの形をした鉄道があり、各駅の間の移動にかかる時間が与えられている。ある駅から別の駅に行くには時計回りと反時計回りの２通りの行き方があるが、時間のかからない側を通るものとする。さて、与えられた環状線で一番移動に時間のかかる駅のペアを選び、そのときにかかる時間を答えよ。
typedef long long LL; (snip) int longestTravel(vector <int> t) { LL sum = accumulate(t.begin(), t.end(), 0); size_t N = t.size(); LL maxvalue = 0; size_t maxi = 0, maxj = 0; for(size_t i=0; i<N-1; i++){ for(size_t j=i+1; j<N; j++){ LL time = accumulate(t.begin() + i, t.begin() + j, 0); time = min(time, sum - time); if(time > maxvalue){ maxvalue = time; maxi = i; maxj = j; } } } return maxvalue; }
解説。
まず、反時計回りにかかる時間は「一周の時間-時計回りの時間」なので最初に一周の時間を求めておく。あとは全部のペアについてかかる時間を求めて最大値を返すだけ。maxiとmaxjはいらなかったのだけど消すのも時間の無駄なのでそのままにした。
-
-
-
- -
-
-
あ、いまシステムテストの結果が出た。
しょんぼりw
-
-
-
- -
-
-
お、レーティングが完了したらしい。
http://www.topcoder.com/tc?module=MemberProfile&cr=22724714
1060になった。
-
-
-
- -
-
-
どういうテストケースで落とされたのかは、Macだとサマリーで自分の名前をCmdクリックしてHistoryを見ればOK。
うわー、なんだかとてもありがちなミスに見えるぞ！
もう一つの1000点問題のFailは上限いっぱいの入力が来たときになぜか
-
-
-
- -
-
-
さて、間違えた500点問題。整数s, kが与えられる。sをk個に分割して掛け合わせた数の最大値を求めよ。
long long maximalProduct(int s, int k) { LL d = s / k; int rest = s - d * k; vector<LL> buf; buf.insert(buf.begin(), k - rest, d); buf.insert(buf.end(), rest, d + 1); multiplies<LL> mul; return accumulate(buf.begin(), buf.end(), 1, mul); }
積が一番大きくなるのは均等に分配したとき。なのでまず平均を切り捨てた値を求めて、それじゃ足りない量だけ1個ずつうわのせする。失敗したのは 60, 20 という入力のとき。3 ** 20 になるわけですな。でも問題文に「回答はlong longの範囲に収まると仮定してよい」と書いてあったんだが。。。
- return accumulate(buf.begin(), buf.end(), 1, mul); + return accumulate(buf.begin(), buf.end(), 1LL, mul);
orz. accumulateの第3引数の型で計算されてしまった。当たり前すぎる。Pythonではオーバーフローする場合に自動的に昇格するからこういうところに気を使う習慣がついていない...
-
-
-
- -
-
-
最後の1000点問題。整数nが与えられたときに、x * y * z がなるべくnに近くなるような x, y, z を求める。ただし別途整数のリストが与えられていて、その中にある整数は使ってはいけない。
まずはPythonで書いた。多少汚い書き方なのはあんまりPythonicな書き方をするとあとでC++で書き直すのがつらいから。普通はgettはNone または result を返すような書き方にするよね。C++は静的型なので面倒だと思ったからPythonで無理矢理参照渡し的にした。
def gett(n, a, result): m = n for i in range(1, n + 1): if n % i: continue if i in a: continue m = n / i; for j in range(i, m + 1): if m % j: continue if j in a: continue k = m / j if j > k: break if k in a: continue result[0] = i result[1] = j result[2] = k return True return False a = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024] n = 512 def main(): result = [0,0,0] got = gett(n, a, result) if got: return result d = 1 while not got: got = gett(n - d, a, result) if got: result2 = [0, 0, 0] got = gett(n + 1, a, result2) if not got: return result else: if result[0] < result2[0]: return result elif result[0] > result2[0]: return result2 elif result[1] < result2[1]: return result elif result[1] > result2[1]: return result2 elif result[2] < result2[2]: return result elif result[2] > result2[2]: return result2 else: got = gett(n + d, a, result) if got: return result d+= 1 print "got:", got, result print main()
解説。まず n を禁止数を避けつつ3つの数の積に分割できるかどうか試す。分割できたらreturn。できなかったら n - 1 と n + 1, n - 2 と n + 2, と徐々に広げていく。nとの差が最小になるようなものを見つければいいので見つかったらreturnすればいい。resultとresult2の比較があるのは、差が同じ回答があった場合にどっちを返すかが問題条件で決まっているのでそれを判定している。Pythonだとresult < result2とかでいいな。C++でもそうかな？
さて、それをC++に直訳。
bool gett(vector <int> a, int m, vector<int> &result) { for(int i=1; i<m+1; i++){ if(m % i) continue; if(find(a.begin(), a.end(), i) != a.end()) continue; m /= i; for(int j=i; j<m+1; j++){ if(m % j) continue; if(find(a.begin(), a.end(), j) != a.end()) continue; int k = m / j; if(j > k) break; if(find(a.begin(), a.end(), k) != a.end()) continue; result[0] = i; result[1] = j; result[2] = k; return true; } } return false; } vector <int> getTriple(vector <int> a, int n) { int _result[3] = {0, 0, 0}; vector<int> result(_result, _result + elementof(_result)); bool got; got = gett(a, n, result); if(got) return result; int d = 1; while(!got){ got = gett(a ,n - d,result); if(got){ int _result2[3] = {0, 0, 0}; vector<int> result2(_result2, _result2 + elementof(_result2)); got = gett(a, n + 1, result2); if(!got){ return result; }else{ if(result[0] < result2[0]){ return result; }else if(result[0] > result2[0]){ return result2; }else if(result[1] < result2[1]){ return result; }else if(result[1] > result2[1]){ return result2; }else if(result[2] < result2[2]){ return result; }else if(result[2] > result2[2]){ return result2; } } }else{ got = gett(a, n + d, result); if(got){ return result; } } d++; } return result; }
システムテストでfailしたのは、禁止リストに1から50までの全部が入っているケース。ああ、、、なるほど。nの上下に1歩ずつ広がっていっているので、1から50まで禁止された時に作ることができる最小の数 51 * 51 * 51 == 132651までたどり着くのに時間がかかってタイムアウトか。。。「使うことができる最小の数の三乗がnを超えている場合は即座にそれを返す」って実装が必要だったんだな。
試してみればすぐに気づくことなんだけど、与えられているテストケースではそういうのをつついてくれないので気づけない。こういう失敗をなくすためには、与えられたテストケースだけじゃなくて自分で境界値とかのテストケースを追加できるようにしないとな。
