結果
| 問題 | No.3329 Only the Rightest Choice is Right!!! |
| コンテスト | |
| ユーザー |
 aketijyuuzou
|
| 提出日時 | 2025-12-20 17:30:29 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 529 ms / 1,571 ms |
| コード長 | 6,069 bytes |
| 記録 | |
| コンパイル時間 | 13,251 ms |
| コンパイル使用メモリ | 169,516 KB |
| 実行使用メモリ | 317,776 KB |
| 最終ジャッジ日時 | 2025-12-20 17:31:01 |
| 合計ジャッジ時間 | 27,416 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 74 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (125 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
// No.3329 Only the Rightest Choice is Right!!!
// https://yukicoder.me/problems/no/3329
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("4 5");
WillReturn.Add("1 4 2 3");
WillReturn.Add("1 4 2 3");
//2
//3 4
}
else if (InputPattern == "Input2") {
WillReturn.Add("6 3000");
WillReturn.Add("1 1 1 1 1 1");
WillReturn.Add("3000 3000 3000 3000 3000 3000");
//1
//6
}
else if (InputPattern == "Input3") {
WillReturn.Add("10 3000");
WillReturn.Add("2992 3000 1 1 1 1 1 1 1 1");
WillReturn.Add("2992 3000 1 1 1 1 1 1 1 1");
//1
//2
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] GetSplitArr(string pStr)
{
return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
}
struct ItemInfoDef
{
internal long Score;
internal long Weight;
}
static ItemInfoDef[] mItemInfoArr;
static long UB;
static long mWeightLimit;
static void Main()
{
List<string> InputList = GetInputList();
long[] wkArr = GetSplitArr(InputList[0]);
mWeightLimit = wkArr[1];
long[] ValueArr = GetSplitArr(InputList[1]);
long[] WeightArr = GetSplitArr(InputList[2]);
var ItemInfoList = new List<ItemInfoDef>();
for (long I = 0; I <= ValueArr.GetUpperBound(0); I++) {
ItemInfoDef WillAdd;
WillAdd.Score = ValueArr[I];
WillAdd.Weight = WeightArr[I];
ItemInfoList.Add(WillAdd);
}
mItemInfoArr = ItemInfoList.ToArray();
UB = mItemInfoArr.GetUpperBound(0);
// スコア[重さ][どこまでみたか]なインラインDPのDict
var DPArrDict1 = new Dictionary<long, long?[]>();
DPArrDict1[UB] = new long?[mWeightLimit + 1];
DPArrDict1[UB][0] = 0;
// 最後に選んだ品物[重さ][どこまでみたか]なインラインDP表
var DPArrDict2 = new Dictionary<long, long?[]>();
DPArrDict2[UB] = new long?[mWeightLimit + 1];
for (long I = UB; 0 <= I; I--) {
long?[] CurrArr1 = DPArrDict1[I];
long?[] CurrArr2 = DPArrDict2[I];
for (long J = mWeightLimit; 0 <= J; J--) {
if (CurrArr1[J].HasValue == false) continue;
long NewJ = J + mItemInfoArr[I].Weight;
if (NewJ > mWeightLimit) continue;
long NewScore = CurrArr1[J].Value + mItemInfoArr[I].Score;
if (CurrArr1[NewJ].HasValue) {
if (CurrArr1[NewJ].Value > NewScore) {
continue;
}
if (CurrArr1[NewJ].Value == NewScore) {
if (CurrArr2[NewJ].HasValue) {
if (CurrArr2[NewJ] > I) {
continue;
}
}
}
}
CurrArr1[NewJ] = NewScore;
CurrArr2[NewJ] = I;
}
if (0 < I) {
DPArrDict1[I - 1] = (long?[])DPArrDict1[I].Clone();
DPArrDict2[I - 1] = (long?[])DPArrDict2[I].Clone();
}
}
//for (long I = UB; 0 <= I; I--) {
// Console.WriteLine("{0}まで見たDP結果", I);
// long?[] CurrArr1 = DPArrDict1[I];
// for (long J = 0; J <= mWeightLimit; J++) {
// if (CurrArr1[J].HasValue) {
// Console.WriteLine("CurrArr1[{0}]={1}", J, CurrArr1[J]);
// }
// }
// long?[] CurrArr2 = DPArrDict2[I];
// for (long J = 0; J <= mWeightLimit; J++) {
// if (CurrArr2[J].HasValue) {
// Console.WriteLine("CurrArr2[{0}]={1}", J, CurrArr2[J]);
// }
// }
//}
long CurrInd = 0;
long RestWeight = mWeightLimit;
var AnswerList = new List<long>();
while (true) {
bool HasAnswer = false;
long AnswerItem = -1;
long MaxScore = long.MinValue;
for (long I = 0; I <= RestWeight; I++) {
long?[] CurrArr1 = DPArrDict1[CurrInd];
long?[] CurrArr2 = DPArrDict2[CurrInd];
if (CurrArr1[I].HasValue == false) continue;
if (CurrArr1[I].Value == 0) continue;
if (MaxScore > CurrArr1[I].Value) continue;
if (MaxScore == CurrArr1[I]) {
if (AnswerItem > CurrArr2[I]) {
continue;
}
}
HasAnswer = true;
MaxScore = CurrArr1[I].Value;
AnswerItem = CurrArr2[I].Value;
}
if (HasAnswer == false) {
break;
}
RestWeight -= mItemInfoArr[AnswerItem].Weight;
AnswerList.Add(AnswerItem);
CurrInd = AnswerItem + 1;
if (CurrInd > UB) break;
}
Console.WriteLine(AnswerList.Count);
for (int I = 0; I <= AnswerList.Count - 1; I++) {
AnswerList[I]++;
}
Console.WriteLine(LongEnumJoin(" ", AnswerList));
}
// セパレータとLong型の列挙を引数として、結合したstringを返す
static string LongEnumJoin(string pSeparater, IEnumerable<long> pEnum)
{
string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
return string.Join(pSeparater, StrArr);
}
}