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した）くやしい。くやしい！！！！

感想

マジで悔しい～～～～

2021-02-14

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

競プロ解説参加記

スーパー場合分けコンテスト（ABのみ）

f:id:mmnkblog:20210213234209p:plain

A - B = C

$A=B+C$ に変形すると負の値が登場しないので考えやすい。
各整数の下限が $0$ だった場合、 $A$ を固定すると $B+C$ は $A+1$ 通りとなる。この組の中で $B$ が $L$ 未満のものは $L$ 組、 $C$ が $L$ 未満のものも $L$ 組あるので正しい答えは $\max (A+1-2L, 0)$ となる。
これをすべての $L$ 以上 $R$ 以下の全ての $A$ に対して求めるとよい。

B - -- - B

公式解説では $C$ の偶奇で場合分けして考察していたが、僕は $B$ の正負（とゼロ）で丁寧に場合分けしてそれぞれの答えを書いた。
その中でさらに、 $B$ よりでかくなるパターン、 $-B$ 以上 $B$ 以下になるパターン、 $-B$ より小さくなるパターンにわけるとそれぞれの答えが簡単に求められる。
$-B$ 以上 $B$ 以下になるパターンの考察をミスして1WA。しょうもない。

C - DFS Game

部分木ごとに考えてよい。というところまではよくて、ある頂点から見た子の結果のうち何がわかれば部分木の答えが求まるのかがわからなかった。説明がふんわりでごめんなさい。理解してないからね。
その部分木に突入して戻ってきたとき、「片方が獲得できるコインの数」「もう片方が獲得できるコインの数」「戻ってきたときに次に子を選ぶ権利があるのは自分かどうか」みたいな情報があれば求められそうだった。が、これらの情報が子から複数来るので、何かの基準に合わせてソートしたりして選ばなければならない。わからない。

感想

コンテスト直後に最大深度6強の地震が起きた。日ごろから地震に備えよう

2021-01-30

AtCoder Beginner Contest 190参加記（～？問題）

競プロ解説参加記

萎えてるので手抜きです

f:id:mmnkblog:20210130232525p:plain

A - Very Very Primitive Game

場合分け

B - Magic 3

ループ

C - Bowls and Dishes

bit全探索

D - Staircase Sequences

N=A*Bと表したとき長さBで要素の平均がAであるような数列を考える

E - Magical Ornament

魔法石を頂点、「隣り合わせにできる関係性」を辺とみたグラフを考える
頂点C_iとC_jの距離をBFSで求めておく
架空の頂点0を追加してすべてのC_iとの間に辺を張ると始点終点を0とした巡回セールスマン問題と見れる

F - Shift and Inversions

見てねえよ

感想

D→A→B→Cの順で解いたあと、1時間かけてEを通したが、順位表を見るとEのAC数が821に対してFのAC数は1510であり、難易度逆転が起こっていた
2ペナかつ解くのが遅かったのもあり、問題単体で見れば青パフォのところなのにD早解きとほぼ同じパフォしかつかなかった
Eを提出してACが表示されたときはマジで膝を叩いて喜んだが、問題の体感難易度とパフォの数値が割に合わず興ざめした

自分がする対策としては

順位表を見て逆転が起きていないか常に監視する（マジで無駄）
とりあえずすべての問題を確認する
全完できる実力をつける
早解き力を付ける

あたりだと思いました

2021-01-24

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

競プロ解説参加記

DP回
100-200-0-400-500-0で0ペナ4完1200点。

A - Slot

$C_1 = C_2$ と $C_2 = C_3$ が真なら、 $C_1 = C_3$ も真である。if文で判定すると解ける。

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

B - Alcoholic

$i$ 番目のお酒を飲んだ時のアルコールの摂取量は、 $V_i\times \dfrac{P_i}{100}$ ml で求められる。 $1$ 番目から $i$ 番目までのお酒をすべて飲んだ時のアルコールの摂取量を計算していき、初めて $X$ を超えたときの $i$ が答えである。 $100$ で割ると誤差が出て怖いので、 $P_i$ を $100$ で割るかわりに $X$ を $100$ 倍すると整数のまま計算できる。

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

C - Mandarin Orange

解けなかった。いや、解けてたんだけど制約を見て $O(N^2)$ 解は通らないと判断して書かなかった（いいわけ）。

$l, r$ を決めたとき、区間 $[l, r]$ の最小値を $x$ とすれば、各皿ごとに $x$ 個のみかんを食べることができる。 $l$ を固定して考えたとき、 $r$ を増やしたときの最小値は $x\gets \min (x, A_{r})$ で更新できる。すべての $l, r$ について全探索して最大値を求めると、計算量は $O(N^2)$ となる。

実はこの問題は「ヒストグラムの最大長方形」の面積を求める問題に帰着できて（というかそのまま）、DPを使うことで $O(N)$ で解けるらしい。へ～

参考：
algorithms.blog55.fc2.com

D - Logical Expression

DP。
$x_0 \land x_1 \lor x_2 ...x_N$ という感じの式を考える（ただし前から順に評価していく）。 $i$ 回目の計算が終わった時点での答えはTrueかFalseのどちらかである。それぞれの答えとなるような変数の割り当て型の個数をそれぞれ $T_i, F_i$ とすると、 $i+1$ 回目の計算が終わった時点での答えも計算できる。

計算量は、 $O(N)$ 。 $N\le 60$ は、答えがオーバーフローしないための制約らしい。

E - Rotate and Flip

とりあえず、点 $(x, y)$ を回転させたり線対称な位置に移動させたりする更新を式で表す。

時計回りに $90$ 度回す

$x\gets y$
$y\gets -x$

反時計回りに $90$ 度回す

$x\gets -y$
$y\gets x$

$x=p$ を軸に対称移動させる

$x\gets -x+2p$
$y\gets y$

$y=p$ を軸に対称移動させる

$x\gets x$
$y\gets -y+2p$

これらの式を眺めてみると、点の位置の更新は
$x\gets Ax+By+C$
$y\gets Dx+Ey+F$
という式で表せることがわかる。さらに、これらの更新する式は重ねることができる。 $(x, y)$ の更新をする式を関数 $f((x, y), A, B, C, D, E, F)$ と見ると、関数の合成 $f(f(A', B', C', D', E', F'), A, B, C, D, E, F)$ は次のように表せる。
$x\gets A(A'x+B'y+C')+B(D'x+E'y+F')+C$
$y\gets D(A'x+B'y+C')+E(D'x+E'y+F')+F$

式を整理して
$x\gets (AA'+BD')x+(AB'+BE')y+C$
$y\gets (DA'+ED')x+(DB'+EE')y+F$
とすれば、関数の合成を $f(AA'+BD', AB'+BE', C, DA'+ED', DB'+EE', F)$ と一つの関数と見ることができる！（なげえ）