2018-09-30

ARC103 参加記録＆解説（C～E）

AtCoder プログラミング競技プログラミング

AtCoder Regular Contest 103 - AtCoder

結果はCE2完+D部分点で73位。黄色復帰！

今回、この獲得点数の人が180人くらいいたので、スピードも功を奏したと思います。

f:id:betrue12:20180930102724p:plain

C～Eを振り返ります。

C - /＼/＼/＼/

↑半角バックスラッシュが円マークになるので全角にしました…

C - /\/\/\/

解法

偶数番目と奇数番目に分けて考えます。変更個数を少なくするためには、それぞれ元から一番多かった数字を残したくなります。

一番多かった数字が異なっていれば、それらをそのまま採用できます。もし同じ数字だった場合は 数列に現れる数はちょうど2種類 という条件に反しないよう、片方を諦めて2番手にする必要があります。「奇数1番手+偶数2番手」と「奇数2番手+偶数1番手」の両方を試して、登場回数合計の多い（＝変更が少ない）ほうを採用します。

ACコード

D - Robot Arms

解法

必要条件を導出する

まず、解が存在する必要条件を考えます。いったん $x$ と $y$ の区別をなくし、「それぞれの腕が正負どちらの方向に伸びているか？」を考えます。これを符号付きで全部足し算したものが、最終到達地点の座標を足したもの、つまり $X_{i} + Y_{i}$ となります。

ある腕を、負から正に変更したとします。その腕の長さを $d_{i}$ とすると、 $-d_{i}$ だったものが $+d_{i}$ になるため、最終地点の座標の和は $+2d_{i}$ 加算されます。逆に正から負に変更した場合は $-2d_{i}$ です。

より一般的に言うと、腕の正負を入れ替えた時、その長さの2倍だけ座標和が変動します。奇数の長さで変動することはありません。つまり作らなければいけない最終到達地点 $(X_{1}, Y_{1}), ..., (X_{N}, Y_{N})$ について座標和を考えると、それらの差は全て偶数である、言い換えると偶奇が一致している必要があります。

まずこれが必要条件になります。

構成方法を考える

では、構成方法を考えましょう。作りたいパターン数が $N \le 1000$ というのはそこまで多い数ではないですが、何と使える腕の本数が $m \le 40$ しかありません。1つ1つのパターンを見て腕の長さを決めていく方法は無理そうです。どんな数でも作れる「必勝法」を考えたいです。

「どんな数でも作れる」の定石は $n$ 進数です。2進数を使うとすると、作りたい座標は $0 \le |X_{i}|, |Y_{i}| \le 10^{9} \fallingdotseq 2^{30}$ であり、腕40本でも足りそうな雰囲気です。ただ、 $x, y$ をそれぞれ作るとなると、それぞれに腕が30本必要そうに見えますし、不必要な腕をどう調整するかも難しく思えます。

ではどうすればいいかというと、 $x, y$ を それぞれ作る をやめて、同時に作る ようにします。1本の腕の方向を選ぶことで $x, y$ 両方の値を操作できれば、腕の数が足りそうです。もちろんこのままでは無理ですが、それを可能にするのが座標変換です。

$u = x+y, v = x-y$ として、 $uv$ 座標系を考えます。これは、座標平面を45度回転しているような変換です。

f:id:betrue12:20180930114650p:plain

このように変換すると、腕の4方向が「 $u$ と $v$ それぞれ、正負どちらの方向にはたらくか」の4通りに対応します。2つの値を同時に操作することができて、かつ「 $u$ は増やしたいけど $v$ は減らしたい」みたいな要求4パターン全てに対応できるのが嬉しいポイントです。

目的地の座標も変換して $(U_{i}, V_{i})$ と書くことにします。そうすると $0 \le |U_{i}|, |V_{i}| \le 2\times 10^{9} \fallingdotseq 2^{31}$ と値の範囲が変わりますが、腕は40本あるので大丈夫です。各腕に $1, 2, 4, 8, ..., 2^{30}$ を割り振って、これらの足し算引き算だけで目的の値を作ることを考えます。

普通の0 or 1の2進数とは違い、-1 or 1の2進数（？）となっていますが、以下のように「大きい方から選ぶ」ことを考えればよいです。

f:id:betrue12:20180930115950p:plain

常に目的の値に近づく方向に正負を採用していけば、最後は目的の値に辿り着きます。実際には目的の値が「3」のような小さな数のときでも、もっと大きな値を組み合わせて作ることになりますが、その場合でも考え方は同じです。

ただしこれがキレイに収まるのは $U_{i}, V_{i}$ が奇数の場合で、偶数の場合は最後にもう1つ1を付けて調整してあげる必要があります。

※ $U_{i}$ と $V_{i}$ の偶奇は一致するため、片方では追加で1が必要だけどもう片方では余計、という事態にはならないので安心です。

f:id:betrue12:20180930120955p:plain

これで解けました。解法をまとめると、

まず目的地の座標和の偶奇が一致しているかチェック。一致していなければ解なしで終了。
座標変換を行う。
腕の長さとして $2^{30}, ..., 4, 2, 1$ の値を用意する。目的地の座標和が偶数の場合、さらに1を足す。
それぞれの目的地ごとに、大きい方の腕から方向を決めていくことで目的の値を作る。

これで解けます。

ACコード

（C++）Submission #3305898 - AtCoder Regular Contest 103

※部分点解法は、全部の腕の長さを1にしても足りるので、偶奇チェックした後は全部1で作ります。部分点獲得コードはこちら。

E - Tr/ee

解法

必要条件を導出する

これも、まず必要条件を考えます。

サイズ1の連結成分は必ず作れる。葉だけを切断するとサイズ1の連結成分になるため。
サイズ $n$ の連結成分は必ず作れない。サイズ $n$ の木を切断するとそれぞれの部分木のサイズは $n$ 未満になるため。
サイズ $i$ の連結成分が作れるならば、サイズ $n-i$ の連結成分も作れる。切断によってサイズ $i$ の連結成分ができたとき、もう片方はサイズ $n-i$ になっているため。

入力がこれらの条件に反する場合、条件を満たす木は構築不可能です。

構成方法を考える

サイズの小さいほうから考えていきましょう。根付き木として考えたとき、深いほうから順に構成していきます。

先ほど見たように、サイズ1は必ず作れます。では「サイズ2が作れる」と「サイズ2が作れない」は、どのように差を付ければ良いでしょうか。

f:id:betrue12:20180930123643p:plain

サイズ2を作りたい場合、サイズ2の部分木の上に親を作ればよいです。逆に作りたくない場合は、サイズ2の部分木で親となっている頂点に、さらに子を生やせばよいです。これを繰り返すことで目的の木を作ることができて、もう少し丁寧に書くと

構築している木がサイズで、次に番目の頂点を付ける時に、
- サイズ $i$ の連結成分を作りたい場合は、現在親となっている頂点のさらに親に $i+1$ 番目の頂点を置く。
- サイズ $i$ の連結成分を作りたくないときは、現在親となっている頂点の子として $i+1$ 番目の頂点を置く。

このように構成することができます。以下は「1, 3, 6, ...」が作れる木の例です。

f:id:betrue12:20180930124619p:plain

ACコード

（C++）Submission #3296518 - AtCoder Regular Contest 103

さいごに

Dの満点解法、2進数よりも45度回転の発想のほうが難しいかなと個人的には思いました。さっさと部分点だけ獲得したのは、結果的には正解でした。

木の問題はけっこう好きなので、Eは速く解けたかなと思います。Fも好きなタイプの問題だったので、本番で通せるようになりたい…

2018-09-24

Codeforces Round #512 参加記録＆解説（Div1 A, B）

Codeforces プログラミング競技プログラミング

Dashboard - Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1) - Codeforces

結果は355位で、レートが結構下がってしまいました…

f:id:betrue12:20180924113227p:plain

Div1のAとBを振り返ります。Div2ではDとEに対応しています。

A. Vasya and Triangle

Problem - A - Codeforces

問題概要

正整数 $n, m, k$ が与えられる。 $xy$ 平面上の $0 \le x \le n$ かつ $0 \le y \le m$ の領域内に格子点3つを取り、それらを結んだ三角形の面積が $\frac{nm}{k}$ となるようにせよ。またはそれが不可能であることを判定せよ。

制約

$1 \le n, m \le 10^{9}$
$2 \le k \le 10^{9}$

本番はかなり面倒な構成方法をした挙げ句にシステスで落ちましたが…簡単な構成方法があります。

格子点のみを頂点とする多角形の面積に関して、「ピックの定理」というものがあります。この定理から、このような多角形の面積は必ず $\frac{1}{2}$ の整数倍になります。

$\frac{nm}{k}$ が $\frac{1}{2}$ の整数倍でなければならないので、 $2nm$ が $k$ で割り切れない場合、答えは NO となります。以降、割り切れる場合を考えます。

仮に $(0, 0), (n, 0), (0, m)$ の3点をとった場合、その面積は $\frac{nm}{2}$ です。作りたい面積はその $\frac{2}{k}$ 倍です。先程「 $2nm$ が $k$ で割り切れる」という条件を調べたので、 $k$ の素因数は2を除いて $n, m$ どちらかの素因数になっています。このことから、以下のように考えることができます。

$k$ が2で割り切れる場合、まず $k$ を2で割って $k^{\prime} = \frac{k}{2}$ とする。その後 $k^{\prime}$ の素因数を、 $n$ または $m$ の割れる方から割っていく。
$k$ が2で割り切れない場合、先に $k^{\prime}$ の素因数を、 $n$ または $m$ の割れる方から割っていく。その後 $n, m$ のうち、素因数で1回以上割ったほうをどちらか選んで2倍する。（素因数で1回以上割ると値が $\frac{1}{2}$ 倍以下になるので、2倍することで $n, m$ が元の値よりも大きくなることはない）

このようにして小さくした $n, m$ で3点 $(0, 0), (n, 0), (0, m)$ を取り三角形を構成すると、作りたい面積が実現できます。

ACコード

（C++）Submission #43341268 - Codeforces

B. Vasya and Good Sequences

Problem - B - Codeforces

問題概要

長さ $n$ の数列 $a_{1}, ..., a_{n}$ が与えられる。この数列の連続部分列のうち、以下を満たすものの個数を求めよ。

「要素を1つ選び、その2進数表記におけるビット2箇所を選んで入れ替える」という操作を好きなだけ行うことで、数列全体のXORを0にできる。

制約

$1 \le n \le 3\times 10^{5}$
$1 \le a_{i} \le 10^{18}$

解法

これも本番はかなり面倒なしゃくとりを書いていて、何とか通ったからまだいいのですが、シンプルな解法で解説してみます。

「「要素を1つ選び、その2進数表記におけるビット2箇所を選んで入れ替える」という操作を好きなだけ行うことで、数列全体のXORを0にできる」まずはこの条件を言い換えてみます。1要素内で好きなだけビットを入れ換えられるので、ビットの位置は気にしなくて良いでしょう。区間内の各要素のビットの個数を考えたときに、以下の2つが満たされていればよいです。

ビットの個数の総和が偶数である。
1つの要素が、ビット総数の過半数を持っていない。

f:id:betrue12:20180924125238p:plain

「ビット総数が偶数となる区間」だけであれば累積和で簡単に求められますが、2番目の条件が厄介です。

ここで、1つの要素が持つビット数の範囲を考えます。 $1 \le a_{i} \le 10^{18}$ という制約から、まず下限は1個です。そして2進数で1を60個並べた数がおよそ $1.15 \times 10^{18}$ で制約を超えてしまうことから、上限は59個です。上限もさることながら下限が1というのも効いていて、例えばビット数59個の要素があっても、それ以外に要素が59個あれば絶対に過半数を占めることはありません。

このことから、過半数の条件を真面目に考えなければいけないのは長さ59以下の区間だけで、それ以上の区間は累積和を使えばよいことが分かります。これなら高速です。

解法をまとめると、

各要素のビット数を数える。
ビット数の累積和と、累積和の偶奇ごとの個数を数える。
左端を固定する。左端から長さ59以下の区間は、区間和と区間内の最大値を計算して真面目に条件判定する。
それ以降は累積和の差分を取って高速に計算する。

これで解けます。

※公式解説とほぼ同じですが、公式解説では累積和の条件だけで全区間を足してしまった後、過半数の条件に違反するものを引き算するという方法になっています。どちらでもよいです。

※実装上は、よほど制限時間が厳しくない限り59というギリギリを攻める必要はなくて、「60くらい」と考えて長さ65くらいまで真面目に条件判定する実装をしてもよいですし、そちらのほうが安全です。

ACコード

（C++）Codeforces

さいごに

どちらも、無駄に難しい解法に走って失敗してしまった回でした。そしてDiv1の人々はやっぱり強いです…Bを300人以上が通しているとは。厳しい戦場です。

2018-09-24

ABC110 参加記録＆解説

AtCoder プログラミング競技プログラミング

AtCoder Beginner Contest 110 - AtCoder

もはや参加記録というより解説メインになっているので、今回からタイトルに「解説」って付けます。

結果は20分台全完で11位。1桁順位の壁は厚い。

f:id:betrue12:20180924005239p:plain

A - Maximize the Formula

解法

作れる式の形は xy+z または x+yz しかなく、どちらも「10の位の数字が1つ、1の位の数字が2つ」という構成になっています。入力のうち一番大きいものを10の位に割り当てると最大になります。

ACコード

（Ruby）Submission #3249599 - AtCoder Beginner Contest 110

B - 1 Dimensional World's Tale

解法

「 $X$ と $x_{1}, ..., x_{N}$ 」が左に、「 $Y$ と $y_{1}, ..., y_{m}$ 」が右にキレイに分かれればよいです。 $X$ 側の最大値 $X_{\max}$ と $Y$ 側の最小値 $Y_{\min}$ を出して、 $X_{\max} \lt Y_{\min}$ であれば No War です。

ACコード

Submission #3250414 - AtCoder Beginner Contest 110

C - String Transformation

解法

「2つのアルファベットを選んで入れ替える」という操作を繰り返すと、どのようなことが起こるでしょうか。

「aをbに、bをaに置き換える」という操作を行うと、元文字列の a は b に、 b は a になる。
その状態からさらに「bをcに、cをbに置き換える」という操作を行うと、元文字列の a は c に、b は a に、c は b になる。

このように繰り返していくと、26文字のアルファベットが、それを1対1の対応で置換されたものに置き換わります。ここで言う「1対1対応」は数学用語には「全単射」というものですが、このレベルの問題であれば直観的な「1対1対応する」のイメージを持っていれば十分です。つまり、

同じ文字が異なる文字に変換されない。
異なる文字が同じ文字に変換されない。

の両方が満たされていれば Yes です。

実装においては、変換をmapなどで管理して $S, T$ の文字を順番に調べていき、同じ文字なのに前と違う変換先になっていれば1の理由で No 。最後に変換先の文字を全部調べて重複があれば2の理由で No とすればよいです。他に、 $S \to T$ と $T \to S$ の両方について1だけを調べる、という方法もあります。

ACコード

（Ruby）Submission #3252530 - AtCoder Beginner Contest 110

D - Factorization

Submission #3253308 - AtCoder Beginner Contest 110

解法

$a_{1} \times a_{2} \times \cdots \times a_{N} = M$ が成り立つということは、 $a_{1}, ..., a_{N}$ は $M$ の素因数を分配したものになっています。含まれる素因数が異なれば必ず値は異なるので（素因数分解の一意性、ですね）、この問題は「素因数の分配の仕方は何通りあるか？」と言い換えることができます。また素因数それぞれについての分け方は独立なので、全部の素因数について分配の仕方を考えて、それを全て掛け算すればよいです。

f:id:betrue12:20180924015211p:plain

ある素因数を $p$ とし、それが $M$ に $k$ 個含まれているとします。求めたいのは「 $a_{1}, ..., a_{N}$ に、 $k$ 個の区別されない要素を分配する方法は何通りあるか？」ですが、これは「重複組合せ」と呼ばれるもので、結果は $_{N-1+k}C_{k}$ になります（リンク先に、「なぜそうなるのか？」を丸と仕切りを用いて解説した記載もあるので見てみてください）。これを全て掛け算すると答えになります。

…とはいえ、この問題を解いて実装する上では

重複組合せについての公式を持っている（知識）
素因数分解できる（ライブラリ）
比較的大きな数において、 $_{N-1+k}C_{k} \mod (素数)$ 、またはこれを計算するのに必要な階乗と階乗逆元を前計算できる（ライブラリ）

これらの材料が必要になります。知識・ライブラリともに非常によく使うものなので、是非準備しておきましょう。

ACコード

（Ruby）Submission #3253308 - AtCoder Beginner Contest 110

さいごに

Cは考察ミスで「単射であればいいのかな？」と考えていたため、時間を余計に使ってしまいました…

Dはほぼ知識問題と言っていいと思いますが、かなり重要知識なので、本番解けなかった人も是非ライブラリ含めて身につけておくと良いと思います！

2018-09-23

Educational Codeforces Round 51 参加記録

Codeforces プログラミング競技プログラミング

結果は4完で450位。

f:id:betrue12:20180923154803p:plain

4問振り返ります。

A. Vasya And Password

Problem - A - Codeforces

問題概要

以下のクエリを $T$ 回処理せよ。

与えられる文字列 $s$ を最小文字数だけ書き換えて、数字、英小文字、英大文字の全てが含まれるようにせよ。

制約

$1 \le T \le 100$
全てのクエリについて、 $s$ は数字・英小文字・英大文字からなり、 $3 \le |s| \le 100$

解法

各文字種を含む・含まないの8通り（「全部含まない」はあり得ないので実際には7通り）で場合分けします。虚無。

ACコード

（C++）Submission #43120392 - Codeforces

B. Relatively Prime Pairs

問題概要

正整数 $l, r$ が与えられる。 $l \lt r$ であり、 $r-l$ は奇数である。

$r-l+1$ 個の整数 $(l, l+1, ..., r)$ を互いに素な2数のペアに分割せよ。（またはそれが不可能であることを判定せよ。）

制約

$1\le l \lt r \le 10^{18}$
$r-l+1 \le 3\times 10^{5}$
$r-l$ は奇数

解法

隣り合う2つの正整数は必ず互いに素である、という性質があります。正整数 $X$ が2以上の約数 $p$ を持っている時、 $X+1$ を $p$ で割った余りは必ず1になるので、2以上の共通約数を持たないことが証明できます。

そのため答えは常にYESで、隣り合う数を順番に出力していけばよいです。

ACコード

（C++）Submission #43121577 - Codeforces

C. Vasya and Multisets

Problem - C - Codeforces

問題概要

$n$ 個の整数 $s_{1}, ..., s_{n}$ が与えられる。これを、以下の性質を満たすように2つのグループに分ける分け方を1つ示すか、そのような分け方が存在しないことを判定せよ。

各グループは0個以上の要素を持ち、それぞれのグループの「グループに1つしか含まれていない整数の種類数」が等しい。

解法

最初に与えられる整数を、その個数に応じて分類します。

1個しかない整数：どちらのグループに入れても、必ず「1つしか含まれていない整数」となる。
2個ある整数：1+1で分けると、それぞれのグループで「1つしか含まれていない整数」となる。2+0で分けるとどちらも該当しない。
3個以上（ $k$ 個）ある整数： $1+(k-1)$ で分けると、1個のほうだけが「1つしか含まれていない整数」となる。それ以外の分け方では、どちらも該当しない。

それぞれの整数が各グループの「1つしか含まれていない整数の種類数」にどのように影響するかを考えると以下のようになります。

1個：1+0
2個：0+0 または 1+1
3個以上：0+0 または 1+0

これらの合計を2グループ間で揃えるにあたって、1個しかない整数はなるべく均等にしたいです。2個ある整数はどのように分けても差を作らないので関係ありません。3個以上ある整数は1種類追加するかどうかを選べるので、これを調整に使えます。

1個しかない整数を均等に分ける。
1個しかない整数の個数が奇数だった場合、偏りがあるので、3個以上ある整数をどれか1種類加える。（これができない場合はNO）
これらの整数がそれぞれのグループで「1つしか含まれていない整数」となるように要素を分ける。

これで解けます。

ACコード

Codeforces

D. Bicolorings

Problem - D - Codeforces

問題概要

2行 $n$ 列のグリッドを白か黒に塗り分ける。

同じ色のマスが縦か横に繋がっているとき、そのマス同士を連結であるとみなす。連結成分がちょうど $k$ 個であるような塗り方を数え上げ、998244353で割った余りを出力せよ。

制約

$1 \le n \le 1000$
$1 \le k \le 2n$

解法

DPをします。「左から $i$ 列目まで見て、その時点での連結成分が $j$ 個で、」までは良いですが、追加で何の情報を持たせると遷移がうまくいくでしょうか。

新しい列はどんどん右側に増えていきます。そして、右側に列を足した時に連結成分の数がどうなるかは、それに直接隣接する列の色によって決まります。一番右側の列の情報を持たせてあげればよさそうです。2マスの白/黒で4パターン持っても良いですが、対称性から「色が同じ」「色が違う」の2パターンだけでも十分です。

つまり、「左から $i$ 列目まで見て、その時点での連結成分が $j$ 個で、一番右の列の色が違う/同じである塗り方の総数」を持ってDPします。くっつくパターンは以下のように書き下せるので、それぞれの遷移を地道に書いていけばよいです。

f:id:betrue12:20180923190848p:plain

ACコード

Submission #43137036 - Codeforces

さいごに

この4問はほどほどの難易度でしたが…この次のEかFを本番中に解けないと、という感じですね。

2018-09-23

CODE FESTIVAL 2018 qual A 参加記録

AtCoder プログラミング競技プログラミング

本戦参加資格はありませんが、普通にunratedなコンテストとして参加。

結果は4完で68位。資格があれば本戦行けてそうな順位ですね…

f:id:betrue12:20180922234652p:plain

4問振り返ります。

A - 配点

解法

作れる合計点の最小値は $A+B+C$ 、最大値は $A+B+C+3$ で、その間の点は全部作れます。この範囲に $S$ が入っているか調べればよいです。

ACコード

（Ruby）Submission #3241130 - CODE FESTIVAL 2018 qual A

B - みかん

解法

制約が小さいので愚直にやれば十分通ります。「房の数は $A$ でなければいけない」フラグを各みかんごとに持って、条件ごとに $L_{i}$ から $R_{i}$ までのフラグを立てていけばよいです。最終的にフラグが立っているみかんは $A$ 、立っていないみかんは $B$ とすればOKです。

ACコード

（Ruby）Submission #3241826 - CODE FESTIVAL 2018 qual A

半分

C - 半分

解法

段階を踏んで、少しずつ考察していきましょう。

ウォームアップ

正整数を2で割ると、どんどん値は小さくなり、やがて0になります。0になった後はいくら2で割っても0のままです。例えば最初の整数が7の場合、7→3→1→0→0→0→... となります。

数え上げにおいては「数え上げる要素として区別されるかどうか？」がとても大事なので、その観点で言い換えると

0になるまでは、数値と2で割った回数が1対1対応し、区別される。
0になって以降は、何回割っても区別されない。

このように言えます。このことから、まずは問題文を次のように解釈できます。

「 $i$ 番目の要素に、合計 $K$ となるように正整数 $k_{i}^{\prime}$ を割り当てる。 $a_{i}$ を2で割って0になるまでの回数を $t_{i}$ として、 $k_{i} = \min(k_{i}^{\prime}, t_{i})$ とする。 $(k_{1}, ..., k_{N})$ の場合の数を求めよ。」

$k_{i}^{\prime}$ が $a_{i}$ を2で割った回数に対応し、 $k_{i}$ がそれに「0になって以降は何回割っても区別しない」ということを加味したものです。このように解釈することで、具体的な $a_{i}$ の値を考えなくてよくなります。

ここで $t_{i}$ の値を見積もっておきましょう。 $\frac{10^{18}}{2^{60}} = 0.86...$ であり、制約上最大の値である $10^{18}$ は2で60回割ると0になります。つまり、 $0 \le t_{i} \le 60$ です。これは後で使います。

場合分け

さて、このような場合の数をどうやって数えましょう。0になる、つまり $k_{i} = t_{i}$ となる要素が存在する場合がやっかいなので、まずそこで場合分けをしてみます。

0になる要素が存在しない場合、0を操作して「無駄に回数を重ねる」ことができないので、ぴったり 回の操作で到達可能な数列しか作れない。つまり、以下の条件を全て満たすの個数を数え上げる。
- 全ての $i$ について $k_{i} \lt t_{i}$
- $\sum k_{i} = K$
0になる要素が1つでも存在する場合、0を操作し続けることでいくらでも回数を水増しできるので、回以下の操作で到達可能な数列は全て作ることができる。つまり、以下の条件を全て満たすの個数を数え上げる。
- 全ての $i$ について $k_{i} \le t_{i}$
- 少なくとも1つの $i$ について $k_{i} = t_{i}$
- $\sum k_{i} \le K$

これらは排反（両方に含まれる数え上げ対象がない）なので、それぞれを数えて合計すればよいです。

このように場合分けをしてしまうと、実際に2で割った回数 $k_{i}^{\prime}$ を考慮しなくてよくなり、 $k_{i}$ を $k_{i} \le t_{i}$ の範囲だけで考えればよくなります。これがとても嬉しくて、 $T = \sum t_{i}$ とすると $\sum k_{i} \le T$ であり、先程見たように $t_{i} \le 60$ なので $T \le 50 \times 60 = 3000$ 、つまり合計が高々3000くらいになりました。 $O(T^{2})$ が間に合うのであれば、動的計画法で解けそうです。

動的計画法

ということでDPをします。「 $i$ 番目まで見て、それまでの $k_{i}$ の和が $j$ であるような場合の数」を $dp\lbrack i\rbrack\lbrack j\rbrack$ として考えるとシンプルに解けそうです…が、先程見たように「0になる要素が1つでも存在するか？」で場合の数たちを区別してあげる必要があります。そこで、「0になった要素が存在する/しない」という条件を追加します。

「0になった要素が存在しない」のほうを $dp\lbrack i\rbrack\lbrack j\rbrack\lbrack 0\rbrack$ 、「存在する」のほうを $dp\lbrack i\rbrack\lbrack j\rbrack\lbrack 1\rbrack$ とします。0になった要素が存在するとは、ある $i$ について $k_{i} = t_{i}$ であるということなので、遷移は以下のようになります。

f:id:betrue12:20180923104141p:plain

これは $O(T^{2})$ で最後まで回せます。最終的な答えは、「場合分け」のセクションで記載したそれぞれの数え上げ対象を足して、

$dp\lbrack N\rbrack\lbrack K\rbrack\lbrack 0\rbrack + \sum_{j \le K} dp\lbrack N\rbrack\lbrack j\rbrack\lbrack 1\rbrack$

となります。ただし $K$ が大きいときにはそのまま実装すると範囲外アクセスや大量のループが起こるので注意です。実際には $K \le T$ の範囲ならどれだけ $K$ がどれだけ大きくても関係ないので、 K = min(K, T) としてしまっても問題ないです。

ACコード

（C++）Submission #3243706 - CODE FESTIVAL 2018 qual A

※解説文のほうを公式解説に合わせたので、上のコードとはdpの0と1が逆です。

D - 通勤

解法

到達条件と給油条件

家、ガソリンスタンド、オフィスをまとめて「ポイント」と呼ぶことにします。家を0番目、オフィスを $N+1$ 番目のポイントとしておきます。

高橋くんがそれぞれのポイントにたどり着いた時の挙動として、以下の2つを考える必要があります。

ガソリン切れを起こさず、そのポイントに到達できるかどうか？
そのポイントがガソリンスタンドだった場合、そこで給油をするかどうか？

これらはガソリンの残量によって決まります。そのポイントに到達した時点でガソリンの残量が負であれば到達不可能ですし、0以上 $T$ 未満であれば給油をします。

ガソリンは毎回満タンまで給油するので、これらの条件は「最後にどのポイントでガソリンが満タンになったか？」だけから決まります。これをパラメータとしてDPしてみましょう。

動的計画法

$dp\lbrack k\rbrack\lbrack i\rbrack$ を「 $k$ 番目のポイントまで見たときに、 $k$ 番目のポイントまで到達可能であって、最後にガソリンが満タンになったポイントが $i$ 番目になるような場合の数」とします。

$k$ 番目のポイントに到達した時に、 $0, ..., k-1$ 番目のポイントのうち最後に満タンになったのがどこかによって、以下の3パターンになります。

遠すぎて、到達できない。
到達できて、ガソリンを給油する。
到達できるが、近すぎてガソリンをあまり消費していないため、ガソリンを給油しない。

この境目は $k$ 番目のポイントとの距離だけで決まり、見ていくポイントを右に進めると境界も単調に右に動いていくため、しゃくとり法が使えます。

f:id:betrue12:20180923103800p:plain

それぞれについて、 $k$ 番目のポイントをガソリンスタンドにしたとき、書店にしたときの遷移を考えます。

f:id:betrue12:20180923111853p:plain

最後の合計結果を見ると、 $k$ 番目のポイントを見た時のDPテーブルの値は、 $k-1$ 番目のポイントを見た時の値と比べて以下のようになっています。

「到達不可」に分類されるところは0。
（到達できて）「給油する」に分類されるところは据え置き。
（到達できて）「給油しない」に分類されるところは、2倍される。
新しい要素として $dp\lbrack k\rbrack\lbrack k\rbrack$ に、「給油する」に分類されるポイントについて $dp\lbrack k-1\rbrack\lbrack i\rbrack$ を合計したものを入れる。

これを2次元テーブルを全部埋める形でやっていくと時間がかかりすぎるので、高速化します。

DP高速化

まず、2次元のDPテーブルを作るのは無駄が多いです。状態は1手前の値のみに依存し、値が据え置きのところもあるので、これを1次元配列で管理して差分だけ更新していくことを考えます。すなわち、 $dp\lbrack i\rbrack$ を「いま見ているポイントまで到達可能であって、最後にガソリンが満タンになったポイントが $i$ 番目になるような場合の数」とします。説明上、「今見ているポイント」は引き続き $k$ と表記します。

「「到達不可」に分類されるところは0」は、しゃくとり法で境界を動かしていくたびに0を埋めていけばいいです。（実際には、これはやらなくてもいいですが、一応）

次に、新しい要素を入れるのに使う「「給油する」に分類されるポイントについて $dp\lbrack i\rbrack$ を合計したもの」です。これはDPテーブルの区間和になるので、逐次累積和を取っておいて差分を使ったり、しゃくとりで境界を動かすたびに差分更新をすればよいです。累積和のほうが個人的にはバグらせにくくてオススメです。

最後に残ったのが「「給油しない」に分類されるところを2倍」で、これはとても厄介です。ですが、以下のように考えることができます。

f:id:betrue12:20180923110650p:plain

「DPを1ステップずつ進める途中で区間内の値を全て2倍する」と考えるととても厄介です。ですが1つ1つの要素に注目すると、「値がセットされる→何回か2倍される→先の値を更新するのに使われる」という流れになっています。途中で更新するのが面倒なら、「何回2倍されるか」を予め求めておいて、最初から掛けておけば良いのです。

つまり、 $k$ 番目のポイントを考える時に $dp\lbrack k\rbrack$ にセットする値は、「それ以前の「給油する」に分類されるポイントについて $dp\lbrack i\rbrack$ を合計したもの」に「それ以降、ポイント $k$ で満タンにした車が給油されないポイントが $k+1, ..., N$ のうちいくつ存在するか」だけ2を掛けたものになります。

これを $N$ 番目のガソリンスタンドまで回し、オフィスに到達可能な範囲でDPテーブルの値を合計したものが答えです。

ACコード

（C++）Submission #3244630 - CODE FESTIVAL 2018 qual A

最後に

企業コンの配点は普段のARC等と単純比較できないこともありますが、まあまあARCの配点として考えても妥当だったのかな…？と個人的には思います。unratedとはいえ700が解けたのは良いですね。来週はARCです！

2018-09-17

Codeforces Round #510 参加記録

Codeforces プログラミング競技プログラミング

Dashboard - Codeforces Round #510 (Div. 2) - Codeforces

結果は4完…ですが、CとDが遅くて誤答ペナルティもかなり付いてるので順位は低めです（配点はA～Dで500-1000-1500-2000です）

f:id:betrue12:20180917214859p:plain

A～Dを振り返ります。

A. Benches

Problem - A - Codeforces

問題概要

$n$ 個の整数 $a_{1}, ..., a_{n}$ が与えられる。この数列に「いずれかの要素の値を1増やす」操作を $m$ 回行い、操作後の $a_{i}$ の最大値を $k$ とする。

$k$ の取りうる値の最小値と最大値を求めよ。

制約

$1 \le n \le 100$
$1 \le m \le 10000$
$1 \le a_{i} \le 100$

解法

最大値のほうが簡単です。操作前で最も大きな要素に $m$ を足すだけです。

最小値のほうは、なるべく平坦になるように要素を足していきたいです。ですが、元々の要素の最大値を下回ることはできません。 $\lceil\frac{\sum a_{i} + m}{n}\rceil$ と $\max a_{i}$ のうち大きい方が答えです。

ACコード

（C++）Submission #42974255 - Codeforces

B. Vitamins

問題概要

$n$ 個の要素について、そのコスト $c_{i}$ と、ABC をそれぞれ0個または1個含む文字列 $s_{i}$ が与えられる。

ABC 全ての文字を1つ以上含むように要素をいくつか選ぶ時、その合計コストの最小値を求めよ。

制約

$1 \le n \le 1000$
$1 \le c_{i} \le 100000$
$s_{i}$ は1～3文字であり、 ABC をそれぞれ0個または1個含む

解法

私は要素を順に見ていくDPをしました。dp[i][S] を、「 $i$ 番目の要素まで見て、既に取った文字の集合が $S$ であるときの最小コスト」とします。

$S$ は3つの要素を取った/取ってないの8通りであり、ABC それぞれをビットで管理すると0～7までの整数で表現できます。新しく要素を取った時の集合の遷移は、ビットのor演算を使って実装することができます。

他の方法もあります。高々8通りしかないパターンに1000個の要素があるため、無駄な要素が大量にあります。含む文字が同じ要素の中では、コストが最小のもの1つだけを考えれば十分です。そうすると高々8個の要素しか残らないので余裕で全探索できます。こっちのほうがスマートですね…

ACコード

（C++）Submission #42976889 - Codeforces

C. Array Product

Problem - C - Codeforces

問題概要

長さ $n$ の数列 $a_{1}, ..., a_{n}$ が与えられる。この数列に以下の操作を行う。

相異なるインデックス $i, j$ を選ぶ。 $a_{j}$ を $a_{i} \times a_{j}$ で置き換え、 $a_{i}$ を消去する。
この操作は1度だけ行える。インデックス $i$ を選び、 $a_{i}$ を消去する。

これらの操作を合計 $n-1$ 回行うと要素が1つだけ残る。この要素を最大化するような操作手順を1つ示せ。

制約

$2 \le n \le 2\times 10^{5}$
$-10^{9} \le a_{i} \le 10^{9}$

解法

問題文の操作は、結局「0個以上の要素を消去し、残りの要素を全て掛け合わせる」という操作になります。複数の要素を消去する場合は、1の操作で消去したい要素を全て掛け合わせてから、最後に2の操作で消せばよいからです。

ということで、上記の操作で最終的な要素を最も大きくするにはどうすればよいか考えます。

正の要素：残す。
負の要素：偶数個なら積が正になるので残す。奇数個の場合、絶対値が最も小さいものを1つ消し、他を残す。
0の要素：基本的には消す。

これが原則になりますが、このまま実装すると「全部0」や「負数1個＋残り全部0」の時に全部消す扱いになってしまうので注意です。これらの場合は単に全部の要素をかけ合わせれば良くて、最後に残る要素の最大値は0です。

ACコード

（C++）Submission #42994169 - Codeforces

本番コードがあまりにも汚かったので書き直しました…

D. Petya and Array

Problem - D - Codeforces

問題概要

長さ $n$ の数列 $a_{1}, ..., a_{n}$ が与えられる。その連続部分列のうち、和が $t$ より小さくなるものの個数を求めよ。

制約

$1 \le n \le 200000$
$|t| \le 2\times 10^{14}$
$|a_{i}| \le 10^{9}$

※絶対値表記になっている要素は、正・負・0の値を取り得る

解法

全要素が非負だとしゃくとり法が使えたりするのですが、負の要素がある場合はもう少し複雑な処理をしなくてはいけません。

まず、数列の区間和を累積和の差だと考えることがポイントです。 $n$ 個の要素について、最初の0を含めて順次累積和を取ります。これらの累積和は以下のような要素間の仕切りに対応し、 $(右の仕切りの値) - (左の仕切りの値) \lt t$ を満たす2つの仕切りの組が、そのまま条件を満たす区間に対応します。

f:id:betrue12:20180917212120p:plain

ということで、各仕切りについて「自分より左に存在する仕切りで、さきほどの条件を満たすものはいくつあるか？」という問題を考えます。仕切りを順番に見ていきながら数え上げることを考えると、

ある点に値を追加する
範囲内の値の総和を求める

を順不同で行えるようなデータ構造、BITを使えば解けそうです。

ただし、今回の問題では累積和として取り得る値が非常に大きくなる可能性があります。この方法では累積和の値をBITのインデックスとして使います。長大なBITを作れればよいのですが、メモリも計算時間も足りません。ということで、座標圧縮を行います。

座標圧縮を行うと、値の種類は高々仕切りの個数である $n+1$ 種類しかないので、（0始まりであれば） $0, ..., n$ の範囲に収まります。これならBITを作って、現実的なメモリや時間で計算できそうです。

圧縮を行ってしまうと、「 $(右の仕切りの値) - (左の仕切りの値) \lt t$ を満たす左の仕切りの値はどこまでか？」というのがすぐには分からなくなってしまいます。ですが、この条件を満たす/満たさないの境界は、圧縮前の座標を二分探索することで求めることができます。

f:id:betrue12:20180917214154p:plain

累積和が単調変化にならないようなケースで、区間和がある値以上/以下である区間の数え上げをBITで行う…というのはよく見る問題ですね。習得しておくとかなり役立つと思います。

ACコード

（C++）Submission #42991177 - Codeforces

さいごに

今回はC問題でハマって多くの時間を使ってしまいました…考察が十分に整理できないままコードを書き上げてWAやREを量産してしまったので、反省です。

2018-09-17

Codeforces Round #509 参加記録

Codeforces プログラミング競技プログラミング

Dashboard - Codeforces Round #509 (Div. 2) - Codeforces

いつもとは違い、（日本基準で）健康的な時間に開催されたこどふぉ。

結果はなんと全完！こどふぉでは全Division通して初めての全完です。TLEとかWAとかが怖い問題もいくつかあったので、運も良かったですね。

f:id:betrue12:20180917001948p:plain

大変ですが6問全部書きます。

A. Heist

Problem - A - Codeforces

問題概要

$n$ 個の整数 $a_{1}, ..., a_{n}$ が与えられる。これはある長さの連続した整数列から、いくつかの要素を抜き取って並び替えたものである。「抜き取った個数」の最小値を求めよ。

制約

$1 \le n \le 1000$
$1 \le a_{i} \le 10^{9}$ であり、これらは相異なる

解法

与えられた整数のうち、数字が飛んでいるところは必ず「抜き取られて」いるので、これらを数えます。具体的には $a_{i}$ の最大値-最小値+1から $n$ を引けばよいです。

ACコード

（C++）Submission #42919267 - Codeforces

B. Buying a TV Set

Problem - B - Codeforces

問題概要

整数 $a, b, x, y$ が与えられる。正整数の組 $(w, h)$ で、以下の満たすものの個数を求めよ。

$w \le a$
$h \le b$
$\frac{w}{h} = \frac{x}{y}$

制約

$1 \le a, b, x, y \le 10^{18}$

解法

まず、 $x, y$ をこの2数の最大公約数で割って、既約にしておきます。条件には $x, y$ の比しか出てこないので、この操作をすることは問題ありません。

$x, y$ を既約にすると、 $\frac{w}{h} = \frac{x}{y}$ を満たす正整数の組 $(w, h)$ は正整数 $k$ を用いて $(kx, ky)$ と表せます。

あとは上限を超えない $k$ の取り方を数えれば良いので、割り算すれば求められます。

ACコード

（C++）Submission #42922269 - Codeforces

C. Coffee Break

Problem - C - Codeforces

問題概要

$n$ 個の整数 $a_{1}, ..., a_{n}$ が与えられ、それらは $m$ 以下である。これらの整数を下記の条件を満たすようにグループ分けするとき、そのグループ数の最小値を求めて、最小になるグループ分けの方法を1つ構成せよ。

グループ内の任意の2つの要素 $b, c$ について、 $|b-c| \lt d$ が成立する。

※問題文の読解がとてもつらくて、上記の文章は簡素化しすぎて原型を留めていません…

制約

$1 \le n \le 2\times 10^{5}$
$n \le m \le 10^{9}$
$1 \le d \le m$
$1 \le a_{i} \le m$ でありこれらは相異なる

解法

要素をソートして、小さいものから順番にグループを割り当てていきます。

今まで作ったグループそれぞれについて、「そのグループで最後に追加した要素」を持っておきます。新しい要素を追加するとき、グループの最後の要素 $c$ との間に $a_{i}-c \lt d$ の関係が成立していれば、そのグループに要素を加えることができます。

新しい要素を順に見ていって、どこかのグループにその要素を追加できるのであれば、そのグループに要素を追加します。どこにも追加できない場合、仕方がないので新しいグループを作ります。こうするとグループ数をできるだけ小さくすることができます。

要素を追加できるグループが複数あるとき、どこのグループに要素を追加するかは関係ありません。新しく見る要素はどんどん大きくなっていくので、もう既に $a_{i}-c \lt d$ が成立している要素 $c$ たちは区別する必要がないからです。

なので、単に「最後に追加した要素が最も小さいグループ」をピックアップして、追加できるかどうか判定すればよいです。これは優先度付きキューなどに「最後に追加した要素の値とグループ番号のペア」を格納して小さい順に取り出していけば実装できます。

ACコード

（C++）Submission #42928504 - Codeforces

D. Glider

Problem - D - Codeforces

問題概要

※問題ページに図があり、そちらを見たほうが分かりやすいです。

$xy$ 平面をグライダーが飛行する。 $x$ 座標において $n$ 個の区間 $[x_{i1}, x_{i2}$ ] が存在し、それらの区間には上昇気流がある。これらの区間は交わらない。

初期位置の $y$ 座標を $h$ 、 $x$ 座標を好きに選んだ値として、グライダーを $x$ 軸の正の方向に飛ばす。グライダーは以下のように飛ぶ。

上昇気流の区間内にグライダーが存在するとき、 $y$ 座標は変化しない。
そうでないとき、 $x$ 座標が1増加するたびに $y$ 座標が1減少する。

グライダーの $y$ 座標が0になるまでの $x$ 座標の移動距離の最大値を求めよ。

制約

$1 \le n \le 2\times 10^{5}$
$1 \le h \le 10^{9}$
$1 \le x_{i1} \lt x_{i2} \le 10^{9}$ であり、これらの区間は交わらない。また、昇順に与えられる。

解法

まず、グライダーの開始地点は上昇気流の区間の開始位置にするのがよいです。途中から始めると、そのすぐ後ろにある上昇気流の区間が無駄になります。

ある上昇気流の開始位置から飛び始めたとき、どこまで飛べるかを求めたいです。このとき、開始位置以降に存在する「上昇気流がない区間」を、どこまで着地せずに通過できるか？と考えるとよいです。上昇気流がない区間を飛んだ長さと同じだけ高度が下がっていくので、上昇気流がない区間の長さの合計が $h$ 未満であれば、着地せずに飛ぶことができます。

つまりグライダーの飛び方は以下のようになります。

ある上昇気流区間の開始位置からスタートする。
上昇気流がない区間を、その長さの合計が $h$ 未満である限り通過する。
その次の上昇気流区間を通過する。
その次の上昇気流がない区間で、力尽きて着地する。

開始位置の上昇気流を左から右に全探索します。そうすると通過可能な「上昇気流がない区間」の右端も、左から右に移っていきます。このような性質が成り立つ場合は、しゃくとり法で効率的に計算することができます。

ACコード

（C++）Submission #42933175 - Codeforces

E. Tree Reconstruction

Problem - E - Codeforces

問題概要

以下の条件を満たす $n$ 頂点の木を構築するか、それが不可能であることを判定せよ。

$n-1$ 本の辺それぞれについて、整数 $a_{i}, b_{i}$ が与えられる。その辺で木を切断したとき、2つの部分木のうちで最大の頂点番号がそれぞれ $a_{i}, b_{i}$ となる。

制約

$2 \le n \le 1000$
$1 \le a_{i} \lt b_{i} \le n$

解法

まず、明らかに不可能になるケースがあり、それは $b_{i} \lt N$ となる辺が1つでも存在したときです。2つに分けた時、少なくとも片方には番号最大の頂点 $N$ が含まれているはずです。

そうでない場合、最大でない頂点番号 $v=1, ..., N-1$ について、 $a_{i} = v$ となる辺がいくつあるかを数えます。その数を元に、以下のように木を構築します。

$a_{i} = v$ である辺が1つであるとき、その頂点は頂点 $N$ に直接接続する。
$a_{i} = v$ である辺が $k$ 個（ $k \ge 2$ ）あるとき、頂点 $v$ と頂点 $N$ の間に、頂点番号が $v$ より小さい頂点を $k-1$ 個挟む。
$a_{i} = v$ である辺が1つもない頂点は↑で間に挟むために使う。

「間に挟む」というのは、具体的には以下のようにします。 $v$ より番号を小さい頂点を $k-1$ 個挟むと、その間の辺 $k$ 本全てについて、部分木が条件を満たします。 $v$ より番号が大きい頂点を挟んでしまうとNGです。

f:id:betrue12:20180917005940p:plain

この構成方法が不可能である場合は、多分どうやっても条件を満たす木が構築できないとは思うのですが…ちゃんと証明はしていません。この構成方法に限らず、より一般的な議論で「 $a_{i} = v$ であるような辺が複数あるとき、間に挟める頂点があるか？」という考察を軸にして証明するのかなあ、とは思います。

ACコード

（C++）Submission #42938536 - Codeforces

F. Ray in the tube

Problem - F - Codeforces

問題概要

※これも問題ページに図があるのでそれを見たほうが分かりやすいです。

横に伸びる管がある。管の伸びている方向を $x$ 座標軸とみなす。

管の下側と上側のいくつかの位置にセンサがある。これらは全て整数座標で表される。下側のセンサは $n$ 個で座標は $a_{1}, ..., a_{n}$ 、上側のセンサは $m$ 個で座標は $b_{1}, ..., b_{m}$ である。

管の下側と上側それぞれ整数座標点を1つ選び、下側の点から上側の点に向けてレーザーを撃つ。レーザーは管の中を反射して進み、いくつかのセンサに当たる。

レーザーが当たる座標点の最大数を求めよ。

制約

$1 \le n, m \le 10^{5}$
$0 \le a_{i}, b_{i} \le 10^{9}$

※実際には管の上側と下側の $y$ 座標が与えられているのですが、使わないので（！？）記載していません。

解法

これ、選ぶ座標点が有理数OKだとかなりキツくなりますが、整数座標限定なのでまだ解けます。

まず、レーザーを真上に撃つケースを考えます。この場合、上下で座標が同じ点にヒットし、延々とその間を反射し続けることになります。上下で座標が同じ点が存在すれば2、そうでない場合は1が最適です。

次に斜めに撃つケースを考えます。一番細かい間隔でレーザーを打てるのは、上下で座標が1ずれた点にレーザーを撃ったときです。

次に、座標が3ずれた点に撃ってみます。そうすると通る点は、1ずれたケースの下位互換になってしまいます。

f:id:betrue12:20180917012643p:plain

このように、他のケースの下位互換になるようなケースは考えなくて良いです。そうすると、3, 5, 7, ...は1の下位互換に、6, 10, 14, ...は2の下位互換に、といったようになり、結果的にずれ方が $2^{k}$ の場合だけを考えればよいことになります。ここまで絞れば、最大でも全部で $\log_2(10^{9})$ くらいのケースを試せばよいので効率的です。

ずれ方が決まれば、あとは各要素について余りを求めて、対応するものを足し合わせます。例えばずれ方が2の場合は、4で割った余りが上と下で2異なるものが対応します。割る数が大きい場合は余りが取りうる値が大きくなるのでmap等を使うことになります。

※ちょっと問題の記述が足りないかな？と思うところはあって、「真上に撃てるのか？」もそうですが、センサの座標が相異なるのかどうか（上下左右含めてまったく同じ位置にセンサがあるのかどうか）も明記されていないように思います。実際、 $a_{1} = 1, b_{1} = b_{2} = 1$ という入力が許されるなら解は3になるはずですが、Editorialのコードだとこれは2を返します。ちょっともやっとする問題でした。

ACコード

（C++）Submission #42946221 - Codeforces

さいごに

今回のレート上昇で薄橙になりました！

f:id:betrue12:20180917015037p:plain

一番上にちょっとだけ見えてる次の色が橙っぽいので、今の色は薄橙ですかね。皆さんはどう呼んでるんだろうか。

現行ルールだと、この色からDiv2単独開催もunratedになります。色落ちしない限りはDiv1で戦い続けることになるんですね…Div2単独も出ますけど。