2024-02-08

競プロ典型 90 問 002 valid parens の列挙

競プロ典型 90 問 002 の解説のうち、 ngtkana さんのもので紹介されている方法がうまくいく理由を次のように考えた。

以下のことを確かめる。

操作後の列は正しいカッコ列である
辞書順で操作前と操作後の間に正しいカッコ列は無い

お断り

"("と")"からなる列 $p$ が正しいカッコ列であることと次のことは同値:

$s_p = 0$ とする。列 $p$ の左から1文字ずつ読み取り、"("ならば+1、")"ならば-1を $s_p$ に足す。以下の両方が成り立つ。

最後の文字を読み終えた時点で $s_p = 0$
最後の文字を読み終えるまで常に $s_p \geq 0$

上に出てきた $s_p$ をスコアと呼んだり、 $p$ の $i$ 文字目を読み終えた時点の $s_p$ の値を指して $s(i)$ と書いたりさせてもらう。また、列 $p$ が明らかな場面では下付き文字を省略して単に $s$ と書かせてもらう

1.を確かめる

操作の前後で"("と")"の個数は変わらないから、操作前が正しいカッコ列ならば操作後の列も先述の(a)を満たす。

以下、操作後の列が先述の(b)も満たすことを確かめる。

操作前の列 $p$ で最も右にある"())"の"("の位置を左から $i$ 文字目と呼ぶことにする。

操作後の列 $p'$ を左から $i-1$ 文字目まで、 $i$ 文字目、 $i+1$ 文字目から終わりまでの三つの部分に分けてスコアが0以上となっていることを確認する。

一つ目の部分

操作前後で左から $i-1$ 文字目までは等しいから操作後の列の左から $i-1$ 文字目まではスコアが0以上である。

二つ目の部分

操作前の列は先述の(b)を満たすことと、 $i, i+1, i+2$ 文字目が"())"という並びであることから $s_p(i-1) \geq 1$ である。

操作後の列の $i$ 文字目は")"になっているが、 $s_{p'}(i) = s_p(i-1) - 1\geq 0$ が成り立つ。

三つ目の部分

操作後の列の $i+1$ から終わりまでは"("を左、")"を右に寄せた形である。

"("が連続する間は明らかにスコアが0以上である。

")"が連続する間にスコアが0より小さくなると仮定する。

このとき、 $p'$ の $i+1$ 文字目から終わりまでの形からして $s_{p'} < 0$ となる。

一方、操作の前後で"("と")"の個数は変わらないから $s_{p} = s_{p'} = 0$ となるべきで、矛盾がある。

背理法から")"が連続する間にスコアが0より小さくなることはない

2.を確かめる

操作後の列が、 $i$ 文字目が")"な列の中では、辞書順で最も早いことは $i+1$ 文字目から終わりまでの形から明らかであり、正しいカッコ列でもある。

後は次のすべてを満たす列がないことがわかればよい:

$p$ より遅い
$i+2$ 文字目まで $p$ と等しい
正しいカッコ列

(i)と(ii)の二つを満たす列 $q$ は(iii)を満たさないことを確認する。

(i)をまじめに言い直すと、 $i+2 < j$ で $p_k = q_k$ $(k < j)$ , $p_j = ($ , $q_j = )$ を満たすものが存在する。ここで $p_j$ などは列の $j$ 文字目を表す。

(ii)より $s_q(j-1) = s_p(j-1)$

ところで $p$ について最も右の"())"より右にある"("ではスコアが1になる。まじめに書くと次が成り立つ:

$p_k = ($ かつ $i < k$ ならば $s_p(k) = 1$

なぜならば $s_p(k) > 1$ とすると、最後の文字を読み終えた時点でスコアが0になるには $k$ 文字目より右で")"が2個以上連続しなければならない。

$k$ 文字目より右で")"が2個以上連続すると、 $i, i+1, i+2$ 文字目の"())"より右にさらに"())"があることとなり、矛盾する。

背理法から $s_p(k) = 1$

"("を読んでスコアが1になるなら、その一文字前ではスコアは0である。

以上をまとめると $s_q(j-1) = s_p(j-1) = 0$ となり、 $q$ を左から読むと $j$ 文字目でスコアは負となるから $q$ は正しいカッコ列でない

2024-01-21

ABC333 D 解説にある実装例

ABC333 Dの実装例にあった次の行がわからなかったので調べた

ranges::max(forest.groups() | views::transform((auto &&g) { return size(g); }))

質問

| って何
views::transform って何
() {} って何

回答

パイプ
range と関数を引数にとり、range の各要素に関数を適用して view を返す関数
ラムダ式

次の質問

view::transform が関数だとして、問題の行は関数しか引数にとってない(range をとってない)じゃないか
range, view って何

回答

第1引数にviewable_rangeを受け取ってviewを返すカスタマイゼーションポイントオブジェクトを、Rangeアダプタオブジェクトという。(中略)

Rangeアダプタオブジェクトadaptorが2つ以上の引数をとる場合、以下の3つの式は等しい。
```
adaptor(range, args...)
adaptor(args...)(range)
range | adaptor(args...)
```
[2]
これの3つ目の式が使われている(パイプライン記法というらしい?)
どちらもライブラリ<range>が定義するコンセプト
- vector<vector<int>> は range らしい( forest.groups() は vector<vector<int>> であり[1]、 view::transform の第一引数になっているから)
- view は range らしい(range::max の引数になっているから)
- そういう見方をしないで view や range の定義を確認してください←はい...

他の質問

auto &&g って何

回答

※ auto&& の && は reference collapsing が働くことを意味しているものです

[3]

Reference collapsing と関連する語をひとまず次のように思うことにしました

思ってるだけなので間違えてたらごめんなさいアンド教えてください

Reference collapsing

今回はラムダ式の引数に &&g と書いてあり、引数として rvalue 参照が与えられたときだけ g は rvalue 参照、それ以外(lvalue, rvalue, lvalue 参照, あと何)が与えられたときは g は lvalue 参照になる

もし、今回 &&g と書いてあるところを &g にすれば、引数として何が与えられようと g は lvalue 参照になる

というように参照の参照ができたときにそれが lvalue 参照と rvalue 参照のどっちになるかを決めたルール

lvalue, rvalue

lvalue は名前のついてるオブジェクト(オブジェクトって何)、rvalue は一時オブジェクト

lvalue 参照, rvalue 参照

lvalue 参照は普通(?!)の参照。rvalue 参照は参照してる先を壊していい参照(ある状況で無駄なコピーを避けるのに有用らしい)

&g か &&g か

全部 &&g で生きていく

自分でも何が言いたいかわかっていないスピリチュアルコーナー

これまで範囲 for 文を、何も考えず cpprefjp から丸パクリしてから const auto &e を auto &e にして生きてきた

C++11の範囲for文を使うと以下のように書ける：
std::vector<int> v;

for (const auto& e : v) {
  std::cout << e << std::endl;
}
変数宣言には直接コンテナ内の要素の型（上記の例であればconst int& eなど）を書いても良いし、型推論autoを使うと、さらに簡潔に書ける。

変数宣言にconst参照const auto& eを書くとコンテナ内の要素の変更を禁止し、要素のコピーも行わない。参照auto& eを書くと、コンテナ内の要素を変更できる。実体auto eを書くと各要素がコピーコンストラクタによってコピーされてからfor文に渡される。

変数宣言 e を変更可能か？コンテナ内の要素を変更可能か？

const auto& e No No

auto& e Yes Yes

auto e Yes No

変数宣言	e を変更可能か？	コンテナ内の要素を変更可能か？
const auto& e	No	No
auto& e	Yes	Yes
auto e	Yes	No

[4]

Reference collapsing を知ったいま、 &e と書いたら e は常に lvalue 参照となることが分かった。&&e と書いても rvalue 参照が与えられない限り e が rvalue 参照になることがないことも分かった。具体的にどんな状況か今の自分には想像できないが、絶対 lvalue 参照にしたいというときに &e を使うんでしょうか。範囲 for 文をするときは範囲をぶっ壊されたらいやだから何かの間違いで rvalue 参照になったらだめそう(だからauto &e と書くんでしょうか)。auto &&e: (ここに範囲に相当するオブジェクトを返す関数呼び出しを書く) とかやったら rvalue 参照になっちゃうんでしょうか。もうわからない

この記事は、自分が件の実装例にある一行を見たときにどのように調べたらよいかすらわからなかったので、関係ある語を列挙しただけのものです。ラムダ式やら view やら lvalue 参照やらについて厳密にご紹介しようという志はありません。

??? 「クネクネとC++について調べる時間で問題解いた方がレート上がりそう(おれのレートがクネクネとC++について調べるまでもない程度に低そうなため)」

参考

[1] AtCoder の記事"AtCoder Library (ACL)"から"document_ja/dsu.md"

[2] cpprefjp - C++日本語リファレンスの"リファレンス/<ranges>", [4] cpprefjp の "言語機能/C++11/範囲for文

[3] プログラミングの教科書を置いておくところの"C++ 11 auto の使い方"、その他の関連する記事

2023-10-29

ARC154 A Swap Digit 解説

解説が間違っているのではないかと思い、この記事を書くことにした。

問題文はこちら。

https://atcoder.jp/contests/arc154/tasks/arc154_a

ここで、 $a_ib_j + a_jb_i$ と $a_ib_i + a_jb_j$ のどちらが小さいかを考えます。これは、 $a_i,a_j$ の大小関係と $b_i,b_j$ の大小関係が一致しているのであれば前者、そうでないならば後者となります。

$�_{�}, �_{�大小関係が一致しているのであれば前者、そうでないならば後者となります。tete}$

解説に書かれているこの文自体は正しい。しかし $A\times B$ を小さくするために、ある桁で交換するかしないか決めたいならば $a_ib_j + a_jb_i$ (交換前)と $a_ia_j + b_ib_j$ ( $i,\space j$ どちらか一方の桁を交換後)のどちらが小さいかを考えることになるのではないか。これらの大小関係を調べる。

$(a_ib_j + a_jb_i) - (a_ia_j + b_ib_j) = a_i(b_j - a_j) + b_i(a_j - b_j) = (b_j - a_j)(a_i - b_i)$

以上より $b_j, \space a_j$ ペアと $b_i,\space a_i$ ペアの大小関係が一致しているとき $a_ib_j + a_jb_i$ 、そうでないとき $a_ia_j + b_ib_j$ の方が小さい(つまり $b_j, \space a_j$ ペアと $b_i,\space a_i$ ペアの大小関係が一致しているならば交換しない方がよい)。こうなると次が納得できる。

よって、 $�_{�}, �_{�}$ $a_i,\space b_i$ のうち小さい方を $a_i$ にし、大きい方を $b_i$ にすることによって $A\times B$ を最小化できます。

(小さい方を $b_i$ にし、大きい方を $a_i$ にすることによっても $A\times B$ を最小化できるはず)

また、解説放送その他で紹介されている以下のやり方の方が手っ取り早い気はする:ある桁を交換しても $A+B$ は保たれるから $A+B=C$ とする( $C$ は定数)。このとき

$A\times B = A(C-A) = -A^2+CA = -(A-\frac{C}{2})^2+\frac{C^2}{4}$ ということで、 $A$ は $C/2$ (すなわち $A,\space B$ の平均)より離れているほど $A\times B$ は小さくなる(このことから逆に積を大きくしたいなら $A,\space B$ が同じ大きさになるように寄せるとよいことがわかる)。

これを書いた動機

解説が理解できなくて数日間悩んでから、解説のある個所を変更することで納得のいく文章になったので、その箇所は書き間違いではないかと思った。適当にインターネットで検索した限りだと解説に言及している人や上で書いたようなことを言っている人が見つからなかった。友人(1人)に、具体的な個所は伏せて、間違いがあると思っているが君はどう思うかと伝えたうえで見てもらったところ彼も自分と同じ考えに至った。それで自分だけの勘違いでもなさそうだと思いここに書くことにした。もともと解説が正しく自分が理解できていない、すでに指摘している人がいる、上で自分が書いてることに間違いがあるなど、なんでもあれば知らせていただきたい。

おれってどうしたらいいですか

おれってどうしたらいいですか←以前にTwitterで見かけた文言を気に入って盗用しています