#paizahack_01 でロックスターがやってきた
新人女子プログラマの書いたコードを直すだけの簡単なお仕事が簡単じゃない件 - アジョブジ星通信
で微妙に頑張った paiza の企画で、まったく期待すらしてなかった「ロックスター 30 本」が当たってしまいました!!
最終的に投稿したコード
あの記事では LINQ で頑張った結果見事にタイムアウトして死にましたが、 LINQ を一切使わないコードを書いたらみるみるスピードアップしました。でも、using System.Linq;
がないコードなんて C# じゃないよね!!
using System; using System.Collections.Generic; namespace ec_campaign { class Program { static void Main(string[] args) { var n_d = Console.ReadLine().Split(' '); var n = int.Parse(n_d[0]); var d = int.Parse(n_d[1]); var products = new int[n]; for (var i = 0; i < n; i++) products[i] = int.Parse(Console.ReadLine()); Array.Sort(products); for (var _ = 0; _ < d; _++ ) { var goal = int.Parse(Console.ReadLine()); var result = 0; var lessProducts = new List<int>(n); foreach (var p in products) if (p <= goal - 10) lessProducts.Add(p); if (lessProducts.Count > 0) { for (var i = 0; result != goal && i < lessProducts.Count; i++) { var p = lessProducts[i]; var startIndex = lessProducts.Count / 2; var middle = lessProducts[startIndex]; if (p + middle <= goal) { for (var i2 = startIndex; i2 < lessProducts.Count; i2++) { if (i != i2) { var sum = p + lessProducts[i2]; if (sum > goal) break; if (sum > result) result = sum; } } } else { for (var i2 = startIndex - 1; i2 >= 0; i2--) { if (i != i2) { var sum = p + lessProducts[i2]; if (sum <= goal) { if (sum > result) result = sum; break; } } } } } } Console.WriteLine(result); } } } }
azyobuzinさんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1
Test case 1 通過 実行時間:0.04 秒 Test case 2 通過 実行時間:0.06 秒 Test case 3 通過 実行時間:0.41 秒
二分割してループ回数を減らそうと頑張りました。結果は散々ですがw
シール付き
裏には
……はい、実は paiza 使えません。というのも 1997 年生まれですからね。
おかげで、途中の模範解答見れませんでした。利用規約には年齢のこと書いてないのにね!!あと艦これもできない。