結果
問題 | No.332 数列をプレゼントに |
ユーザー |
![]() |
提出日時 | 2016-02-15 14:51:20 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 307 ms / 2,000 ms |
コード長 | 3,300 bytes |
コンパイル時間 | 851 ms |
コンパイル使用メモリ | 108,160 KB |
実行使用メモリ | 19,712 KB |
最終ジャッジ日時 | 2024-12-24 08:31:42 |
合計ジャッジ時間 | 7,363 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;class Program {static string ReadLine() { return Console.ReadLine(); }static int ReadInt() { return int.Parse(ReadLine()); }static int[] ReadInts() { return ReadLine().Split().Select(int.Parse).ToArray(); }static string[] ReadStrings() { return ReadLine().Split(); }static void Output(int[] ar, List<long> es, long x) {long sum = 0;for (int i = 0; i < ar.Length; i++) {int p = es.IndexOf(ar[i]);if (p == -1) {Console.Write("x");}else {sum += ar[i];Console.Write("o");es.RemoveAt(p);}}Console.WriteLine();if (sum != x) {Console.WriteLine("sum が一致しません");Console.WriteLine("x : {0}", x);Console.WriteLine("sum: {0}", sum);}if (es.Count > 0) {Console.WriteLine("es が空ではありません");Console.WriteLine(string.Join(" ", es));}}static void Calc(long x, int[] ar) {var xs = ar.Select(e => (long)e).ToList();xs.Sort();var ys = new List<long>();for (int i = 0; i < 20; i++) {if (xs.Count == 0) break;ys.Add(xs[xs.Count-1]);xs.RemoveAt(xs.Count-1);}long sum = xs.Sum();var dp = new bool[xs.Count, sum + 1];if (xs.Count > 0)dp[0, xs[0]] = true;for (int i = 1; i < xs.Count; i++) {for (long j = sum - xs[i]; j > 0; j--) {if (dp[i-1, j]) {dp[i, j] = true;dp[i, j + xs[i]] = true;}}}var es = new List<long>(ys); // ys の選択要素for (int i = 0; i < (1 << ys.Count); i++) {int p = 0;long t = 0;for (int j = 0; j < ys.Count; j++) {if ((i & (1 << j)) > 0) {t += ys[j];es[p++] = ys[j];if (t > x) break;}}if (t == x) {Output(ar, es.GetRange(0, p), x);return;}else if (t < x) {if (xs.Count > 0 && x - t < dp.GetLength(1) && dp[xs.Count-1, x - t]) {var es2 = es.GetRange(0, p);long rest = x - t;for (int j = xs.Count-1; j >= 0; j--) {if (rest == 0) break;if (j == 0) {if (rest != xs[0]) throw new Exception();es2.Add(rest);}else if (!dp[j-1, rest]) {es2.Add(xs[j]);rest -= xs[j];}}Output(ar, es2, x);return;}}}Console.WriteLine("No");}static void Main() {var ss = ReadStrings();long x = long.Parse(ss[1]);var xs = ReadInts();Calc(x, xs);}}