車校でABC/ARCに出ていない間に灰色が10個くらい増えていたので、灰色全完奪還ついでに一番気に入った問題の解説です。とはいえARC灰ですが。

問題概要

制約を満たすカードへの数字の書き込み方を数え上げてmodを取るだけです。

とはいえその制約が結構ややこしいので、整理していきましょう。

考え方

全ての数字についてただ一つの制約があります。その内容は「左から、あるいは右から数えて $k_i$ 番目にはじめて $i$ が書かれたカードが出現する」というものです。

制約が無い状態での書き込み方は $k^n$ 通りです。というのは、$1 \leq i \leq n$ な $i$ について $i$ 番目のカードには $1$ ～ $k$ のいずれかの整数が書ける、という意味です。この上から前述の制約を載せましょう。すなわち、

左または右から $k_i$ 番目のカードに書かれた数字が$i$である
左または右から $k_i$ 番目よりも更に左または右には、$i$ が書かれたカードはない

という条件を追加で満たせば、題意を満たす書き込み方の数え上げが出来ます。

この条件を満たすには、

左または右から $k_i$ 番目のカードに書き込める数字は $i$ のみ、$1$ 種類
左または右から $k_i$ 番目よりも更に左または右には $i$ を書き込めないので、それらのカードに書き込める数字の種類が $1$ 減る

というように、各カードに書き込める数字の種類数を配列で持って減らすなどすればよいです。

ただし、例えば

L 5 L 7

という制約を処理しようとするときには注意が必要です。なぜなら、最初の制約で $5$ 番目のカードに書き込める数字が $1$ 種類になったあと、何も考えずに次の制約で $1$ ～ $6$ 番目のカードに書き込める数字を $1$ 減らすと、 $5$ 番目のカードには数字が書けるのに、配列の中身は $0$ になってしまいます。これを避けるには配列の既に $1$ である要素を無視して処理するなどの方法が考えられます。

この処理をした配列の要素全てを掛け算した結果を出力して終了です。

ACコード

白羽です。

初の記事です。よろしくお願いします。

ABC209に参戦したので、その感想や解説を書きます。

問題一覧

A - Counting
B - Can you buy them all?
C - Not Equal
D - Collision

注意：以下の解説はここにはありません。逆に教えてください。

E - Shirotori
F - Deforestation

A - Counting

初手、やたらとめんどくさい問題でした。
$a>b$なら必ず0、と条件分岐してやるのが正解なのですが、面倒なので数え上げ。
検証すべき数字は$0 < i \leq 100$くらいで良いでしょう。

https://atcoder.jp/contests/abc209/submissions/24102842

B - Can you buy them all?

偶数なら1円を引くという条件ですが、色々な引き方が考えられます。

$n / 2$を引く -> これを思いついた貴方はスマート。
偶数番目は実際に1を引いてから配列に入れる -> 問題文に忠実。だけどforループのカウンタは偶奇逆転するので注意。
https://atcoder.jp/contests/abc209/tasks/abc209_b 実装速度のことしか考えてない。脳死でも速ければいいと思ってる。

C - Not Equal

$10^9+7$という数字にぎょっとしましたが、普通に簡単でした。
数列Aを実際に構成するときのことを考えます。

たとえば、$C_1$が5だとします。このとき、$A_1$では1～5のうちのいずれかの数を使います。そして、その数は$A_2…A_n$には使用できなくなります。

よって、たとえば$C_2 = 7$だとすれば、$A_2$には1～7のうち、$A_1$でない、いずれかの数を使うことになります。

これをもって、$C_i$が何であれ、$A_i$について使用できる数は$C_i - (i - 1)$個になる、と言いたくなります。

ですが、以下のような反例があります。たとえば、$C = \{7, 6, 5\}$とします。すると、$A_1 = 7$ならば、$A_2$は$1 \leq A_2 \leq C_2$で制限されません。これはめんどくさいです。

そこで、今回は$A$の各要素同士が大小関係ではなく、ただの等しくないという関係であることに着目しましょう。大小関係は順序が入れ替われば台無しになりますが、等しくないものは順序が入れ替わろうが等しくないままです。なので、最初に$C$を昇順にソートしてしまえば、$1 \leq i < j \leq n$な$i, j$について、$C_i > C_j$な場合を考える必要はなくなります。

https://atcoder.jp/contests/abc209/submissions/24113926

D - Collision

この一カ月、グラフ問題から逃げなかった成果がようやく出せた。そんな問題でした。

問題文には明記されていませんが、

頂点が$N$個で辺が$N - 1$個
グラフが連結

この時点でこのグラフはどう考えても木にしかなり得ません。木グラフになるために無駄な辺のひとつでもあろうものなら、片方の条件は満たせなくなります。

そして、このグラフが木であることに気づけば、木であるグラフの性質を乱用できます。

その中でも今回使うのは、木グラフの互いに異なる2頂点間の最短経路は一つに定まる、というものです。というか、そのような経路は一つしかありません。これについては問題文からうすうす察せられるかもしれません(2頂点間の経路が複数あると、高橋君と青木君が遭遇しない可能性が生じます)。

まず、出力がRoadかTownですが、これは単純な話で、クエリの頂点$c, d$間の最短距離が、奇数か偶数かだけを考えればよいです。前者がRoadで後者がTownです。

ここで、今回与えられる入力については、どのような場合もグラフは頂点1を有します。そこで、グラフの頂点1をつまんで、上に持ち上げたような形にして考えましょう。これも木の性質ですが、どの頂点を根にしても木グラフは木グラフのままです。

すると、クエリ入力で与えられる$c, d$それぞれ頂点1からの距離はわかります。これは、最初に頂点1から全頂点へとBFSやDFSをすればよいです。そして、$c → 1 → d$と移動する経路の長さは、頂点1からcへの距離と、頂点1からdへの距離の和になります。

ここで、考察を簡単にするために、以下のような場合を考えます。

f:id:Shiroha_14:20210710220801p:plain

ここで、頂点2から8への経路を考えているものとします。(字も図も下手でごめんなさい)

すると、頂点1を通る経路は2-3-4-5-1-5-6-7-8です。この5-1-5さえ圧縮できれば……となりますが、ここでRoadかTownかという条件が、経路の長さの偶奇だけで決められたことを踏まえると、この圧縮は経路の偶奇に影響しません。

となれば、$c → 1$の距離と$1 → d$の距離を合算して偶奇を判定するだけになります。ちなみに前者の$c → 1$についてですが、このグラフは問題文に書いてある通り、双方向、すなわち無向グラフなので$1 → c$と等しいです。

また、$c → 1$に$1 → d$が内包される(あるいは逆)ような場合でも、精査すれば上のような考察は成り立ちます。

https://atcoder.jp/contests/abc209/submissions/24122956

感想

まさかの好相性な問題を引き当てた結果、17分半で4完ノーペナ、まさかの暫定600位台に入りました。

ほぼまぐれみたいなものです。この順位を平常運転にしていきたい……！

白羽Diary

白羽の雑記です。

ARC124 A - LR Constraints