Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What are the problem?

AtCoderログ:0044 - ARC 124 A

問題

問題文

$N$ 枚のカードが左から右に並んでいます。 各カードに $1$ 以上 $K$ 以下の整数を書き込みます。はじめ、どのカードにも整数は書かれていません。
$1$ から $K$ の番号がついた $K$ 個の制約が与えられます。制約 $i$ は文字 $c_i$ と整数 $k_i$ からなります。$c_i$ が L ならば、$i$ が書かれたカードのうち最も 左 にあるものは $N$ 枚のカードのうち左から $k_i$ 番目である必要があります。$c_i$ が R ならば、$i$ が書かれたカードのうち最も 右 にあるものは $N$ 枚のカードのうち左から $k_i$ 番目である必要があります。
$1$ 以上 $K$ 以下の各整数 $i$ について、$i$ が書かれたカードが少なくとも $1$ つ存在する必要があることに注意してください。
上記の $K$ 個の制約をすべて満たすようなカードへの整数の書き込み方の個数を $998244353$ で割ったあまりを求めてください。

制約

・$1 \le N, K \le 1000$
・$c_i$ は L, R のいずれか
・$1 \le k_i \le N$
・$i \ne j$ ならば $k_i \ne k_j$

回答

回答1 (AC)

$N$ 枚のカードのそれぞれに $1$ から $K$ までの整数のいずれかが書き込まれるので、最初の段階で、各カードの値の可能性は $K$ 通りずつあります。そこで $K$ 行 $N$ 列の表を用いて、各カードの値の可能性を調べていくことにします。$i$ 行目は数字 $i$ を書き込む列を表します。

例として入力例2を使用しましょう。1 番目の制約条件は「R 6」なので、1 行目の左から 6 番目は $1$ を書き込むことを表すために「○」をかき、さらに左から 7 番目以降には $1$ が書き込まれる可能性がないことを表すために「×」をつけていきます。2 番目の制約条件は「R 7」なので、2 行目の左から 7 番目には「○」をかき、8 番目以降には「×」をつけていきます。全ての制約条件に対してこの作業を繰り返した結果が下表になります。

arc124a.png

この表より、1 番目のカードに書き込まれる値は $1, 2, 3, 4, 7, 10$ の 6 通り、2 番目のカードに書き込まれる値も $1, 2, 3, 4, 7, 10$ の 6 通りであることがわかるので、1 番目と 2 番目のカードに書き込まれる数字のパターンは $6 \times 6=36$ 通りとなります。同様にして全てのカードについて調べると、30 枚のカードに書き込まれる数字のパターンは
$$
6 \times 6 \times 6 \times 6 \times 6 \times
1 \times 1 \times 1 \times 3 \times 3 \times
1 \times 4 \times 1 \times 1 \times 4 \times
4 \times 4 \times 4 \times 4 \times 4 \times
4 \times 4 \times 1 \times 5 \times 1 \times
1 \times 5 \times 5 \times 5 \times 1 = 11466178560000
$$
通りとなり、これを $998244353$ で割って、余り $343921442$ を得ます。この操作をコードにすると以下のようになります。

arc124a-1.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int N, K;
  cin >> N >> K;

  vector<vector<int>> m(K+1,vector<int>(N+1,1));
  string c;
  int k;
  for ( int i=1; i<=K; i++ ) {
    cin >> c >> k;
    if ( c=="L" ) {
      for ( int j=1; j<k; j++ ) {
        m.at(i).at(j) = 0;
      }
    } else {
      for ( int j=k+1; j<=N; j++ ) {
        m.at(i).at(j) = 0;
      }
    }      
    for ( int ii=1; ii<=K; ii++ ) {
      if ( ii!=i ) {
        m.at(ii).at(k) = 0;
      }
    }
  }

  int64_t answer = 1, MOD = 998244353;
  for ( int j=1; j<=N; j++ ) {
    int sum = 0;
    for ( int i=1; i<=K; i++ ) {
      sum += m.at(i).at(j);
    }
    answer = answer*sum%MOD;
  }

  cout << answer << endl;
}

回答2 (AC)

回答1を再考してみると、最終的には各列の値の可能性をかけていけばよく、具体的に取り得る値までを管理する必要はありません。ここである列の値の可能性に変化が生じるのは、(1)どこかの列で L または R に関する処理をおこなったときで、列の値の可能性は1通り減ることがある、(2)その列のどこかの行で値が確定したときで、列の値の可能性は1通りになる、のいずれかです。そこで各列の値の可能性だけを管理することで、処理を簡略化することが可能になります。ただし、(2)の処理で値を 1 した列から (1)の処理でさらに 1 を減じることのないように注意が必要になります。コードは以下のようになりました。

abc047b-2.cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;

  vector m(n+1,k);
  string c;
  int p;
  for ( int i=1; i<=k; i++ ) {
    cin >> c >> p;
    if ( c=="L" ) {
      for ( int j=1; j<p; j++ ) {
        if ( m.at(j)>2 ) {
          m.at(j) -= 1;
        }
      }
    } else {
      for ( int j=p+1; j<=n; j++ ) {
        if ( m.at(j)>2 ) {
          m.at(j) -= 1;
        }
      }
    }
    m.at(p) = 1;
  }

  int64_t answer = 1, MOD = 998244353;
  for ( int j=1; j<=n; j++ ) {
    answer = answer*m.at(j)%MOD;
  }

  cout << answer << endl;
}

調べたこと

AtCoder の解説公式解説

回答2と同じ方針ですが、それぞれの制約条件ごとに値の可能性を増やす戦略をとることで処理が簡単になるようでした。

リンク

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
0
Help us understand the problem. What are the problem?