2021-03-28

AtCoder Beginner Contest 197（Sponsored by Panasonic）参加記（～E問題）

競プロ解説参加記

D問題みたいな数学問題もっと出してもいいんですよ
f:id:mmnkblog:20210328022948p:plain

A - Rotate

文字列で受け取ってもいいが、文字変数を3つ用意して入力順と出力順を入れ替えた方がシンプルに書ける。

計算量は、 $O(1)$ 。

B - Visibility

むずくない？

マス $(X, Y)$ から始めて、上下左右の4方向に向かって探索する。もし探索途中に#が出現したら、それより奥のマスは障害物で遮られて見えないので探索をやめる。この個数をカウントしたものが答え。

計算量は、入力がボトルネックで $O(HW)$ 。探索自体は $O(H+W)$ である。

「長さ $N$ の数列を1つ以上の空でない連続した区間に分ける」、つまり、各要素の間に区切りを入れるか・入れないかを独立に選択する方法は全部で $2^{N-1}$ 通り。制約より $N$ は最大でも $20$ なので、全パターンを試しても間に合う。こういう、「選ぶか」「選ばないか」の2択をいくつか選択するような状況の全探索にはbitを活用する。（bit全探索という）
C＋＋では、ORの計算はa|b、XORの計算はa^bと書くことで簡単に計算できる。

計算量は、 $O(N2^N)$ 。

D - Opposite

正多角形の座標のうち、一番離れている2点の座標が与えられる。 $N$ は偶数なので、この正多角形の中心の座標がわかる。
また、正多角形の隣り合う頂点は、正多角形の中心から見てちょうど $\dfrac{2\pi}{N}$ だけ回転している。2次元平面状の座標を回転させるには、回転行列を用いるとよい。具体的には、
$\begin{pmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{pmatrix} \begin{pmatrix} x\\ y \end{pmatrix}= \begin{pmatrix} x\cos \theta -y\sin \theta \\ x\sin \theta + y\cos \theta \end{pmatrix}$
を用いればよい。ググると出てくる。
答えが小数になるため、誤差に注意。

計算量は、 $O(1)$ 。

E - Traveler

色 $i$ のボールを回収するとき、現在の座標を $x$ とすると、
・負の方向に進んでから正の方向に進む
・正の方向に進んでから負の方向に進む
という2通りの行動以外は最適な行動ではない。（引き返した分の時間が損であり、引き返さなくてもすべてのボールを回収できる行動が存在するため。）

つまり各色のボール群を回収する際は上記の2通りの行動のうちどちらかを選んで行動する。この時点で全通りを試すと $O(2^N)$ の計算量となり、実行時間制限に間に合わない。
ここで、ある色までのボールを回収し終えた時点での座標は、その色のボール群のうち一番座標が小さいボールがあった位置か一番座標が大きいボールがあった位置かのどちらかである。それまでの行動を考慮しなくても、前の段階での終了時の座標を全通り試すだけで最適解が求まる。これを、動的計画法（DP）という。

よって、ひとつ前の色の座標の候補（2通り）と、ボールを回収するときの行動パターン（2通り）の全パターンを試して最適なものを選択していけばよい。

計算量は、 $O(N)$ 。

感想

EのDPは比較的簡単な方の部類だと思うのだが、コンテスト中は嘘の貪欲を書いていた。強くなりたい…！

2021-03-21

AtCoder Beginner Contest 196参加記（～E問題）

競プロ解説参加記

水色なのにCでWA出たのでだめです
f:id:mmnkblog:20210321031700p:plain

A - Difference Max

$x$ を大きくすると $x-y$ の値も大きくなる。逆に、 $y$ を大きくすると $x-y$ の値は小さくなる。なので、 $x-y$ の値を最大化する場合、 $x$ は最大に、 $y$ は最小にすればよい。つまり $b-c$ が答え。
最大化するときの基礎的な考えが問われる良問。

計算量は、 $O(1)$ 。

B - Round Down

C++を使ってる前提で話すと、 $10^{100}$ なんてデカい数は扱えない。文字列で受け取れば、「小数点以下を切り捨て」したいので、文字列の先頭からピリオドが登場する手前までを切り取って出力すればよいことがわかる。先頭から1文字ずつピリオドかどうか判定しながらちまちま出力すればよい。

計算量は、 $O(\log N)$ 。

C - Doubled

解けなかった。
制約がある程度大きいので $O(1)$ で解こうと思ったがどこかで実装をバグらせたらしくWAが出た。想定解は前半の桁だけ全探索して $N$ 以下か判定するというもの。発想としては全く難しくない。過去に類題も出てるのになぜその発想に至らなかったのか…。

計算量は、 $O(\sqrt N)$ 。

D - Hanjo

制約が小さいので、ピースの置き方を全探索する。再帰関数によるDSFを書いた。残りの畳の枚数と現在の敷き詰め状態を引数として渡す。もし空白のマスが存在していたら、そこに「縦長」「横長」「正方形」の3種類を敷き詰めた状態をそれぞれ作って再帰呼び出しする。もう置けない状態なら1を返す。こう書くと、返ってきた値の総和が求める通り数になる。状態数は超ざっくり見積もって最悪でも $3^{16} = 43,046,721$ 通りしかない（実際にはさらに少ない）ので全探索しても実行時間制限に十分間に合う。

E - Filters

考察を書く。間違っている可能性が大いにある。

$\max(x, a_i)$ もしくは $\min(x, a_i)$ が登場するまでに $x$ に足された数の合計を $S$ とすると、 $\max(x + S, a_i)=\max(x, a_i - S) + S$ である。クエリが来る前段階で $a_i - S$ は定数なのでこの答えはすぐに求められる。さらに $\min(x + S, a_i) = -\max(-x, -a_i+S)-S$ と書ける。さらにさらに、 $\max$ 関数の定義から、 $x$ のほうが選ばれなければそれ以降 $x$ が解に干渉してくることはない、つまり前から見て $k$ 番目の $\max$ 関数で $x$ のほうが採択されなかったときの答えは事前に計算しておくことが可能である（計算量の話はあとで考える）。なので、 $x$ と $-x$ のどちらかがある定数より小さいことが判明すれば、その時点で解が定まる。 $\max$ 関数が $K$ 個あったとすれば、数直線が $K+1$ 個の区間に分割され、さらにクエリで与えられる数値はその区間のどこかに必ず含まれる。

つまりどういうことかというと、「クエリで与えられた $x_i$ 」と「 $\max$ 関数のしきい値」をソートして前から見ていけば $O( (N+Q)\log(N+Q) )$ で答えが求まるのではないか？ということだ。
この「数直線を $K+1$ 個の区間に分割する」ことで先ほどの前計算（ $x$ が絡まない場合）の解も求められそう。（ここが求められずに時間が来てしまった）

ここで脳みそが疲れたのでやめた。
公式解説によると、この定義の関数は合成することができるらしく、「定数（低）」「 $x+\alpha$ 」「定数（高）」の3パターンしかないとのこと。クエリの数がバカ多いので合成できそうだとは思ったが合成した後のグラフの形がなぜエスカレーターみたいになるのかはわからなかった。

F - Substring 2

問題文がシンプルで簡単そうだがFFTを使うらしい。FFTってなんですか？

感想

コンテスト終了後もE問題を粘って解いていたが頭が腐っていたので解けなかった。レートが20くらい無くなった

2021-03-15

AtCoder Regular Contest 114参加記（～B問題）

競プロ解説参加記

早解きの巻

f:id:mmnkblog:20210315012932p:plain

A - Not coprime

互いに素でないということは、 $X_i$ と $Y$ に共通の素因数が存在するということと同値である。制約より、 $Y$ は最大でも $50$ 以下の素数の積（およそ $6.1\times 10^{17}$ ）にしかならない。さらに、 $50$ 以下の素数それぞれに対して「 $Y$ に含めるか」「含めないか」の2択を選ぶbit全探索をして全通り試してもも実行時間制限にも十分間に合う。
ちなみに $50$ 以下の素数は $15$ 個。素数リストを実行時に生成してもよかったが、ライブラリを引っ張り出してくるより暗記しているものを書き出したほうが早かった。

計算量は、 $O(N \pi(\max(X)) 2^{\pi(\max(X))})$ 。

B - Special Subsets

全射の整数集合が与えられていて、その部分集合のうち全単射であるものはいくつあるか？という問題。（たぶん）
この集合と関数の関係は、 $a\to f(a)$ へと有向辺を生やしたグラフと等価である。このグラフは、頂点数と辺数がそれぞれ $N$ で等しい。
また、関数が全単射であるとき、有向グラフはいくつかの重複しない閉路のみからなるグラフとなる（必ずしも連結とは限らない）。
つまり元のグラフのなかに閉路がいくつ存在するかがわかればよい。これは単純にDFSで閉路判定をすればよいし、「頂点数と辺数が等しいグラフの閉路の数は、連結成分の数に等しい」という定理をもちいてUnionFindなどを用いて連結成分の数を持つだけでも良い。
閉路の数を $C$ とすれば、答えは $2^C - 1$ である。

計算量は、 $O(N)$ 。

感想

Cは解けなかった。サンプルが合わなかった。
D問題をみて「貪欲かな～」と思ったけど、順位表を見るとD-EのAC数が逆転していたのでC問題をずっとにらんでいた。貪欲は嘘解法らしく一安心。

個人的に早解きで暖まるのは申し訳ない気持ちになる。

2021-03-07

AtCoder Beginner Contest 194参加記（～F問題）

競プロ解説参加記

Fがむずすぎる
青パフォ
f:id:mmnkblog:20210306225900p:plain

A - I Scream

読解力が試される。問題文の太字で書かれたところはすべて入力で与えられる $A, B$ に置き換えられる。if文で処理する。

計算量は、 $O(1)$ 。

B - Job Assignment

問題文を読んだ時点で、計算量が $O(N)$ でも解けることを確信したので制約を見ていなかった。実は $O(N^2)$ でも通るらしい。こういうところで実装をサボらないとなんだか損した気分になる。

コンテスト中は場合分けして $O(N)$ で解いた。

1. 仕事 A と仕事 B をそれぞれ別の従業員に割り当てる場合
$A_i$ の最小値を $A_{\min}$ 、 $B_j$ の最小値を $B_{\min}$ とする。
$A_{\min}$ 分で仕事ができる従業員と、 $B_{\min}$ 分で仕事ができる従業員がそれぞれ別になるように割り当てられるか調べる。具体的には、
・ $A_i = A_{\min}$ となるような $i$ が2個以上ある場合
・ $B_j = B_{\min}$ となるような $j$ が2個以上ある場合
・ $A_i = A_{\min}$ となるような $i$ が1個のみ　かつ　 $B_j = B_{\min}$ となるような $j$ が1個のみ　かつ　 $i \neq j$
のどれかの場合、答えは $\max (A_{\min}, B_{\min})$ となる。上記に当てはまらない場合、 $A_i = A_{\min}$ を満たす従業員 $i$ が仕事Aか仕事Bを行うのは確定しているので、従業員 $i$ を除いた $N-1$ 人の中で一番早く仕事Aもしくは仕事Bをこなすことができる従業員をkを探す。よって答えは $\min(A_k, B_k)$ となる。

2. 仕事 A と仕事 B をどちらも同じ従業員に割り当てる場合
答えは $A_i + B_i$ の最小値である。

これらの答えの最小値が最終的な答えである。

計算量 $O(N^2)$ で解くなら、従業員のペアを全探索してシミュレーションし、その最小値を求めればよい。

C - Squared Error

式が正しいかどうか自信が無いがとりあえず書いておく（間違ってたらごめんなさい）。
式変形すると、
$\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2$
$= \displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} (A_i^2 + A_j^2 - 2 A_i A_j)$
$= \displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} A_i^2 + \sum_{i=2}^N \sum_{j=1}^{i-1} A_j^2 -2 \sum_{i=2}^N \sum_{j=1}^{i-1} (A_i \times A_j)$
となる。

ここで、
$\displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} A_i^2 + \sum_{i=2}^N \sum_{j=1}^{i-1} A_j^2 = \sum_{i=1}^N (N-1)\times A_i^2$
であり、
$\displaystyle \sum_{i=2}^N \sum_{j=1}^{i-1} (A_i \times A_j) = \sum_{i=2}^N (i \times \sum_{j=1}^{i-1} A_j)$
である。これは累積和を用いることで $O(N)$ で求められる。（参考：過去問に下位互換となる問題が出題済み。C - Sum of product of pairs）

よって全体でも計算量 $O(N)$ で答えを求めることができる。

D - Journey

わかってないけどAC。
まだ選ばれていない頂点が選ばれると、「すでに選ばれた頂点の集合（連結）」と連結になる。つまり、最初に高橋君がいる頂点1以外の $N-1$ 頂点をすべて選ぶまでの回数の期待値は？という問題になる。これはたしかガチャコンプ問題とかいう名前（俗称）がついていて、結構頻繁に出題されている（のに、未だに理解できていない）。

期待値の求め方がわからないので「期待値　回数　計算」でググると高校数学の美しい物語さんがヒットする。
mathtrain.jp

ここにそのまま答えが書いてある。どうやら期待値は漸化式を使って表現できるらしい。 $k$ 種類すでに引いている場合の期待値を考えると上手くいく？
とりあえず漸化式が立てばそれを更新していくだけなので、計算量は $O(N)$ である。

期待値の問題が苦手ということがわかったのでどこかで特訓したい（しない）

E - Mex Min

数列 $A$ のなかで、連続する $M$ 個の $\mathrm{mex}$ の最小値は？という問題。

$\mathrm{mex}$ 関数の定義より、 $M$ 個ある整数の中に、とある整数 $K$ が含まれていなければ、 $\mathrm{mex}$ 関数の返す値は少なくとも $K$ 以下となることがわかる。なので、 $0$ から $N-1$ までの整数 $K$ それぞれに対して、 $K$ が含まれない区間の長さの最大値が求められれば良い。これは、数列を前から舐めていって、各整数の直前の出現位置をメモしておけば解くことができる。

あとは $0$ から小さい順に、整数 $K$ が含まれない区間の長さの最大値は $M$ 以上かを判定してやればよい。

計算量は、 $O(N)$ 。

F - Digits Paradise in Hexadecimal

桁DPっぽさがある。
dp[i桁目まで確定][N未満フラグ][Leading Zeroを抜けたかフラグ][iビット目：iをすでに含んでいるか？を保持するフラグ(16bit)] := 総数
とすると解けそうだが、計算量が(dはd進数であることを示す、本門ではd=16) $O((Nの桁数)\times d 2^d)$ 程度になり、これは $10^{10}$ 回程度の計算が必要になるので間に合わない。

どうやら桁DPをしなくても解けるらしい。わかりません。

感想

Bがむずすぎる

2021-02-22

SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)参加記（～E問題）

競プロ解説参加記

f:id:mmnkblog:20210222021259p:plain

A - Star

高橋君が最後に ~~1UPキノコ~~ ご褒美をもらったあと何枚コインを集めているかわかるなら、 $100$ からその枚数を引けば必要な枚数がわかる。これは剰余算を用いて計算することができる。答えは $100 - (X \% 100)$ となる。

計算量は、 $O(1)$ 。

B - uNrEaDaBlE sTrInG

まず前提として、「ある文字が英大文字か？」を判定する関数と、「ある文字が英小文字か？」を判定する関数を書いてしまう（標準で用意されているなら使い方を調べる）。こうすることで考えることを減らせるし、デバッグの速度も上がる。

文字列を先頭から一文字ずつ見ていき、奇数番目の文字なら英小文字か判定して、偶数番目の文字なら英大文字か判定すると解ける。一文字でも条件を満たしていないのなら答えはNoである。

主要な言語だと配列や文字列の添え字番号は0から始まるので、奇数・偶数が入れ替わるのがややこしいところ。

計算量は、 $O(|S|)$ 。

C - Kaprekar Number

とりあえず、 $g_1(x)$ と $g_2(x)$ を実装する。これは、整数を文字列に変換してからソートしてまた整数に戻す、という処理で実現可能である。これらの関数があれば、定義通り $f(x)$ も問題なく実装できる。 $f(x)$ の計算量は $O(\log x)$ である。

この関数 $f(x)$ についての漸化式が与えられている。制約を見ると求める項は最大でも $10^5$ 番目までなので、愚直に漸化式の定義通り計算しても間に合う。

計算量は、 $O(K\log N)$ 。

D - Base n

誤読した。1桁のとき、何進数でも $M$ 以下になるじゃねえか！と思って15分経ったところでclarを投げたところ、10秒でテンプレ質問が返ってきたのでいったん別の問題に逃げた。

再び戻ってよく読むと、 $n$ の種類数ではなく、計算して得られる値の種類数を求める問題だった。なにこれ？あほくさ

$X$ の長さが $2$ 以上のとき、 $n$ の値が大きくなると得られる値も大きくなる。つまり、 $n$ について条件を満たす境界を二分探索で探すことができる。 $X$ の長さが大きい時、 $n$ が1増えるだけで指数的に増加する場合があるのでオーバーフローに注意しながら実装すること、解が $0$ 種類になるパターンもあること、 $X$ の長さが $1$ のときの場合分けなど、考えることが多い。しかも問題文がわかりづらくて誤読したせいで解いた時の達成感が無かった。クソ

計算量は、 $O(|X|\log M)$ 。

E - Train

都市を頂点、鉄道路を辺と見たグラフを考える。このグラフの頂点 $X$ から各頂点までの最短コスト（問題文中では到着までにかかる時間）を求めたいので、ダイクストラ法が適用できないか考える。

辺のコストが固定ですべて正のコストならばダイクストラ法を適用できる。もし列車が発車するタイミングちょうどに出発都市に到着した場合、コストは $T_i$ である。もし発車までに時間があるなら、その時間をコストに追加してやればよい。頂点への到着時刻を $t$ とすると、 $t-(t\%K_i)+K_i$ がコストとなる。よって、最短コストで移動している場合の辺のコストは固定であるとみなすことができ、すべて正のコストであるので、ダイクストラ法を適用することができる。

計算量は、 $O(N+M\log N)$ 。

F - Potion

まだちゃんと読んでない。DPっぽい。

感想

誤読も競プロのうちだけど、運営陣の発言を見てるとなんかモヤモヤするんだよなあ。どうにかならないのかな。

2021-02-22

AtCoder Regular Contest 113参加記（～D問題）

競プロ解説参加記

いろいろ悔しい
f:id:mmnkblog:20210221230637p:plain

A - ABC

最初、 $ABC=K$ と誤読していた。サンプルで気付くまで15分かかった。ダメ。

$K$ は定数なので、たとえば $A$ を固定すると条件式が $BC\le \dfrac{K}{A}$ となる。この式を満たす正の整数の組 $(B, C)$ の個数は、 $\dfrac{K}{A}$ 以下の整数それぞれの約数の個数の総和に等しい。

よって、 $1$ から $K$ までの整数それぞれの約数の個数が高速に求められれば良い。これは計算量 $O(K\log K)$ で求められる。これらの結果に累積和を適用することで、答えが求まる。

計算量は、 $O(K\log K)$ 。

B - A^B^C

$10$ 進法での $1$ の位というのは、 $\bmod 10$ の値のことを指す。なので、はじめに $A$ の値は $\bmod 10$ で持って良い。

ここからの議論があいまいだが、ある程度大きい定数 $k$ に対して
$A^k \equiv A^{k+4} \pmod{10}$
である。よって、 $B^C\bmod 4$ の値がいくつか分かれば答えが求まることになる。具体的には、

$B \equiv 0 \pmod{4}$ ならば $B^C \equiv 0 \pmod{4}$
$B \equiv 1 \pmod{4}$ ならば $B^C \equiv 1 \pmod{4}$
$B \equiv 2 \pmod{4}$ かつ $C=0$ ならば $B^C \equiv 2 \pmod{4}$
$B \equiv 2 \pmod{4}$ かつ $C\neq 0$ ならば $B^C \equiv 0 \pmod{4}$
$B \equiv 3 \pmod{4}$ かつ $C\equiv 0 \pmod{2}$ ならば $B^C \equiv 3 \pmod{4}$
$B \equiv 3 \pmod{4}$ かつ $C\equiv 1 \pmod{2}$ ならば $B^C \equiv 1 \pmod{4}$

となる。あとは計算して、最後に $10$ で割った余りを出力すればよい。例外的に、 $B\le 8$ かつ $C\le 8$ の場合は場合分けを通さずに実際に $A^{B^C}$ を計算した。

計算量は、 $O(1)$ 。

C - String Invasion

手元で実験してみると、ある場所でaabのような並びがあった場合連鎖的に操作が行え、文字列の末尾まですべてaで置き換えることができる。また、aab...ccd...というように2か所以上操作が行える箇所が存在した場合、より後ろにあるものから操作しても解は悪化しない。よって、文字列を後ろから見ていくことにする。

ある文字が連続していた場合、基本的にはその箇所より後ろにある文字全てが操作によって置き換わることになる。1回の操作で1文字置き換わるので、 $i$ 文字目と $i+1$ 文字目が連続していた時、 $|S| - i - 1$ 回操作を行える。
ただし、連続している文字より後ろに、その文字と同じ種類の文字が存在していた場合は操作を行えない。ただしそこで操作の連鎖がストップするわけではなく、それより後ろにある違う種類の文字に対しては操作できる。つまり、「 $i+1$ 文字目より後ろにある文字のうち、文字 $s_i$ と文字の種類が同じである文字の個数」回は操作を行えない。この文字の個数は、「文字の種類」から「個数」を引ける構造を用意しておくことで簡単に調べられる。

以上の操作を文字列の後ろから実行して答えをカウントしていく。計算量は、文字の種類数を $C$ として $O(|S|C)$ 。

D - Sky Reflector

列A、Bを決めたときに矛盾なく数を埋められるか？を考えるとわかりやすい（と個人的に感じた）。

問題文の条件を言い換えると、

行 $i$ に書き込める整数は $A_i$ 以上 $K$ 以下
列 $j$ に書き込める整数は $1$ 以上 $B_j$ 以下

となる。さらにまとめると、

マス $(i, j)$ に書き込める整数の範囲は $A_i$ 以上 $B_j$ 以下

であることがわかる。

つまり、列 $A$ の最大値を $A_{\max}$ と固定すれば、各 $j$ に対して $A_{\max}\le B_j \le K$ が成立する。 $M$ 個ある要素 $B_j$ はそれぞれ独立である。よって、最大値が $A_{\max}$ であるような列 $A$ の個数を $C_{A_{\max}}$ とすると、 $C_{A_{\max}}\times (K - A_{\max} + 1)^M$ をすべての $A_{\max}$ に対して求め、その総和を取ったものが答えとなる。ここでの計算量は、 $O(K\log M)$ 。

$C_{A_{\max}}$ を求める。 $A_i$ の値は $1$ 以上 $A_{\max}$ 以下なら何でもよいが、どれか1個以上は $A_i = A_{\max}$ でなければならない。よって、
$1\le k \le K$ を満たす $k$ に対して、 $C_k = k^N - (k-1)^N$ が成り立つ。ここでの計算量は、 $O(K\log N)$ 。

まとめると、全体の計算量は、 $O(K(\log N + \log M))$ となる。

…ただし、 $N=1$ （または $M=1$ ）の場合は例外で、マス $(1, j)$ に書かれた整数は $B_j$ なので、 $B_j$ がすべて決まれば $A_1$ の値も決まる。よってこの場合の答えは $K^M$ となる。この場合分けを忘れて、コンテスト時間内のACを逃した…。（コンテスト後に気付いて場合分けを追加して提出したところ、ACした）くやしい。くやしい！！！！