編集履歴

質問編集履歴

表示がバグってたので修正

2018/09/15 07:13

投稿

fly3555

スコア13

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -152,13 +152,173 @@
     }
+  }
+  cout << ans << endl;
+}
-  }```ここに言語を入力
+int main() {
-コード
+  solve();
+  return 0;
+}
 ```
+### 補足情報
+C++ (GCC 5.4.1) で提出しました。
+### 修正したソースコード
+2018/09/15作成。
+```C++
+#include <iostream>
+#include <algorithm>
+#include <cassert>
+using namespace std;
+#define MAXN 2000
+#define INF 1000000000 //修正
+int N, K;
+int a[MAXN + 1];
+int dp[MAXN + 1][MAXN + 1];
+void solve() {
+	int ans;
+	cin >> N >> K;
+	for (int i = 1; i <= N; ++i) {
+		cin >> a[i];
+	}
+	int sumA = 0;
+	for (int i = 1; i <= N; ++i) {
+		sumA += a[i];
+	}
+	if (sumA <= K) {
+		ans = 1;
+	}
+	else {
+		/*dp[tmpN][tmpW]は、tmpN日ゲームをして機嫌のいい日がtmpW日となる最小の勝ち数の合計*/
+		/*tmpN>=tmpWの場合だけ考える*/
+		/*tmpW=0のとき、dp[tmpN][0]=0*/
+		/*tmpN=tmpW>0のとき、tmpN=1以外は不可能
+		  ↑間違い a[1]=1のときはtmpN=1以外は不可能だが、a[1]>1のときは可能なケースがある*/
+		  //dp[1][1] = 1;
+		  //for (int i = 2; i <= N; ++i) {
+		  //	dp[i][i] = INF;
+		  //}
+		  /*tmpN>=tmpW>0のとき*/
+		dp[1][1] = 1;
+		int A_previous_tmpN = a[1]; //前日までの勝ち数の合計
+		for (int tmpN = 2; tmpN <= N; ++tmpN) {
+			dp[tmpN - 1][tmpN] = INF;
+			for (int tmpW = 1; tmpW <= tmpN; ++tmpW) {
+				const int k_tmpN = (a[1] == 1 && tmpW == tmpN) ? INF : (long long int) dp[tmpN - 1][tmpW - 1]
+					* a[tmpN] / A_previous_tmpN + 1;
+				//tmpN日に機嫌がよくなるために必要な勝ち数
+				assert(k_tmpN > 0);
+				dp[tmpN][tmpW] = min(dp[tmpN - 1][tmpW],
+					dp[tmpN - 1][tmpW - 1] + k_tmpN);
+			}
+			A_previous_tmpN += a[tmpN];
+		}
+		for (int tmpN = 0; tmpN <= N; ++tmpN) {
+			for (int tmpW = 0; tmpW <= N; ++tmpW) {
+				assert(dp[tmpN][tmpW] >= 0);
+			}
+		}
+		for (int tmpW = N; tmpW >= 0; --tmpW) {
+			if (dp[N][tmpW] <= K) {
+				ans = tmpW;
+				break;
+			}
+		}
+	}
-  cout << ans << endl;
+	cout << ans << endl;
 }
@@ -166,172 +326,10 @@
 int main() {
-  solve();
+	solve();
-  return 0;
+	return 0;
 }
 ```
-### 補足情報
-C++ (GCC 5.4.1) で提出しました。
-### 修正したソースコード
-2018/09/15作成。
-```C++
-#include <iostream>
-#include <algorithm>
-#include <cassert>
-using namespace std;
-#define MAXN 2000
-#define INF 1000000000 //修正
-int N, K;
-int a[MAXN + 1];
-int dp[MAXN + 1][MAXN + 1];
-void solve() {
-	int ans;
-	cin >> N >> K;
-	for (int i = 1; i <= N; ++i) {
-		cin >> a[i];
-	}
-	int sumA = 0;
-	for (int i = 1; i <= N; ++i) {
-		sumA += a[i];
-	}
-	if (sumA <= K) {
-		ans = 1;
-	}
-	else {
-		/*dp[tmpN][tmpW]は、tmpN日ゲームをして機嫌のいい日がtmpW日となる最小の勝ち数の合計*/
-		/*tmpN>=tmpWの場合だけ考える*/
-		/*tmpW=0のとき、dp[tmpN][0]=0*/
-		/*tmpN=tmpW>0のとき、tmpN=1以外は不可能
-		  ↑間違い a[1]=1のときはtmpN=1以外は不可能だが、a[1]>1のときは可能なケースがある*/
-		  //dp[1][1] = 1;
-		  //for (int i = 2; i <= N; ++i) {
-		  //	dp[i][i] = INF;
-		  //}
-		  /*tmpN>=tmpW>0のとき*/
-		dp[1][1] = 1;
-		int A_previous_tmpN = a[1]; //前日までの勝ち数の合計
-		for (int tmpN = 2; tmpN <= N; ++tmpN) {
-			dp[tmpN - 1][tmpN] = INF;
-			for (int tmpW = 1; tmpW <= tmpN; ++tmpW) {
-				const int k_tmpN = (a[1] == 1 && tmpW == tmpN) ? INF : (long long int) dp[tmpN - 1][tmpW - 1]
-					* a[tmpN] / A_previous_tmpN + 1;
-				//tmpN日に機嫌がよくなるために必要な勝ち数
-				assert(k_tmpN > 0);
-				dp[tmpN][tmpW] = min(dp[tmpN - 1][tmpW],
-					dp[tmpN - 1][tmpW - 1] + k_tmpN);
-			}
-			A_previous_tmpN += a[tmpN];
-		}
-		for (int tmpN = 0; tmpN <= N; ++tmpN) {
-			for (int tmpW = 0; tmpW <= N; ++tmpW) {
-				assert(dp[tmpN][tmpW] >= 0);
-			}
-		}
-		for (int tmpW = N; tmpW >= 0; --tmpW) {
-			if (dp[N][tmpW] <= K) {
-				ans = tmpW;
-				break;
-			}
-		}
-	}
-	cout << ans << endl;
-}
-int main() {
-	solve();
-	return 0;
-}
-```

修正したコードを追加

2018/09/15 07:12

投稿

fly3555

スコア13

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -152,7 +152,11 @@
     }
+  }```ここに言語を入力
-  }
+コード
+```
   cout << ans << endl;
@@ -177,3 +181,157 @@
 C++ (GCC 5.4.1) で提出しました。
+### 修正したソースコード
+2018/09/15作成。
+```C++
+#include <iostream>
+#include <algorithm>
+#include <cassert>
+using namespace std;
+#define MAXN 2000
+#define INF 1000000000 //修正
+int N, K;
+int a[MAXN + 1];
+int dp[MAXN + 1][MAXN + 1];
+void solve() {
+	int ans;
+	cin >> N >> K;
+	for (int i = 1; i <= N; ++i) {
+		cin >> a[i];
+	}
+	int sumA = 0;
+	for (int i = 1; i <= N; ++i) {
+		sumA += a[i];
+	}
+	if (sumA <= K) {
+		ans = 1;
+	}
+	else {
+		/*dp[tmpN][tmpW]は、tmpN日ゲームをして機嫌のいい日がtmpW日となる最小の勝ち数の合計*/
+		/*tmpN>=tmpWの場合だけ考える*/
+		/*tmpW=0のとき、dp[tmpN][0]=0*/
+		/*tmpN=tmpW>0のとき、tmpN=1以外は不可能
+		  ↑間違い a[1]=1のときはtmpN=1以外は不可能だが、a[1]>1のときは可能なケースがある*/
+		  //dp[1][1] = 1;
+		  //for (int i = 2; i <= N; ++i) {
+		  //	dp[i][i] = INF;
+		  //}
+		  /*tmpN>=tmpW>0のとき*/
+		dp[1][1] = 1;
+		int A_previous_tmpN = a[1]; //前日までの勝ち数の合計
+		for (int tmpN = 2; tmpN <= N; ++tmpN) {
+			dp[tmpN - 1][tmpN] = INF;
+			for (int tmpW = 1; tmpW <= tmpN; ++tmpW) {
+				const int k_tmpN = (a[1] == 1 && tmpW == tmpN) ? INF : (long long int) dp[tmpN - 1][tmpW - 1]
+					* a[tmpN] / A_previous_tmpN + 1;
+				//tmpN日に機嫌がよくなるために必要な勝ち数
+				assert(k_tmpN > 0);
+				dp[tmpN][tmpW] = min(dp[tmpN - 1][tmpW],
+					dp[tmpN - 1][tmpW - 1] + k_tmpN);
+			}
+			A_previous_tmpN += a[tmpN];
+		}
+		for (int tmpN = 0; tmpN <= N; ++tmpN) {
+			for (int tmpW = 0; tmpW <= N; ++tmpW) {
+				assert(dp[tmpN][tmpW] >= 0);
+			}
+		}
+		for (int tmpW = N; tmpW >= 0; --tmpW) {
+			if (dp[N][tmpW] <= K) {
+				ans = tmpW;
+				break;
+			}
+		}
+	}
+	cout << ans << endl;
+}
+int main() {
+	solve();
+	return 0;
+}
+```