2021-06-06

Ritsumeikan University Programming Contest 2013 (AOJ 2507) Computer Onesan

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

お題箱より。

Aizu Online Judge

解法

実は過去の解説記事に類題があります。

Educational Codeforces Round 17 D. Maximum path - ARMERIA

Codeforcesの問題は最大化でAOJの問題は数え上げという違いはありますが、解法はほぼ同じです。

左上から右下に向かう経路において、もし下から上に引き返せないというルールであれば、上から動的計画法で経路数を求めていくことができます。 $M=1$ の場合と $M=2$ の場合をそれぞれ考えます。

$M=1$ の場合

$M=1$ のとき縦の辺は2列あり、一度下から上に引き返してしまうとゴールすることができません。そのため引き返すことを考慮せずに動的計画法で答えを求めることができます。

あるいは縦の辺を1本通るたびに、どちらの列を通るかの2通りから選べるので、答えを $2^{N}$ と直接求めることもできます。

$M=2$ の場合

$M=2$ のとき縦の辺は3列あり、下から上に引き返す経路を考慮する必要があります。そのため下から引き返してきて、また下に進むコの字型の経路を予め作っておくことで動的計画法を用いることができます。

f:id:betrue12:20210606125911p:plain

コの字型の経路は高々1本で、スタートから伸びている列以外の2列がコの字になっている場合に限られます。このことから次のように動的計画法の状態を定義することができます。

$dp\lbrack i \rbrack\lbrack j \rbrack\lbrack k \rbrack =$ スタート地点から縦の辺 $i$ 本分だけ下に進んでいて、スタート地点から伸びている経路が $j$ 列目にあって、残りの2列がコの字型に伸びてきている（ $k=1$ ）/いない（ $k=0$ ）ような経路数

遷移パターンは先ほどの類題の記事と同じです（図の縦横を入れ替えて見てください）。

求めたい答えは、縦の辺 $N$ 本分だけ下に進み右下でゴールする経路数です。これは「一番右の列から、 $N+1$ 本目の縦の辺を通って出ていく」と考えると $dp\lbrack N+1 \rbrack\lbrack 2 \rbrack\lbrack 0 \rbrack$ と求めることができます。

ACコード

Aizu Online Judge

2021-04-25

yukicoder No.1460 Max of Min

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

お題箱より。

No.1460 Max of Min - yukicoder

解法

この問題の解法はいくつかのステップで構成されていて、その1つ1つが覚えておくと有用なテクニックだと思います。順に追っていきましょう。

ステップ1

求めたい値 $A_{N}$ は、与えられた数列の要素に対して $\max$ と $\min$ を取ることを大量に繰り返したものです。要素に対して四則演算などを行うことはありません。

このような問題では二分探索が有用であることがあります。つまりある整数 $x$ に対する「求めたい値は $x$ 以上か？」という判定問題を考え、これを様々な $x$ について繰り返し解くことで求めたい値を特定するという戦略です。

判定問題に落とすメリットは、与えられた要素や計算途中の要素を $x$ 以上かどうかで二値化して考えることができる点です。関数 $f$ を

$a$ が $x$ 以上ならば $f(a) = 1$ 、そうでなければ $f(a) = 0$

と定義します。このとき $\max$ と $\min$ について

$f(\max(a, b))$ は、 $f(a) = 1$ または $f(b) = 1$ のとき $1$ 、そうでないとき $0$
$f(\min(a, b))$ は、 $f(a) = 1$ かつ $f(b) = 1$ のとき $1$ 、そうでないとき $0$

が成立します。そして最終的に $f(A_{N}) = 1$ かどうかを判定すれば良いので、全ての要素を最初から最後まで二値化した状態で考えることができます。

これ以降、数列 $A, B$ の要素は二値化されたものとして扱います。

ステップ2

$A_{i}$ の値を順に決めていく処理について考察します。この処理を視覚的にとらえると次の図のようになります。数列 $B$ をずらして数列 $A$ に重ねていき、もし縦に $1$ が並んだところが存在すれば次の $A$ の要素は $1$ 、そうでなければ $0$ となります。

f:id:betrue12:20210424181547p:plain

ここで数列 $B$ 側の $1$ である要素に注目します。数列 $B$ の後ろから $t$ 番目の要素が $1$ であるとします（ $t$ は $1$ 始まりで数えます）。この $1$ は、

$A$ 側の $1$ である要素 $A_{i}$ と重なったときに、その $t$ 個先にある $A$ の要素 $A_{i+t}$ を $1$ にする能力がある

と考えることができます。

f:id:betrue12:20210424183333p:plain

判定したいのは $A_{N} = 1$ かどうかです。この考え方を用いると、判定問題を次のように書き表すことができます。

与えられた $0 \le i \lt K$ の範囲で $A_{i} = 1$ である要素からスタートして、 $B$ 側の $1$ と重なることで右側に進むことを繰り返し、ちょうど $A_{N}$ に到達できるか？

より正確に定式化するため、次のように集合 $S, T$ を定義します。

与えられた範囲の数列 $A$ について、 $A_{s} = 1$ である整数 $s$ からなる集合を $S$ とする。
与えられた数列 $B$ について、 $B_{K-t} = 1$ である整数 $t$ からなる集合を $T$ とする。

$A_{N} = 1$ かどうかの判定問題は、次のように定式化されます。

集合の要素を1つ選んで、変数の初期値とする。以下の操作を0回以上繰り返すことで、をと一致させることができるか？
- 集合 $T$ の要素を1つ選んで $t$ とする。このとき $x+t \ge K$ である必要がある。 $x$ に $t$ を加算する。

ここで「 $x+t \ge K$ である必要がある」という条件は、処理の過程で $A_{x}$ と $B_{K-t}$ が重なる機会があることに対応しています。

ステップ3

説明を簡単にするため、「 $x+t \ge K$ である必要がある」という条件をいったん無視します。

前ステップで定式化した問題は、個数制限なし部分和問題に初期値の条件が付いたものです。それぞれの値の大きさを確認すると、 $N$ は非常に大きく、 $S, T$ の要素は $K$ 以下なので $1000$ 以下と比較的小さいことが特徴です。

この部分和問題を $O(K^{2})$ で解く方法があります。キーなるアイデアは次の通りです。

大きい値を作る時でも小さい値を大量に足す必要がある。なので小さい値をどれか選んで $m$ として、まず $m$ で割った余りを $N$ と一致させてから、 $m$ を足し続ければ良い。

具体的に解法を説明します。 $T$ の要素のうち、どれでも良いので1つを選んで $m$ とします。 $0 \le r \lt m$ である整数 $r$ について、次の値を考えます。

$D(r) =$ 操作によって作ることができる $x$ の値であって、 $m$ で割った余りが $r$ であるものの最小値

$x$ を $N$ と一致させられる必要十分条件は $D(N \bmod m) \le N$ です。必要性は $D(r)$ の定義から直接分かり、十分性は $x = D(N \bmod m)$ としたあとに $m$ を加算し続けることで $N$ と一致させられることから分かります。

あとは $D(r)$ の求め方です。これを求めるために、次のグラフを構成します。

グラフはそれぞれの $r$ の値に対応する $m$ 個の頂点と、1個の始点を持つ。
始点から、 $S$ の要素を1つ選んで初期値とすることに対応する辺を作る。初期値とする値を $s$ とすると、これは終点が $s \bmod m$ でコストが $s$ の辺である。
始点以外の $m$ 個の頂点から、 $T$ の各要素を加算する操作に対応する辺を作る。辺の始点を $r$ 、加算する値を $t$ とすると、これは終点が $(r+t) \bmod m$ でコストが $t$ の辺である。

$m$ 個の頂点番号は $x$ を $m$ で割った余りに対応し、辺は $x$ に値を加算することに対応しています。そのため $D(r)$ はこのグラフにおける始点からの最短距離として計算することができます。グラフは密になる可能性がありますが、優先度付きキューを使わないダイクストラ法を用いることで $O(K^{2})$ で解けます。

※説明がしやすいので始点を明示的に置きましたが、置かずに $D(r)$ の初期値を $S$ から設定しても構いません。

最後に「 $x+t \ge K$ である必要がある」という条件を考慮します。これを扱うのは面倒なので、最初に $A_{2K-1}$ までの値を愚直に求めて、 $S$ の要素 $s$ を $K \le s \lt 2K$ の範囲で取ってしまうのが楽だと思います。最初から $x \ge K$ として扱うようにすれば条件を気にする必要はありません。ただしこの場合は、 $N$ が小さいときの実装に注意してください。

ACコード

#651415 (C++17(1z)) No.1460 Max of Min - yukicoder

2021-03-28

AtCoder Beginner Contest 195 F - Coprime Present

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

お題箱より。

F - Coprime Present

解法

互いに素であるという条件を扱うときには、素因数だけに注目することで考慮すべき対象の個数を減らせる場合があります。2つの正整数が互いに素であることと共通の素因数を持たないことは同値です。

集合 $S = \lbrace A, A+1, ..., B-1, B\rbrace$ とします。求めるべき答えは、 $S$ の部分集合のうち、どの相異なる2つの要素も共通の素因数を持たないものの個数です。そのため考えるべき素因数は、 $S$ の要素のうち2つ以上のものが持っている素因数だけで十分です。

$S$ の要素が連続する整数であり、その最大値と最小値の差が $72$ 以下と小さいことに注目します。 $73$ 以上の素数 $d$ について、 $S$ に $d$ の倍数が2つ以上含まれることはありません。相異なる $d$ の倍数を2つ取ったとき、その差の絶対値は $d$ 以上であるからです。

つまり考えるべき素因数は $72$ 以下の素数だけで十分であり、これは実際に数えると $20$ 個です。ここまで個数を絞れれば解法の見通しが立ちます。

ここからの考察の進め方ですが、まず動的計画法を考えてみるのが堅実で見通しが立ちやすいでしょう。要素を1つずつ見ていって、部分集合に追加する・追加しないの遷移をするDPを考えます。

要素を部分集合に追加して良いかを判定するために、追加前の部分集合の情報として何を覚えておけば良いかを考えます。これは「 $72$ 以下の素因数のうち、集合内の要素が既に持っているのはどれか」だけで十分なので、次のように状態を定義します。

集合の前から個の要素のうち個以上のものを含む部分集合であって、次の条件を満たすものの個数。
- どの相異なる2要素も共通の素因数を持たない。
- 含んでいる要素が持っている $72$ 以下の素因数からなる集合が $p$ である。

これは $p$ を $2^{20}$ 未満の非負整数として表現するビットDPとして実装できます。 $dp\lbrack i\rbrack\lbrack p\rbrack$ からの遷移は次の2通りになります。

次の要素を部分集合に追加しない：そのまま $dp\lbrack i+1\rbrack\lbrack p\rbrack$ に遷移する。
次の要素を部分集合に追加する：次の要素は $A+i$ であり、これが持っている $72$ 以下の素因数からなる集合を $p_{i}$ と表記する。 $p$ と $p_{i}$ が共通要素を持っていればこの遷移を無視し、持っていなければ $dp\lbrack i+1\rbrack\lbrack p\cup p_{i}\rbrack$ に遷移する。

ACコード

Submission #20980982 - Panasonic Programming Contest (AtCoder Beginner Contest 195)

考察の進め方について

この記事では考慮すべき素因数が少ないという点から考察を進めていきました。考慮すべき素因数が $20$ 個しかないと分かると、指数時間かかるアルゴリズムも視野に入るので考察の幅が広がります。

先にDPを考えるアプローチもできます。条件を満たす部分集合の個数を求める方法として、要素を1つずつ見ていって部分集合に追加する・追加しないの遷移をするDPは代表的でまず考えるべきものです。このDPで必要な情報を考えると、既に持っている素因数の集合が必要になり、その種類数を見積もろうという考察に進むことができます。

※「ビットDP」はDPで必要な情報を考えた結果出てくるものなので、最初からビットDPを思いつく必要はありません。考察のスタートはあくまで「要素を1つずつ見ていくDP」です

記事リクエストでもコンテスト後のTwitterでも、包除を考えて上手く行かなかったという声がありました。確かに、連続した整数・互いに素・数え上げという問題の断片的な特徴からは、通称「約数系包除」と呼ばれるアプローチを連想します。しかし実際に公式を適用してみると必要な値が求められずに行き詰まります。この問題のように部分集合の個数を数える問題では、約数系包除が上手くいきづらい印象です。

2021-03-20

AtCoder Heuristic Contest 001 参加記

AtCoder プログラミングマラソンコンテスト競技プログラミング

A - AtCoder Ad

得点率97.4％で130位でした。

f:id:betrue12:20210320121932p:plain

seed値0の入力に対する解のビジュアライザ出力です。

f:id:betrue12:20210320135516p:plain

考察

スコアの計算式を見ます。各企業が指定する1マス（以下、指定マスと呼びます）を含めないとその企業からの点は貰えないので、まずこれは含める必要があります。

企業ごとの得点は希望面積 $r_{i}$ と実際の面積 $s_{i}$ の単純な比ではなく、 $s_{i}$ が $r_{i}$ に近づくにつれて伸びが緩やかになります。例えば面積を希望の50％確保すると75％の点が貰えるので、面積が足りなくても全ての企業からまんべんなく点を得たほうが効率が良さそうです。

そして面積が $r_{i}$ を超えてしまうと今度は得点が下がるので、面積が $r_{i}$ を超えることにほとんどメリットはないことが分かります。

最初は希望を叶えるのが難しい企業、つまり希望面積が大きく指定マスが密集地帯にあるような企業は諦めたほうがトータルで良いスコアになるのではと思うこともありました。しかし順位表の上位陣の得点率がコンテスト初期から98％以上と非常に高く、1つの企業の得点が0％になるだけでこの得点率はほぼ絶望的なので、その可能性はないと判断しました。

方針

焼きなまし法です。初期解は指定マスだけからなる $1\times 1$ の正方形として、スコアは問題通りに計算しました。

近傍は3種類使い、それぞれ試す頻度を変えています。近傍1を1回実行する単位をイテレーション1回と呼ぶことにします。

近傍1

1つの企業ID $i$ と4方向のうちの1つをランダムに選び、長方形をその方向にマス1つ分伸ばします。盤外に出る、面積が $r_{i}$ を超える、他の長方形と被る場合はその近傍を諦めます。

面積を広げてスコアを高めるための基本となる近傍です。イテレーション1回につき1回近傍を取ります。

近傍2

1つの企業ID $i$ と4方向のうちの1つをランダムに選び、長方形をその方向にマス1つ分伸ばします。盤外に出る、面積が $r_{i}$ を超える場合はその近傍を諦めます。しかし他の長方形と被っている場合は、押し潰すようにそちらの長方形をマス1つ分縮めます。縮めることで指定マスが含まれなくなってしまう場合は諦めます。

スコアを悪化させる可能性がある近傍です。最初は近傍1に、20％の確率で長方形を縮める方向に近傍を取るという処理を入れていたのですが、縮めたマスを他の企業が使わないと結局スコアが増えないので、こちらの取り方に変更しました。

イテレーション10回につき1回近傍を取ります。

近傍3

1つの企業ID $i$ と、4方向の優先度を決める $\lbrace 上, 下, 左, 右\rbrace$ を並び替えた順列をランダムに選びます。その企業の長方形を指定マスのみの1マスに初期化し、優先度の高い方向から順番にその方向に伸ばせるだけ伸ばします。「伸ばせるだけ」とは、盤外に出ず、面積が $r_{i}$ を超えず、他の長方形と被らないように最大限伸ばすことを指します。

後半に動きづらくなった長方形を大きく動かす目的で導入しました。制限時間の半分が過ぎた以降、イテレーション1000回につき1回近傍を取ります。

高速化など

特にやっていません。スコア計算は近傍を取ったときに変更された企業のものだけを差分計算しました。他の長方形と被っているかの判定は自身以外の $n-1$ 個全てに対して愚直にやりました。

seed値0の入力（ $n=52$ ）に対して、コードテストでイテレーション5400万回くらい回っていました。

振り返り

最初に貪欲解法を考えてみたものの良いものが思い浮かばず、 $1\times 1$ を初期解としてただランダムに伸ばすだけの焼きなまし解法からスタートして、近傍の取り方を考えていきました。

上位陣との得点の離れを見て、焼きなまし以外の解法を色々と考えたものの、シンプルな焼きなましを超えることができませんでした。お約束としてビームサーチも考えてみたけど、遷移先の候補をどう取れば良いか全く分からず撃沈しました。

近傍の取り方のアイデア、逆に言うと改善できそうな悪い所を見つけるためにビジュアライザ出力は非常に有用です。しかし今回は画像を眺めても、ここをこうすれば良くなるというアイデアをあまり思いつけなかったのが厳しい点でした。「この長方形、縦じゃなくて横に伸ばしたほうが面積大きくなるのに」と思うことはあり、その結果として近傍3が追加されました。近傍3を入れたのは最終日で、それでスコアが少し伸びて今の順位に落ち着きました。

変化が大きすぎると思うくらいの近傍も含めたほうが良い、という経験則はありましたが、単純に伸び縮みの長さを増やしたり乱数で決めたりするだけでは逆にスコアが悪くなってしまいました。もっと近傍の取り方そのものを工夫して多様な変化を作るべきだったと思います。

とはいえ最終日の頑張りで得点率が96.2％から97.4％くらいまで上がり、最終順位が想定で100くらい上がっているので、この粘りは今後も大事にしていきたいですね。

f:id:betrue12:20210320164913p:plain

最終提出コード

Submission #20927098 - AtCoder Heuristic Contest 001

2021-02-21

AtCoder Regular Contest 047 C - N!÷K番目の単語

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

お題箱より。

C - N!÷K番目の単語

解法

※この解説の「何番目」という表記は全て1-indexedです。

一般に $n$ を $1$ 以上 $N!$ 以下の整数として、 $N!$ 個の順列のうち辞書順で $n$ 番目にあるものを、前の要素から順番に求めていく方法を考えます。

最初の要素は、 $N!$ 個の順列を辞書順に並べて $N$ 等分したグループに分けたときに、対象の順列が何番目のグループにあるかで決まります。
次の要素は、対象の順列が属していたグループをさらに $(N-1)$ 等分したグループに分けたときに、対象の順列が何番目のグループにあるかで決まります。
…

この手順を繰り返すことで対象の順列を求めることができます。 $i$ 段階目の手順で属しているグループが $g_{i}$ 番目だとすると、対象の順列の $i$ 番目の要素は、それまで使われていない正の整数のうち小さい方から $g_{i}$ 番目のものです。

f:id:betrue12:20210221130509p:plain

今回求めたいのは $\frac{N!}{K}$ 番目の順列です。各段階で何番目のグループに属するかを求めるには割り算の商、そのグループ内で何番目の順列であるかを求めるには割り算の余りとして計算できますが、桁数が非常に大きいので直接計算することは困難です。

ここからの考え方の概要をまず示します。先ほどの図で示した1つ1つの段階において、全体のサイズを $1$ とするような相対値として、対象の順列の位置を管理します。そして属しているグループが何番目かを求めて、そのグループのサイズがまた $1$ となるように「拡大」して、次に属しているグループが何番目かを求めて…ということを繰り返していきます。

具体的な手順を説明します。まず $N!$ 個の順列全体のサイズを $1$ と見なすと、最初の順列の位置は $\frac{1}{N!}$ 、最後の順列の位置は $\frac{N!}{N!}$ すなわち $1$ です。そして対象の順列の位置は $\frac{1}{K}$ だと見なすことができます。

全体を $N$ 等分してサイズ $\frac{1}{N}$ のグループ $N$ 個に分けたときに、対象の順列が何番目のグループに属するかを考えます。これは $\frac{1}{K}$ を $N$ 倍した値を整数に切り上げることで計算することができます。この値を $g_{1}$ とします。

次に、この $g_{1}$ 番目のグループのサイズが $1$ になるように拡大し、そのグループ内における対象の順列の位置を再計算します。これは $\frac{1}{K}$ を $N$ 倍したまま、 $(g_{1}-1)$ を引けば良いです。

この操作を繰り返していくことで、各段階で所属しているグループが何番目なのかを順に求めていくことができます。

$\frac{1}{K}$ を初期値とする対象の順列の位置は整数ではないですが、これを $K$ 倍した値は各段階において常に整数となります。 $K$ 倍した値を持っておくことで誤差なく計算することができます。

ここまでの処理で、各段階で所属しているグループが何番目なのかを求めることができました。これを $g_{1}, g_{2}, ..., g_{N}$ とします。ここから実際の順列を求めるためには次の手順を踏む必要があります。

まず、未使用の整数の集合 $S = \lbrace 1, 2, ..., N\rbrace$ を用意する。
次の処理をに対して順に行う。
- $S$ の中で小さい方から $g_{i}$ 番目の要素を求め、 $S$ から取り除く。それが対象の順列の $i$ 番目の要素である。

これはBITやセグメント木の上で二分探索を行うことで処理することができます。

ACコード

Submission #20364664 - AtCoder Regular Contest 047

2021-02-20

PAST公式テキストを書きました

プログラミング競技プログラミング書籍執筆

このたび、マイナビ出版から発行される「アルゴリズム実技検定公式テキスト（エントリー～中級編）」の執筆をさせていただきました。kenkooooさんとの共著です。

アルゴリズム実技検定公式テキスト[エントリー~中級編] (Compass Booksシリーズ)

作者:岩下真也,中村謙弘
発売日: 2021/02/27
メディア: 単行本（ソフトカバー）

アルゴリズム実技検定（通称PAST）のための学習参考書です。PASTに限らず、普段のコンテストのための学習教材としても使うことができます。

本記事では私個人の意見も交えつつ、執筆で重視したことや競技プログラミング（競プロ）を既にやっている人が気になっていそうな点などを書いていこうと思います。

本書の特徴

Amazonの商品ページなどにも本書の特徴が書かれていますが、特に次の2点が大きな長所だと考えています。

Pythonの文法解説から始まってエントリー→初級→中級と順番に解説していくので、プログラミング自体が初めてという人でも段階を踏んで学習できる
PASTとAtCoderの問題を合計で約50問解説し、その多くに図解が付いているので、実際の問題を用いて理解を深められる

競プロの学習に使える書籍は蟻本（通称）を筆頭にいくつか書かれていて、本書の執筆中にもけんちょん本（通称）という素晴らしい本が出版されました。それぞれの書籍では重視している内容や読者の想定レベルが少しずつ異なります。

本書はPAST公式テキストという位置付けなので、PASTの出題範囲や出題傾向に沿って構成を考えています。PASTで出題されにくい内容や、知らなくても問題が解けるような知識は思い切って省き、Pythonの文法解説や出題されやすいアルゴリズムの解説にページ数を使っています。そのため、

時間を掛けて手を動かせば、本書の内容だけでPAST中級が取得できる

とまで言える内容になっていると考えます。（もちろん複数の教材を併用したほうが学習効率が上がるのは言うまでもありませんが）

本書の掲載範囲

普段のコンテストでは出題範囲というものは存在しないも同然ですが、PASTには公式Webサイトに「出題範囲」という記載が存在します。本書の第4章がエントリー、第5章が初級、第6章が中級の出題範囲に対応しています。

本書は中級の出題範囲として記載されているアルゴリズムなどの解説に最も注力しています。Amazonの商品ページに掲載されているサンプルから第6章の目次を引用します。この第6章だけで約200ページ、本書の半分以上を占めています。

f:id:betrue12:20210220100933p:plain

この後に第7章が続きますが、新しい知識やアルゴリズムは登場しません。第6章で解説したアルゴリズムを複数組み合わせる問題や、遷移が少し複雑な動的計画法の問題などを扱います。

扱っている問題について

なるべくPASTの過去問を扱うようにしましたが、該当する問題がない場合はAtCoder Beginner Contest（ABC）や他のコンテストの問題も使っています。特に動的計画法の解説ではEducational DP Contestの問題がとても使いやすくて助かりました。

解説に適した問題がAtCoderにないアルゴリズムについては、アルゴリズムをそのまま適用する問題をいくつかAtCoder上に作成しました。発売までには公開される予定です。Aizu Online Judgeなどには既に適した問題が存在するのですが、書籍で扱う全ての問題をAtCoderでジャッジできるようにしたいという方針からこのような形になりました。

Pythonについて

言語がPythonであることは執筆のお話をいただいた時点で決まっていました。私個人としてもPythonを用いて良かったと考えています。Pythonの文法などを解説する第4章は私が担当しましたが、動かすために間接的に必要となるコードが少ないことは大きなメリットだと書きながら思いました。

私もkenkooooさんも競プロでPythonを使っているわけではないので、結果的に解答例は技巧的でなく平易な実装になったと思います。例えばリスト内包表記や引数の複雑なスライス記法は本編では用いていません。その代わり付録で、これらの応用的な記法や本編で扱っていないPythonの関数などを紹介しています。

PyPyについても少しだけ触れています。解説で扱う問題のいくつかは、素直な実装で通常のPython（CPython）で提出しても通らなかったので、PyPyで提出するように注意書きを付けています。

AtCoderの色について

本書を競プロの学習教材として使いたい人は、「この本の内容でAtCoderの何色まで到達できるのか」という疑問を持つと思います。

一概に言えるものではないので完全に私個人の意見ですが、およそ水色くらいだと思っています。中級レベルの後半で解説しているアルゴリズムを素直に適用できる問題が、最近のABCで出題されたとき、AtCoder ProblemsのDifficulty計算では水色に判定されることが多いからです。

しかし数学的知識を筆頭に、本書でカバーできない内容はABCのB～C問題でも出題されます。また最近は計算誤差の扱いをテーマとする問題がしばしば出題されています。これらは過去問で学習したり、コンテスト中に検索して知識を得ることに慣れたり（実はこっちのほうが重要かも）する必要があります。

アルゴリズムを素直に適用する問題は、知識が広く浸透していて検索にも引っかかりやすいため、コンテストでも正答率が高い傾向があります。そうすると同点の参加者が増え、正答時刻とペナルティの個数がパフォーマンス値に大きく影響します。

本書の内容を網羅して速度と正確さを常に発揮し続ければ青までは届くのではないかと思いますが、それよりは数学的知識やセグメント木などのデータ構造にも触れていったほうが青までの効率は良いと思います。

最後に

IT技術者のスキル評価において、アルゴリズムの知識とそれを実装に落とし込む能力が、これまで競プロのコミュニティで名前が挙がることが少なかった企業からも注目されてきています。そうすると必然的に、これらを学習する手段にも注目が集まります。

私が競プロを始めた3年前と比べると、学習教材は増えていますしこれからも増えていくでしょう。競プロから入った人もPASTから入った人も何を使えばいいのか迷うかもしれませんが、本書はそのどちらにもオススメできる内容となっています。色々見比べて、本書が合いそうだなと思ったら是非ご購入いただければと思います。

以上、真面目な（？）書籍紹介記事でした。私個人の体験談は発売後に別の記事で書くつもりなので、そちらもよろしければどうぞ。

2021-02-18

AtCoder Regular Contest 112 B - -- - B

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

B - -- - B

解法

ある整数 $x$ を作ることが可能か判定するときには、 $x$ を最小のコストで作る操作列だけを考えれば十分です。作りたい整数を最小のコストで作る操作列が、何らかの限定的な特徴を持つことを見つけられると非常に見通しが良くなります。

その特徴を探すために、逆に無駄な部分を持つ操作列としてどのようなものがあるかを考えます。ここで言う無駄な部分とは、操作列の一部であって、そこをある規則で変形することでより小さいコストで同じ整数を作れるものを指します。

まず、「 $-1$ 倍する」という操作を連続して2回行うことは無駄で、その2回の操作を除いても同じ整数が得られます。

また、その時点での整数が $0$ であるときに「 $-1$ 倍する」という操作を行うことも無駄で、その操作を除いても同じ整数が得られます。

さらに、次の図で表される操作も無駄です。

f:id:betrue12:20210218222152p:plain

これは「 $1$ を引く」→その時点での整数が $0$ でないときに「 $-1$ 倍する」→「 $1$ を引く」という一連の操作で、2回の「 $1$ を引く」という操作を除いても同じ整数が得られます。

作りたい整数を最小のコストで作る操作列は、これらの無駄な部分を持たないものに限られます。そのような操作列は必ず次の性質を満たします。

操作列の先頭と末尾以外に「 $-1$ 倍する」という操作が存在しない。

もしこの性質を満たさない場合、先に挙げたいずれかの無駄な部分が必ず1つ以上含まれることが場合分け等で証明できるからです。

このことから操作列としては「先頭で $-1$ 倍する/しない」「末尾で $-1$ 倍する/しない」の組み合わせ4通りだけを考えれば十分だということが分かります。

それぞれの場合について作ることが可能な整数を調べると、これは区間になります。例えば先頭で $-1$ 倍を行って末尾では行わない場合を考えます。その間に「 $1$ を引く」という操作は $0$ 回から $\lfloor\frac{C-1}{2}\rfloor$ 回までの好きな回数だけ行うことができるので、作ることが可能なのは閉区間 $\lbrack -B-\lfloor\frac{C-1}{2}\rfloor, -B\rbrack$ に含まれる全ての整数です。

同様の考え方で、4通りの場合について作ることが可能な整数の区間を求めると次のようになります。

$\lbrack B-\lfloor\frac{C}{2}\rfloor, B\rbrack$
$\lbrack B, B+\lfloor\frac{C-2}{2}\rfloor\rbrack$
$\lbrack -B-\lfloor\frac{C-1}{2}\rfloor, -B\rbrack$
$\lbrack -B, -B+\lfloor\frac{C-1}{2}\rfloor\rbrack$

これらの和集合に含まれる整数の個数が答えになります。一般に複数の区間の和集合のサイズを求めるためには、順序付き集合で区間を管理するライブラリや、座標圧縮＋imos法などを用いることができます。または4つの区間を $B$ 周辺と $-B$ 周辺でそれぞれマージすると2つの区間になるので、それぞれの長さと重なりを考えることで直接計算することもできます。

ACコード

考察過程に忠実なバージョン（座標圧縮＋imos法）：Submission #20215733 - AtCoder Regular Contest 112
計算式で直接出すバージョン（2つの区間として計算）：Submission #20219040 - AtCoder Regular Contest 112