# 競プロ講習会第18回 Web資料
## ◎第18回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #18 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Virtual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/551a727747f9fa37509928277625805485f8eadd
#### ◎公式解説
##### A〜H問題
https://codeforces.com/blog/entry/55233
## ◎問題訳(意訳あり注意,F問題まで)
### ◎A. Trip For Meal
:::spoiler **クリックで展開**
TL: 1s ML: 512MB
#### ●問題
くまのプーさんははちみつが大好き！
そこで彼は友達を訪ねることにしました。彼には3人の親友、ラビット・オウル・イーオーが居て、それぞれ別の家に住んでいます。
ラビットとオウルの家の間の距離は $a$ メートル、ラビットとイーオーの家の間の距離は $b$ メートル、オウルとイーオーの家の間の距離は $c$ メートルです。
プーさんは1日に $n$ 回食事をします。今彼は、ラビットの家にいて、今日初めての食事の真っ最中です。友達がもう蜂蜜をくれなくなったら、プーさんは家を出て、別の友達の家に蜂蜜を貰いに向かいます。訪問する度に、友達は何度でも蜂蜜を出してくれると仮定します。
この場合、 $n$ 回食事をするまでに必要な移動距離の総和の最小値を求めてください。
#### ●入力
1行目に、食事の回数を表す整数 $n(1 \le n \le 100)$ が与えられる。
2行目に、ラビットとオウルの家の間の距離を表す整数 $a(1 \le a \le 100)$ が与えられる。
3行目に、ラビットとイーオーの家の間の距離を表す整数 $b(1 \le b \le 100)$ が与えられる。
4行目に、オウルとイーオーの家の間の距離を表す整数 $c(1 \le c \le 100)$ が与えられる。
#### ●出力
$n$ 回の食事を行うために必要な最短移動距離をメートル単位で出力してください。
#### ●入出力例
##### 入力例1
```
3
2
3
1
```
##### 出力例1
```
3
```
ラビットの家 → オウルの家 → イーオーの家と移動するのが最適で、移動距離は $2+1 = 3$ です。
##### 入力例2
```
1
2
3
5
```
##### 出力例2
```
0
```
既にラビットの家で1回目の食事をしているので、移動する必要はありません
:::
### ◎B. Divisiblity of Differences
:::spoiler **クリックで展開**
TL: 1s ML: 512MB
#### ●問題
$n$ 個の整数からなる多重集合が与えられます。あなたは、任意の2整数の差が $m$ で割り切れるようにちょうど $k$ 個の整数を選ぶか、不可能である場合はそのことを教えてください。
元の多重集合でも、選択された数からなる多重集合でも同じ整数が複数回登場できます。ただし、ある整数が、選ばれた数からなる多重集合に現れる個数は元の多重集合に現れる個数を超えてはいけません。
#### ●入力
最初の行に、3つの整数 $n, k, m (2 \leq k \leq n \leq 100000, 1\leq m \leq 100000)$ が与えられます。それぞれ 多重集合に含まれる整数の個数、選ぶ必要のある整数の個数、選んだ整数同士の差の約数です。
二行目に、 $n$ 個の整数 $a_1, a_2, \ldots, a_n(0 \leq a_i \leq 10^9)$ として、多重集合の要素が与えられます。
#### ●出力
条件を満たす用に $k$ 個の整数を選べない場合は `No` と出力してください。
可能な場合は、最初の行に `Yes` と出力してください。そして、二行目に $k$ 個の整数 $b_1, b_2, \ldots, b_k$ として、選んだ整数を出力してください。複数の解が存在する場合、いずれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
3 2 3
1 8 4
```
##### 出力例1
```
Yes
1 4
```
##### 入力例2
```
3 3 3
1 8 4
```
##### 出力例2
```
No
```
##### 入力例3
```
4 3 5
2 7 7 7
```
##### 出力例3
```
Yes
2 7 7
```
:::
### ◎C. Classroom Watch
:::spoiler **クリックで展開**
TL: 1s ML: 512MB
#### ●問題
8年生のVovaは、今日は日直です。彼は黒板を消すために教室に行き、黒板の上に整数 $n$ が書いてあるのを見つけました。
数学の教師曰く、これは1年生の数学の課題の答えです。この問題は、ある正の整数 $x$ が与えられた時、$x + (xの各桁の和)$ を求める問題です。
Vovaは、$n$ から $x$ を推測することにしました。考えられる $x$ を全て求めてください。 $x$ として有りうる正の整数が存在しない場合もあります。
#### ●入力
最初の行に、整数 $n(1 \le n \le 10^9)$ が与えられる。
#### ●出力
最初の行に、$x$ として考えられる正の整数の個数 $k$ を出力してください。続く $k$ 行に、 $x$ として考えられる値を昇順に出力してください。
#### ●入出力例
##### 入力例1
```
21
```
##### 出力例1
```
1
15
```
$x = 15$ の時、 $15+1+5 = 21 = n$ を満たします。
##### 入力例2
```
20
```
##### 出力例2
```
0
```
:::
### ◎D. Sorting the Coins
:::spoiler **クリックで展開**
TL: 1s ML: 512MB
#### ●問題
最近 Dima は コレクター向けのお店で Sasha と出会い、それからは二人でコイン収集を始めました。彼らが好きな作業はコインのコレクションをソートすることです。Sasha は物を順番に並べることが好きなので、流通していないコインの次に流通しているコインが来るよう一列に並べたいです。
コインを並べるために、 Dima は次のアルゴリズムを用いました。一回のステップでは、アルゴリズムは次のように動きます。
1. すべてのコインを左から右に向かって順番に見ていく。
2. $i$ 番目のコイン が流通していて、 $i+1$ 番目のコインは既に流通していないとき、2つのコインを入れ替えて $i+1$ 番目のコインから再開する。
Dima はこの手順を、1ステップの間で交換が起きなくなるまで繰り返します。 Dima は列をソートするために上のアルゴリズムに従ったとき繰り返す必要のあるステップの回数を、*並び替えの難しさ* と呼ぶことにしました。これは、彼がコインを先頭から見ていく回数です。例えば、既にソートされている列の並び替えの難しさは 1 です。
今日、Sasha は Dima を招きゲームを提案しました。まず、彼は $n$ 個の流通していないコインを1列に並べます。 そして、Sasha が流通していないコインを一つ選び、流通しているコインと交換することを $n$ 回繰り返します。このプロセスの間、 Sasha は毎回 Dima に現在の列についての並び替えの難しさを質問します。
Dima はコインに触れずに並び替えの難しさを頭の中で求める必要があるため、この問題はより難しいです。 Dima を助けてあげましょう。
#### ●入力
最初の行に、1つの整数 $n (1 \leq n \leq 300000)$ として Dima の前に Sasha が置くコインの数が与えられます。
二行目に、 $n$ 個の異なる整数 $p_1, p_2, \ldots, p_n(1 \leq p_i \leq n)$ として、Sasha が流通しているコインと交換する位置が与えられます。Sasha は、まず $p_1$ にあるコインを交換し、次に $p_2$ にあるコインを交換していくようにと続けていきます。コインは左から右に番号が付けられています。
#### ●出力
$n+1$ 個の整数 $a_0, a_1, \ldots, a_n$ を出力してください。
$a_0$ は最初の並び替えの難しさ、$a_1$ は最初の交換を行った後の並び替えの難しさでその後は同様です。
#### ●入出力例
##### 入力例1
```
4
1 3 4 2
```
##### 出力例1
```
1 2 3 2 1
```
`o` で流通していないコイン、`x` で流通しているコインを表します。
最初、列には流通していないコインだけがあるため、Dima は一度左から右にコインを見て、隣り合ったコインを交換せずに終了します。
最初のコインの置き換えの後の状況を考えます。
Dima はこのコインを3回交換して最後尾まで動かします。その後、もう一度コインを全部見て手続きを終了します。
`xooo -> ooox`
3つ目のコインを置き換えた後、Dima は次のように行動します。
`xoxo -> oxox -> ooxx`
4つ目のコインを置き換えた後は、次のように行動します。
`xoxx -> oxxx`
最後に、2つ目のコインを交換すると列には流通しているコインのみが含まれているため、Dima は一度コインを左から右に見た後交換を行わずに終了します。
##### 入力例2
```
8
6 8 3 4 7 2 1 5
```
##### 出力例2
```
1 2 2 3 4 3 4 5 1
```
:::
### ◎E. National Property
:::spoiler **クリックで展開**
TL: 1s ML: 512MB
#### ●問題
Library of Booklandは、世界最大の図書館です。Booklandでは、非常にたくさんの文字が使われているため、各文字は番号(1つの整数)で代用されています。各文字には大文字と小文字があり、$x$ の大文字は $x'$ と表記します。
辞書順では、小文字同士・大文字同士については番号順ですが、大文字と小文字に関しては、全ての大文字は全ての小文字に対して辞書順で前です。
例: $2 < 3\ ,\ 2' < 3'\ ,\ 3' < 2$
Denisは、小文字のみからなる単語列を持っています。彼は、単語列の順番を変えることなく、この単語列を辞書順昇順にしたいです。彼のできる操作は、ある未操作の小文字を選んで、その文字の**単語列内のすべての出現箇所**を大文字にすることだけです。
彼がこの操作を0回以上の任意の回数行って、単語列を辞書順昇順にできるでしようか？ 可能か判定し、可能な場合行うべき操作を求めてください。
単語列内に、等しい単語が含まれている可能性があることに注意してください。
*☆備考*
単語 $x_1,x_2,...,x_a$ は、以下の条件の少なくとも片方を満たすとき、 単語 $y_1,y_2,...,y_b$ よりも辞書順で大きくないと定義します。
- $a \le b$ かつ、$x_1=y_1,x_2=y_2, ... , x_a=y_a$ である。つまり、前の単語が後ろの単語の接頭辞である。
- $x_1=y_1, ... , x_{j-1}=y_{j-1}$ かつ $x_j < y_j$ を満たす整数 $j\ (1 \le j \le \mathrm{min}(a,b))$ が存在する。
#### ●入力
1行目に、2整数 $n,m (2 \le n \le 100000,1 \le m \le 100000)$ が与えられる。$n$ は、単語列内の単語の個数である。$m$ は、Booklandの文字の種類数である。各文字は、$1$ 以上 $m$ 以下の整数で表現される。
続く $n$ 行に単語が与えられる。$l_i,s_{i,1},s_{i,2},s_{i,l_i}\ (1 \le l_i \le 100000, 1 \le s_{i,j} \le m)$ の形式で与えられ、まず単語の長さ $l_i$ が与えられたのちに単語 $s_i$ の各文字が順に与えられる。
単語列内の単語の長さの総和は、$100000$ を超えないことが保証されます。
#### ●出力
可能な場合は、1行目に `Yes` と出力してください。そうでない場合は、`No` と出力します。
`Yes` を出力した場合、2行目に 行う操作の回数 $k$ を出力します。3行目に、操作を行う文字を示す異なる $k$ 個の整数を出力します。$k$ を最小化する必要はありません。
答が複数ある場合、どれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
4 3
1 2
1 1
3 1 3 2
2 1 1
```
##### 出力例1
```
Yes
2
2 3
```
操作後の単語列は以下になります。
- 2'
- 1
- 1 3' 2'
- 1 1
これは辞書順昇順になっています。
##### 入力例2
```
6 5
2 1 2
2 1 2
3 1 2 3
2 1 5
2 4 4
2 4 4
```
##### 出力例2
```
Yes
0
```
操作をしなくても、最初から辞書順昇順です。
##### 入力例3
```
4 3
4 3 2 2 1
3 1 1 3
3 2 3 3
2 3 1
```
##### 出力例3
```
No
```
:::
### ◎F. High Cry
:::spoiler **クリックで展開**
TL: 1s ML: 512MB
#### ●問題
特殊な反響が起こるため、Rick と Morty は大声で叫ぶために High Cry という峰に行くことが好きです。
最近、彼らはこの峰の面白い音響上の特徴を発見しました。もし Rick と Morty が同時に異なる山から叫ぶと、彼らの叫び声はその間にある山の内、高さが彼らが登っている山とその間にある山の高さの bitwise OR 未満である山で聞くことができます。
bitwise OR はバイナリ操作で、次のように行われます。 整数 $x, y$ のバイナリ表現を先頭の 0 を許して $x = x_k\ldots x_1x_0, y=y_k\ldots y_1y_0$ として考えます。すると、 $z = x | y$ は $z = z_k \ldots z_1z_0$ としたとき、$x_i = 1$ もしくは $y_i = 1$ のときに $z_i = 1$、それ以外の場合は $z_i = 0$ になります。言い換えると、2つの数の bitwise OR のある桁が $0$ になるのは、両方の数の対応する位置の桁が $0$ になるときに限ります。例えば、$10 = 1010_2, 9 = 1001_2$ の bitwize OR は $11 = 1011_2$ になります。
2つの山の選び方であって、Rick と Morty がそれらの山で叫んだときに叫び声がその2つの山と間にある山全てで聞こえるようなものが何通りあるかを計算してください。より形式的には、$l, r(1 \leq l < r \leq r)$ のペアであって、端を含めて $l$ と $r$ の間にある山の高さの bitwise OR がこの区間にある任意の山よりも大きくなるようなものの個数を求めてください。
#### ●入力
最初の行に、整数 $n(1 \leq n \leq 200000)$ として峰にある山の個数が与えられます。
二行目には、$n$ 個の整数 $a_i (0 \leq a_i \leq 10^9)$ が与えられます。これらは峰に並んでいる山の高さを順番に並べたものです。
#### ●出力
一つの整数として、2つの異なる山を選ぶ方法の数を出力してください。
#### ●入出力例
##### 入力例1
```
5
3 2 1 6 5
```
##### 出力例1
```
8
```
1から番号をつけたとき、次が条件を満たすペアです。
$$
(1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)
$$
##### 入力例2
```
4
3 3 3 3
```
##### 出力例2
```
0
```
任意のペアについて叫び声の高さは $3$ になりますが、山の高さも全て $3$ なので答えは $0$ になります。
:::
## ◎ヒント・解説
### ◎A. Trip For Meal
:::spoiler **◎ヒント1**
考えられる場合を全て列挙し、最小化すればよいです
:::
:::spoiler **◎ヒント2**
基本的には、同じ道を何度も往復するのが最適になります。
:::
:::spoiler **◎解説**
以下の4パターンを網羅して、最小値を取ればよいです。
- $a$ の道のみを往復する場合
- $b$ の道のみを往復する場合
- $a$ を利用して $c$ の道に到達し、 $c$ の道を往復する場合
- $b$ を利用して $c$ の道に到達し、 $c$ の道を往復する場合
$n = 1$ の場合に注意して実装しましょう。
:::
:::spoiler **◎実装例(Python)**
```python=
import sys
from sys import stdin
n = int(stdin.readline())
n -= 1
a = int(stdin.readline())
b = int(stdin.readline())
c = int(stdin.readline())
if n == 0:
ans = 0
else:
ans = min(a*n,b*n , a+c*(n-1) , b+c*(n-1))
print (ans)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ll n,a,b,c,ans;
cin >> n >> a >> b >> c;
n--;
if (n == 0) ans = 0;
else ans = min( min(a*n,b*n) , min(a+c*(n-1) , b+c*(n-1)) );
cout << ans << endl;
}
```
:::
### ◎B. Divisiblity of Differences
:::spoiler **◎ヒント1**
$a - b \equiv 0 \pmod m$ のとき、$a$ と $b$ を同時に選ぶことができます。
:::
:::spoiler **◎ヒント2**
移項すると $a \equiv b \pmod m$ です。
:::
:::spoiler **◎解説**
$m$ で割ったあまりでグループ分けすると、同じグループに $k$ 個以上の要素があればそこから $k$ 個出力すればよいです。
Python ならリストを載せた dictionary、C++ なら vector を載せた map を使って実装するのが楽です。
:::
:::spoiler **◎実装例(python3)**
```python=
n, k, m = map(int, input().split())
a = list(map(int, input().split()))
groups = dict()
for x in a:
rem = x % m
if rem not in groups:
groups[rem] = []
groups[rem].append(x)
ok = False
for g in groups.values():
if len(g) >= k:
print("Yes")
print(*g[:k])
ok = True
break
if not ok:
print("No")
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, k;
cin >> n >> k >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
map<int, vector<int>> groups;
for (const auto &x : a) {
groups[x % m].push_back(x);
}
for (const auto &[rem, g] : groups) {
if (g.size() >= k) {
cout << "Yes" << endl;
for (int i = 0; i < k; i++) {
cout << g[i] << " ";
}
cout << endl;
return 0;
}
}
cout << "No" << endl;
}
```
:::
### ◎C. Classroom Watch
:::spoiler **◎ヒント1**
桁和の取りうる最大値を考えてみましょう
:::
:::spoiler **◎ヒント2**
探索するべき $x$ のは範囲は非常に小さいです。
:::
:::spoiler **◎解説**
$x < n \le 10^9$ なので、$x < 10^9$ です。
$9$ 桁以下の整数で、桁和が最も大きい場合は $999999999$ で、桁和は81です。
よって、$x$ として考えられるのは $n-81$ 以上 $n$ 未満の場合のみであることが分かります。後は、この範囲を全探索すればよいです。
:::
:::spoiler **◎実装例(Python)**
```python=
import sys
from sys import stdin
def solve(x):
ret = x
while x:
ret += x % 10
x //= 10
return ret
n = int(stdin.readline())
ANS = []
for i in range(max(1,n-81) , n):
if solve(i) == n:
ANS.append(i)
print (len(ANS))
print ("\n".join(map(str,ANS)))
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll solve(ll x){
ll ret = x;
while (x){
ret += x % 10;
x /= 10;
}
return ret;
}
int main() {
ll n;
cin >> n;
vector<ll> ans;
for (ll i = max(1LL,n-81) ; i < n ; ++i){
if (solve(i) == n) ans.push_back(i);
}
cout << ans.size() << endl;
for (ll i = 0 ; i < ans.size() ; ++i){
cout << ans[i];
if (i == ans.size()-1) cout << '\n';
else cout << ' ';
}
}
```
:::
### ◎D. Sorting the Coins
:::spoiler **◎ヒント1**
一度どのようにコインが動くか手で試してみましょう。
:::
:::spoiler **◎ヒント2**
自分より右に流通していないコインがないものを右端に到達したコインと呼ぶことにします。
まだ右端についていないコインで最も右にあるものは、1ステップで右端に到達します。
:::
:::spoiler **◎ヒント3**
ヒント2の状況で、最も右にあるもの以外は右端に到達しません。
:::
:::spoiler **◎解説**
各段階で、右端にない流通しているコインの個数がわかればいいです。
これは、右端にある流通しているコインの個数を求めてそれを既に入れ替えた個数から引けば求められます。
右から何番目まで流通しているかというポインターを持っておいて、その左が流通している間は左に進めるということをすると最後まで合わせて $n$ 回しか動かさないので十分早く解くことができます。
:::
:::spoiler **◎実装例(python3)**
```python=
n = int(input())
p = list(map(int, input().split()))
cir = [False] * n
ptr = n
res = [1]
for i in range(n):
cir[p[i] - 1] = True
while ptr > 0 and cir[ptr - 1]:
ptr -= 1
res.append(i + 1 - (n - ptr) + 1)
print(*res)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> p(n);
for (int i = 0; i < n; i++) {
cin >> p[i]; p[i]--;
}
vector<bool> cir(n, false);
int ptr = n;
cout << 1 << " ";
for (int i = 0; i < n; i++) {
cir[p[i]] = true;
while (ptr > 0 && cir[ptr - 1]) {
ptr--;
}
cout << i + 1 - (n - ptr) + 1 << " ";
}
cout << endl;
}
```
:::
### ◎E. National Property
:::spoiler **◎ヒント1**
隣り合う文字列だけ見ればいいです。
:::
:::spoiler **◎ヒント2**
隣り合う文字列のうち、最初の異なる文字だけ見ればよいです。
:::https://hackmd.io/geu5HXqMTQqvYlwRmu-tQA
:::spoiler **◎ヒント3**
隣り合う文字列のうち、最初の異なる文字がそれぞれ $x,y$ だとします。
$x > y$ の時、 $x < y$ の時、それぞれ分けて考えてみましょう。
:::spoiler **◎ヒント4**
- $x > y$ の時、$x$ は大文字化必須、 $y$ は小文字のまま必須(大文字化禁止)となります。
- $x < y$ の時、$y$ を大文字化した場合、$x$ も大文字化する必要があります。
:::
:::spoiler **◎解説**
まず、ヒントを読んでください。
$x,y$ のペアを見ていき、各文字に制約を課していきます。
各文字に課された制約の状態を以下の0～3の値で記録します。
0. 制約なし
1. 小文字のまま必須 (大文字化禁止)
2. 大文字化必須
3. 大文字化必須かつ、大文字化禁止
このように記録すると、大文字化を必須にしたいときは 2 を ORし、
大文字化を禁止したいときは、 1 を ORすればいいので状態管理が楽です。
また、状態が3になる文字があった場合、矛盾するので答えは No です。
まず、以下の条件を全て処理します。
- $x > y$ の時、$x$ は大文字化必須、 $y$ は小文字のまま必須(大文字化禁止)となります。
これは、$x$ の状態に 2をORし、 $y$ の状態に 1をORするだけなので簡単に処理できます。
次に、以下の条件を処理します。
- $x < y$ の時、$y$ を大文字化した場合、$x$ も大文字化する必要があります。
まず $m$ 頂点 0辺ののグラフを用意します。各条件に対して $y \longrightarrow x$ に有向辺を引きます。キューを用意し、大文字化が必須の頂点を全て入れます。後は、以下の操作をキューが空になるまで繰り返します。
- キューから頂点を1つ取り出す。この頂点を $u$ とする。辺 $u \longrightarrow v$ が存在し、現時点で大文字化が必須でない全ての頂点 $v$ に関して、$v$ の状態に 2をORし、$v$ をキューにpushする。
操作後、状態が3となっている頂点があった場合、答えは No です。
そうでない場合、答えは Yes で、状態が 2であるような頂点全てに対して操作を行うことで目標を達成できます。
:::
:::spoiler **◎実装例(python)**
```python=
import sys
from sys import stdin
from collections import deque
n,m = map(int,stdin.readline().split())
state = [0] * (m+1)
s = []
for i in range(n):
word = list(map(int,stdin.readline().split()))[1:]
s.append(word)
lis = [ [] for i in range(m+1) ]
for i in range(n-1):
w1 = s[i]
w2 = s[i+1]
for j in range( min( len(w1) , len(w2) )):
if w1[j] != w2[j]:
if w1[j] > w2[j]:
state[w1[j]] |= 2
state[w2[j]] |= 1
else:
lis[w2[j]].append(w1[j])
break
else:
if len(w1) <= len(w2):
continue
else:
print ("No")
sys.exit()
q = deque()
for i in range(m+1):
if state[i] & 2:
q.append(i)
while q:
v = q.popleft()
for nex in lis[v]:
if state[nex] & 2 == 0:
state[nex] |= state[v]
q.append(nex)
if 3 in state:
print ("No")
sys.exit()
ANS = []
for i in range(m+1):
if state[i] == 2:
ANS.append(i)
print ("Yes")
print (len(ANS))
print (" ".join(map(str,ANS)))
```
:::
### ◎F. High Cry
:::spoiler **◎ヒント1**
各山について、その山が区間に入っているときは右と左それぞれどこまで伸びている必要があるかが知りたいです。
:::
:::spoiler **◎ヒント2**
色々な方法がありますが、各ビットが立っていた最後の要素はどれかを持ちながら左と右から見ていけば求められます。
:::
:::spoiler **◎ヒント3**
各区間をダブルカウントしないために、最大値を代表させて考えることができます。
最大値になるものを一つ決めて、条件をみたすように左右に伸ばしながら最大値であることを維持させると、区間に含まれる他の要素も条件をみたすので都合が良くなります。
:::
:::spoiler **◎解説**
まず、適当な $i$ を固定し、実際に選択するペアを $l, r$ と書くことにします。
ヒント2を実装し、まず左右どちらかはここまで伸ばさないといけないという範囲を求めておきます。これを $l_1, r_1$ とすると、$l \leq l_1$ もしくは $r_1 \leq r$ を満たす必要があります。
また、$a_i$ が最大値となる区間が $l_2, r_2$ とします。すると、 $l_2 \leq l, r \leq r_2$ は必ず成り立っている必要があります。 $l_1, r_1$ も $l_2, r_2$ をはみ出してはいけないので $\min, \max$ で収めておきましょう。
すると、$a_i$ が最大値になる区間の個数は $(r_2 - i) \cdot (i - l_2)$ であり、その中で条件を満たさない区間の個数は $(r_1 - i) \cdot (i - l_1)$ になります。前者から後者を引くと、条件を満たす区間の個数になるのでこれを足し上げればよいです。半開区間で扱うかどうかなどで、$\pm 1$ のズレが出てくるので注意してください。
$a_i$ が最大値になる区間は、stack などでうまく行うと $O(n)$ で求めることができますが、ソートして大きい値から見ていきながら既に見た座標を set に入れることで $O(n \log n)$ で少し楽に求めることができます。
同じ値が複数存在する場合にも注意する必要がありますが、区間の最大値の中で左端のものに代表させるなどの工夫を行えば問題なく解くことができます。
:::
:::spoiler **◎実装例(C++)**
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, m;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector<long long> bnext(n, n), bprev(n, -1);
{
vector<long long> bit(30, -1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < 30; j++) {
if (a[i] >> j & 1) {
bit[j] = i;
} else {
bprev[i] = max(bprev[i], bit[j]);
}
}
}
}
{
vector<long long> bit(30, n);
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < 30; j++) {
if (a[i] >> j & 1) {
bit[j] = i;
} else {
bnext[i] = min(bnext[i], bit[j]);
}
}
}
}
using P = pair<int, int>;
vector<P> ord;
for (int i = 0; i < n; i++) {
ord.emplace_back(a[i], i);
}
sort(ord.rbegin(), ord.rend());
set<int> idx;
idx.insert(-1); idx.insert(n);
long long res = 0;
for (auto &[x, i] : ord) {
auto itr = idx.lower_bound(i);
long long l = *prev(itr), r = *itr;
long long l2 = max(bprev[i], l), r2 = min(bnext[i], r);
res += (r - i) * (i - l) - (r2 - i) * (i - l2);
idx.insert(i);
}
cout << res << endl;
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet