2021-03-05

Codeforces Round #698 (Div. 2) 1478C - Nezzar and Symmetric Array

問題

Problem - C - Codeforces

$a$ を、 $2n$ 個の相異なる整数からなり、任意の $a_i$ に対して $a_i = -a_j$ となる要素 $a_j$ が存在する配列とする。

配列 $a$ から生成した配列 $d$ が与えられる。

ここで、 $\displaystyle{ d_i = \sum_{j=1}^{2n}|a_i - a_j| }$ である。

元の配列 $a$ は存在するだろうか。

解法

Editorial of Codeforces Round #698 (Div.1, Div.2) - Codeforces

Editorialを軸に説明を進める。

前提

$\displaystyle{ \begin{aligned} d_i = d_j & (a_i = -a_j) \\ d_i \neq d_j & (a_i \neq -a_j) \end{aligned} }$

つまり、 $d$ に相異なる $n$ 個の整数が2つずつ含まれていない場合、答えはNO。

この事実から、一般性を失わず、

$0 \lt a_1 \lt a_2 \lt \cdots \lt a_n$ かつ、任意の $i$ に対して $a_{i + n} = -a_i$

$0 \lt d_1 \lt d_2 \lt \cdots \lt d_n$ かつ、任意の $i$ に対して $d_{i + n} = d_i$

と仮定する。

式変形

前提より、 $1 \leq i \leq n$ において、

$\displaystyle{ \begin{aligned} d_i &= \sum_{j=1}^{i}(a_i - a_j) + \sum_{j=i+1}^{n}(a_j - a_i) + \sum_{j=1}^{n}(a_i + a_j) \\ &= 2ia_i - \sum_{j=1}^{i}a_j + \sum_{j=i+1}^{n}a_j + \sum_{j=1}^{n}a_j \\ \end{aligned} }$

差分をとると、

$\displaystyle{ \begin{aligned} d_{i+1} - d_i &= 2(i+1)a_{i+1} - 2ia_i - 2a_{i+1} \\ &= 2i(a_{i+1}-a_i) \end{aligned} }$

つまり、 $d_{i+1} - d_i$ が $2i$ で割り切れない場合、答えはNO。

確認

$a_1 \gt 0$ ならば、 $d_{i+1} - d_i \gt 0$ より、 $1 \le i \le n$ において $a_i \gt 0$ 。

また、 $1 \le i \lt j \le n$ において $a_{i+1}-a_i$ から $a_j - a_i$ が求まるので、

$\displaystyle{ \begin{aligned} d_1 - 2\sum_{i=1}^{n}(a_i - a_1) &= 2\sum_{i=1}^{n}a_i - 2\sum_{i=1}^{n}a_i +2\sum_{i=1}^{n}a_1 \\ &= 2na_1 \end{aligned} }$

つまり、 $a_1$ が0以下であるか $2n$ の倍数ではない場合、答えはNO。

コード(Rust)

Submission #109130082 - Codeforces

感想

Editorialを読んでも理解できなかったため、記事を書いてみた。

少しは苦手意識を克服できた気がする。

2020-10-04

ARC104 C - Fair Elevator

問題

C - Fair Elevator

解法

まず、各階に、乗った階が指定されている場合は $L$ を、降りた階が指定されている場合は $R$ をマークする（ $L$ 、 $R$ は階数と被らない何かしらの数）。ただし、どちらも指定されている場合は、乗った階に降りた階をマークする。このとき、以下の場合はNoとなる。

同じ階が指定されている。
乗った階より降りた階の方が下にある。

次に、下の階から順に、乗り降りした階を対応させていく。現在の階を $A$ とし、対応する可能性のある階を $B$ とすると、 $A+1 \leq B \leq 2N$ であり、この範囲を全探索すれば良い。

ここで、 $A$ と $B$ を対応させた場合、 $C = B - A$ とすると、 $A \leq X \lt B$ において、 $X$ と $X + C$ は制約上対応しなければならない。つまり、これらが対応できる場合、次に探索するのは $B + C$ 階からとなる。ただし、以下の場合は $A$ と $B$ を対応することはできない。

$B + C \gt 2N + 1$ （ $X$ と対応する階がない）。
$X$ に降りた階 $Y$ がマークされているが、 $Y - X \neq C$ である。
$X$ に $R$ がマークされている。
$X + C$ に $L$ や降りた階がマークされている。
$X$ に $L$ 、 $X + C$ に $R$ がマークされている（異なる人物の記録は対応できない）。

最後に、ある対応付けが上手くいった場合はYesである。上手くいかなかった場合は、探索開始が同じであれば結果は同じとなるので、メモしておく。よって、動的計画法の考え方に帰着された。計算量は（恐らく） $O(n^3)$ である。

コード

Submission #17181371 - AtCoder Regular Contest 104

感想

場合分けが多いと厳しい。

2020-08-20

ABC161 D - Lunlun Number

問題

https://atcoder.jp/contests/abc161/tasks/abc161_d

$K$ 番目のルンルン数を求めよ。

解法

今のルンルン数から次のルンルン数を求める方法を考える。

ルンルン数をある程度列挙して眺めてみると、繰り上がりが起きた桁は、一つ上位の桁より1小さい（0の場合は0）となっていることがわかる。

このことから、繰り上がりが起きない桁を見つければ良い。

この桁は、下位桁から順に、1を足した値が制約を満たしているかを確認していけばわかる。

あとは、その桁より下位の桁を、1を引いた値（0の場合は0）にしていけば良い。

計算量は、K番目のルンルン数を $L_{k}$ とすると、 $O(Klog_{10}L_{k})$ である。

コード

https://atcoder.jp/contests/abc161/submissions/16055536

一言

考察が逐次更新に偏ってしまい、全列挙に辿り着かなかった。

（ACできたので結果オーライではあるが）

2020-08-15

yukicoder No.1170 Never Want to Walk

問題

https://yukicoder.me/problems/no/1170

座標が $x_{i}$ である $N$ 個の駅がある。 $A \leq |x_{i} - x_{j}| \leq B$ のとき、駅 $i$ と駅 $j$ に無向辺が張られている。各駅が含まれる連結成分の数を求めよ。

解法

座標が小さい順に見ていく。

Union-Findを用いて、各駅 $i$ における、 $x_{i} + A$ から $x_{i} + B$ の間に存在する駅を（二分探索等で列挙し）uniteすることで、 $O(N^{2})$ で求めることができるが、これだとTLEしてしまう。

そこで、尺取り法を用いる。
具体的には、一つ前の駅において最後に辺が張られた駅（無ければ自分自身）を保存しておき、そこから探索を始める。
そうすることで、一つ前の駅と範囲が被っている部分は、最後に辺が張られた駅がuniteされることでカバーされるため、重複部分を探索する必要がなくなり、おおよそ $O(N)$ で求めることができる。

コード

https://yukicoder.me/submissions/530719

一言

尺取り法楽しい。

2020-08-14

Codeforces 1391D 505

問題

https://codeforces.com/problemset/problem/1391/D

$n$ 行 $m$ 列の01行列 $a$ において、全ての部分偶数長正方行列に含まれる1の数を奇数にするための最小操作回数を求めよ。

解法

$n \leq m$ とする（そうでない場合は $a$ を転置）。

$n = 1$ の場合、部分偶数長正方行列は存在しないため $0$ 。

$n = 2$ の場合、 $a_{00} + a_{10}$ の偶奇を決めてしまえば後の列の偶奇は自然に定まるため、2通り試す。
偶奇の状態は、00 or 11、01 or 11であり、どの調整も1回の操作で済む。

$n = 3$ の場合、 $a_{00} + a_{10}$ と $a_{10} + a_{20}$ の偶奇を決めてしまえば後の列の偶奇は自然に定まるため、4通り試す。
偶奇の状態は、000 or 111、001 or 110、010 or 101、011 or 100であり、どの調整も1回の操作で済む。

$n \geq 4$ の場合、 $4 \times 4$ の正方行列が必ず含まれ、それに含まれる4つの $2 \times 2$ の正方行列とそれ自身は同時に条件を満たすことができないので $-1$ 。

コード

https://codeforces.com/contest/1391/submission/89863543

一言

自力ACではないが、久しぶりに書いてみたくなったので書いた。

2020-06-05

ABC147 E - Balanced Path

問題

E - Balanced Path

コード

Submission #14018954 - AtCoder Beginner Contest 147

解法

左上のマスから右下のマスまで移動した際に、通ったマスに書かれている2つの数の差の絶対値を足すか引くかした値の絶対値を $x$ とすると、 $x$ の最小値を求めたい。

これは、マス $(i,j)$ までに $x$ の値を $k$ にすることができるかというbool値を $dp_{ijk}$ として管理すれば求めることができる。

遷移としては、 $dp_{ijk}$ がtrueの場合、次のマス（ $dp_{(i+1)j}$ または $dp_{i(j+1)}$ ）は、次のマスに書かれている2つの数の差の絶対値を $y$ とすると、 $k + y$ 、 $abs(k - y)$ 、 $abs(y - k)$ のときtrueとなる。

計算量は、 $O(HW(H + W) \cdot max(abs(A_{ij} - B_{ij}))$

感想

安定の解説ACではあるが、競プロへのモチベが微妙なので諦め。

Rust勉強中のため、コードは冗長かもしれない。

2020-04-29

ABC136 D - Gathering Children

問題

D - Gathering Children

解法

$10^{100}$ 回の移動後は必ずRLとなっている箇所に集まるので（それ以外では明らかにループしない）、その箇所に集まる人数を求めれば良い。

あるRLとなっている箇所における左側のRの個数を $r$ とすると、 $10^{100}$ は偶数であることから、 $\lceil \frac{r}{2} \rceil$ 人が左に集まり、 $\lfloor \frac{r}{2} \rfloor$ 人が右に集まる。
このことは、一番Lに近いRの位置に居た人が偶数回動くと元の位置に戻ってくることを考えるとわかりやすい。
右側のLの個数 $l$ についても同じようなことが言えるが、集まる位置が左右逆になるので注意が必要である。

$r$ と $l$ の求め方としては、 $i$ がRの左端とすると、 $i+r-1$ がRの右端、 $i+r$ がLの左端、 $i+r+l-1$ がLの左端となることを考えると、実装が楽になる。

コード

Submission #12485674 - AtCoder Beginner Contest 136

感想

綺麗に実装出来たので気持ちよかった。

Strorkisのブログ

信憑性については悪しからず