AtCoder Regular Contest 107 A,B,C,D,E問題メモ

A - Simple Math

問題

  • $A,B,C$ が与えられるので、$\displaystyle \sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc$ を $\mod{998244353}$ で求めよ
  • $1 \le A,B,C \le 10^9$

解法

$a,b$ を固定して $c$ のループだけを考えると、以下のようになる。

  • $(ab \times 1)+(ab \times 2)+\ldots+(ab \times C)$

これは、$ab \times (1+2+\ldots+C)$ とまとめられる。

すると、$\mathbf C=1+2+\ldots+C$ として、$\mathbf C$ は定数なので外に出せて、最初の式は以下のようになる。

  • $\displaystyle \mathbf C \sum_{a=1}^{A} \sum_{b=1}^{B} ab$

$b,a$ についても同様のことがいえるので、結局答えは $\mathbf A \mathbf B \mathbf C$ となる。

a, b, c = map(int, input().split())
ans = a * (a + 1) * b * (b + 1) * c * (c + 1) // 8 % 998244353
print(ans)

B - Quadruple

問題

  • 整数 $N,K$ が与えられる
  • 以下の条件をともに満たす4つの整数の組 $(a,b,c,d)$ の個数を求めよ
  • 条件
    • $1 \le a,b,c,d \le N$
    • $a+b-c-d=K$
  • $1 \le N \le 10^5$
  • $-2(N-1) \le K \le 2(N-1)$

解法

$a+b$ と $c+d$ に分けて考える。

$a+b$ を固定すると、$c+d=(a+b)-K$ も決まる。また、$X=a+b$ の時に $a,b$ が取り得る組の個数も、値の範囲を考えるとすぐに計算できる。(同様に $c+d$ も)

なので、$a+b$ を全通り試す。

$a+b$ の取り得る範囲は、$c,d$ を移行すると $a+b=K+c+d$ となり、

  • $2 \le a+b \le 2N$
  • $2+K \le K+c+d \le 2N+K$

これが等しくなる(重なる)範囲のみ探せばよいので、$\max(2,2+K)~\min(2N,2N+K)$ となる。

Python3

C - Shuffle Permutation

問題

  • $N \times N$ の行列と整数 $K$ が与えられる
  • 行列の $i$ 行目 $j$ 列目の要素は $a_{i,j}$ である。この行列の要素は $1~N^2$ が1つずつ出現する
  • 以下の操作をどちらでも好きなだけ行える
    • 2つの行 $x,y$ について、同じ列の要素の和($a_{x,j}+a_{y,j}$)が全ての列で $K$ 以下であれば、2行をスワップする
    • 2つの列 $x,y$ について、同じ行の要素の和($a_{i,x}+a_{i,y}$)が全ての行で $K$ 以下であれば、2列をスワップする
  • 操作後のあり得る行列の個数を $\mod{998244353}$ で求めよ
  • $1 \le N \le 50$

解法

まず、和が $K$ 以下とか関係なく、全ての行、列をスワップできるとすると、どういう行列を作れる?と考えると、

1 2 3      8 9 7
4 5 6  →  2 3 1
7 8 9      5 6 4
  • 初期状態で同じ行の数字は(順番は変わっても、組は)変わらない
    • 1,2,3は互いに1つだけ別の行にいったりしない
  • 初期状態で同じ列の数字は(順番は変わっても、組は)変わらない
    • 1,4,7は互いに1つだけ別の列にいったりしない

なので、行、列をそれぞれどういう順番で並べるかで $N! \times N!$ 通りが、制約の無いときに作れる行列となる。

また、この条件より、列をどれだけスワップしても、ある2行が入れ替え可能かどうかが変わることはないことがわかる。(逆も同じ)

さて、サンプル1は $K$ の制約無しでは $3! \times 3!=36$ 通りの行列が作れるところ、答えは12通りになっている。

3 2 7
4 8 9
1 6 5

これが何故かを観察すると、$K$ の制約があると '4 8 9' の行が動かせないから。
よって行方向では $2!$ 通りの並べ方しか無く、$2! \times 3!=12$ 通り、ということになる。

スワップできる行同士をUnion-Find等で連結していくと、同じ連結成分の行同士は(たとえ2つが直接スワップできなくても、適当な行を仲介すれば)好きに入れ替えられる。
その連結成分の最終的な並べ方は、連結成分のサイズを $S$ とすると $S!$ なので、これ毎に乗算していけばよい。

計算量は、2行を選ぶのが $O(N^2)$、選んでその2行が入れ替え可能か調べるのが $O(N)$、調べてUnion-Findで連結させるのはほぼ定数とみなせ1)、全体で約 $O(N^3)$ となる。

Python3

D - Number of Multisets

問題

  • 整数 $N,K$ が与えられる
  • 以下の条件を全て満たす多重集合(同じ要素があってもいいが並び順は区別しない集合)の個数を $\mod{998244353}$ で求めよ
  • 条件
    • 要素数は $N$
    • 要素の総和は $K$
    • 全ての要素は $1,\frac{1}{2},\frac{1}{4},\ldots$ のように「2の累乗分の1」からなる
  • $1 \le K \le N \le 3000$

解法

制約から、なんとなく2次元DPっぽい。

  • $DP[i][j]=$ 要素が $i$ 個、総和が $j$ の多重集合の個数

どう更新するかに、ひらめきが必要。

「$\frac{1}{4}$ を含む集合は $\frac{1}{8}$ 2つに分解して、総和を変えずに要素数を1増やせる」などと遷移しようとしても筋が悪い。
$DP[i][j]$ のうちいくつに $\frac{1}{4}$ が含まれいくつに含まれていないかという情報が必要になり、それを $1,\frac{1}{2},\frac{1}{4},\ldots$ の全てではとても持たせていられない。

また、「1を $M$ 個の要素で作る場合の数 $D_M$ を求めておいて、$DP[i][j]+=DP[i][j-m] \times D_m$ を足し合わせる」みたいなことも、重複が発生しまくって、上手い除き方がわからない。

ここでは、以下の2つが同じことに気付けば見通しが立つ。

  • $N$ 要素で総和が $2K$ の、$1,\frac{1}{2},\frac{1}{4},\ldots$ からなる多重集合の個数
  • $N$ 要素で総和が $K$ の、$\frac{1}{2},\frac{1}{4},\frac{1}{8},\ldots$ からなる多重集合の個数

つまり、$DP[i][j]$ を求めたいとき、その中に“1”が存在するか否かで遷移元を変えて、

  • 存在するとき
    • 1を1つ除いた場合の数をそのまま引き継ぐ
    • $DP[i-1][j-1]$
  • 存在しないとき
    • 上記の言い換えで、要素数 $i$、総和 $2j$ の時の場合の数と等しい
    • $DP[i][2j]$
    • ただし問題設定から、$DP[i][i]=1$、また $i \gt j$ のとき $DP[i][j]=0$
  • まとめて、
    • $DP[i][j]=DP[i-1][j-1]+DP[i][2j]$

$i$ の小さい方、$j$ の大きい方からDPテーブルを埋めていくことで、$O(N^2)$ で全て埋められる。

Python3

E - Mex Mat

問題

  • $N \times N$ のグリッドがあり、各要素は $0,1,2$ からなる
  • 先頭行と先頭列は与えられる
  • それ以外のマスの要素は、自身の1つ上と1つ左のマスの要素のMexとなる
    • Mexはその集合に含まれない最小の非負整数。詳細は問題ページ参照
  • グリッド内の $0,1,2$ の要素の各個数を求めよ
  • $1 \le N \le 5 \times 10^5$

解法

こういうのは、問題文の操作通りにシミュレーションするコードを書いて実験する。
シミュレーションは簡単に書けるし、見た目上わかりやすい性質が表れてくれたら「何も無いところから性質を見つける」より「仮説を証明する」方が一般的には簡単。

すると、幾らもしないうちにナナメ↘に同じ数字が並び始めることが分かる。

2 1 0 0 1 1 2 1 1 1
2 0 1 2 0 2 0 2 0 2
2 1 0 1 2 0 1 0 1 0
0 2 1 0 1 2 0 1 0 1
0 1 0 1 0 1 2 0 1 0
0 2 1 0 1 0 1 2 0 1
1 0 2 1 0 1 0 1 2 0
2 1 0 2 1 0 1 0 1 2
2 0 1 0 2 1 0 1 0 1
2 1 0 1 0 2 1 0 1 0

ナナメに同じ数字が続くなら、実際にシミュレーションしなくても計算で個数は求められる。
必ずそうなるのか確かめる。

まず、所与である1行目・1列目を除いて、“0”の右下は必ず“0”となる。

0 A    A: 左に0があるので0にはならない
B C    B: 上に0があるので0にはならない
       C: 左も上も0ではないので0

また、(しばらく行が進んだ)隣接する3本のナナメ↘ラインには、必ず1つは“0”が含まれる。

↘↘
↘ A B        B,C がともに非0なら、Aは0でないと矛盾
   C A D      一度0になると先ほどの条件よりずっとAは0
     E A F

なので、“0”は、ナナメラインで1個おきか、2個おきに現れることとなる。
1個おきの場合は間の数字は1に収束し、2個おきは色々試すと 0 1 2 0 または 0 2 1 0 に収束する。

収束までにかかる回数はちょっと厳密に分からないが……

  • 1行目は同じ数字が連続しうるので、「“0” 以外が隣接3本のナナメラインで続かない」性質が2行目の時点では現れないことがある
  • 2行目は同じ数字が連続しないので、3行目ではその性質は保証される
  • その時、“0”の間の数字が収束する値とは異なる場合があるが、4行目、5行目と繰り返す内にほぼすぐ収束する(はず)

よって、念のためでも行・列それぞれで10回程度シミュレーションすればまず収束し、個数を求められる。

収束するまでのシミュレーションは1行 or 1列あたり $O(N)$ でできる。

Python3

D問題が苦手すぎたのが逆に功を奏してE問題に取りかかれたのがよかったかも。

F - Sum of Abs

問題

解法



programming_algorithm/contest_history/atcoder/2020/1031_arc107.txt · 最終更新: 2020/11/04 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0