質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.12%
C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

解決済

Atcoder ドワンゴからの挑戦状第四回 予選 C問題について一部のテストケースでWAになる

rdld036
rdld036

総合スコア14

C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1回答

0リアクション

1クリップ

445閲覧

投稿2022/09/25 17:40

質問事項

Atcoderドワンゴからの挑戦状第四回予選C問題を下をコードで解いたのですが、一部のテストケースでWAになってしまいました。方針としてはこの問題の解説に従ったのですが、私の実装面で不備があるのか、または分割数やdpテーブルの定義に不備があるのかわかりません。どなたか教えていただけますでしょうか。

該当のソースコード

C++

//#define _GLIBCXX _DEBUG #include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = INT_MAX; const int MOD = 1e9 + 7; vector<vector<ll>> P(1001, vector<ll>(1001,0)); ll solve(vector<int> &kill, vector<int> &death){ deque<pair<int, int>> cnt; // cnt...キル数で分けたグループの集合 cnt.push_back({kill[0], 1}); //cnt.first キル数 cnt.second同じキル数の人数 for(ll i = 1; i < kill.size(); ++i){ if(cnt.back().first == kill[i]) cnt.back().second++; else cnt.push_back({kill[i], 1}); } int toll = 0; for(auto i : death){ toll += i; } int n = cnt.size(); vector<vector<ll>> dp(n + 1, vector<ll>(toll + 1, 0)); // dp[group][d]:= group番目までで、デス数がdである組み合わせ数 dp[0][0] = 1; for(int group = 0; group < n; ++group){ for(int d = 0; d <= toll; ++d){ for(int j = 0; j < toll - d + 1; ++j){ dp[group + 1][d + j] += (dp[group][d] * P[cnt[group].second][j]); dp[group + 1][d + j] %= MOD; } } } return dp[n][toll]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vector<int> A(N), B(M); for(int i = 0; i < N; ++i) cin >> A[i]; for(int i = 0; i < M; ++i) cin >> B[i]; P[0][0] = 1; for(int i = 1; i <= 1000; ++i ){ for(int j = 0; j <= 1000; ++j){ P[i][j] = P[i - 1][j]; if(j >= i) P[i][j] += P[i][j - i]; //P[i][j]:= jをi個以下に分割する方法の総数 } } ll a = solve(A, B); ll b = solve(B, A); ll ans = a * b; ans %= MOD; cout << ans << endl; }

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

2022/09/26 04:07

こちらの質問が複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という指摘を受けました。

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.12%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C++11

C++11は2011年に容認されたC++のISO標準です。以前のC++03に代わるもので、中枢の言語の変更・修正、標準ライブラリの拡張・改善を加えたものです。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。