# 競プロ講習会第19回 Web資料
## ◎第19回の参加方法について
今回も、好きな時間に問題を解いておくことができるようにします。
講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。
まず、Codeforcesにログインします。
その後、K-LMSに公開してあるコンテストリンクを開きます。
KeioAICKyoproCourseContest #19 に、**Virtual participation**します。**Enter**の方ではないので注意！！！
(※Virtual perticipation機能は、好きな時間を選んでコンテストに参加できる機能です. Enterを押して入ると、コンテスト外で問題を解いたことになります。)
開始したい時間を入力し、Registar for virtual participationを押します。
指定した時間になったらコンテストが始まるので、問題を解きます。
コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。
また、参加中であってもweb資料のヒント・解説は参照してかまいません。
Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。
#### ◎問題セット
https://codeforces.com/contestInvitation/60850ac811283ecff8c7d3b11368a25f07a7abc6
#### ◎公式解説
##### A〜G問題
https://codeforces.com/blog/entry/61356
## ◎問題訳(意訳あり注意,E問題まで)
### ◎A. Single Wildcard Pattern Matching
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
あなたは、2つの文字列 $s,t$ を貰いました。$s$ は、小文字アルファベットと、**最大1文字**のワイルドカード文字 `*` から構成されます。$t$ は、小文字アルファベットのみから構成されます。 $s$ の長さは $n$ であり、 $t$ の長さは $m$ です。
ワイルドカード文字 `*` は、任意の長さ(0も可)の小文字アルファベットの列に置き換えることができます。この操作のみを行って、 $s$ を $t$ と一致させることが可能か判定してください。
例えば、 $s$ が `aba*aba` の場合、この文字列は `abaaba`,`abacaba`,`abazzzaba` 等に変換することができます。しかし、 `ababa`, `abcaaba`, `codeforces`, `aba1aba`, `aba?aba` などに変換することはできません。
$s$ を $t$ に一致させることができる場合、`YES` を、そうでない場合 `NO` を出力してください。
#### ●入力
1行目に、2つの整数 $n,m\ (1 \le n,m \le 2 \times 10^5)$ が与えられます。これらはそれぞれ、文字列 $s,t$ の長さを表しています。
2行目に、長さ $n$ の文字列 $s$ が与えられます。これは、小文字アルファベットと、最大1文字のワイルドカード文字`*`から構成されます。
3行目に、長さ $m$ の小文字アルファベットからなる文字列 $t$ が与えられます。
#### ●出力
$s$ と $t$ を一致させることが可能な場合、`YES` を、そうでない場合 `NO` を出力してください。
#### ●入出力例
##### 入力例1
```
6 10
code*s
codeforces
```
##### 出力例1
```
YES
```
ワイルドカード文字`*` を、`force` に置き換えることで一致させられます。
##### 入力例2
```
6 5
vk*cup
vkcup
```
##### 出力例2
```
YES
```
ワイルドカード文字`*` を、空文字列に置き換えることで一致させられます。
##### 入力例3
```
1 1
v
k
```
##### 出力例3
```
NO
```
ワイルドカード文字が無く、元々 $s,t$ が等しくないため、答えは `NO` です。
##### 入力例4
```
9 6
gfgf*gfgf
gfgfgf
```
##### 出力例4
```
NO
```
どのように置き換えても、$s$ が $t$ よりも長くなってしまうので、答えは `NO` です。
:::
### ◎B. Pair of Toys
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
Tanechka はおもちゃ屋さんで買い物をしています。お店ではちょうど $n$ 個のおもちゃが売られていて、 $i$ 番目のおもちゃの値段は $i$ 円です。 彼女は、値段の合計が $k$ 円になるように2つのおもちゃを選びたいです。 そのように選ぶ方法は何通りあるでしょうか。
それぞれの玩具はちょうど1つしかありません。ペア $(a, b)$ と $(b, a)$ は同じものとみなし、 $a = b$ は認められません。
#### ●入力
最初の行に、2つの整数 $n, k (1 \leq n, k \leq 10^{14})$ が与えられます。それぞれ、おもちゃの個数と希望の合計価格です。
#### ●出力
条件を満たすようにおもちゃのペアを選ぶ方法が何通りあるか出力してください。 Tanechka がおもちゃのペアの合計価格が $k$ 円になるように選べない場合は $0$ を出力してください。
#### ●入出力例
##### 入力例1
```
8 5
```
##### 出力例1
```
2
```
Tanechka は ペア $(1, 4)$ と $(2, 3)$ を選ぶことができます。
##### 入力例2
```
8 15
```
##### 出力例2
```
1
```
Tanechka はペア $(7, 8)$ だけを選ぶことができます。
##### 入力例3
```
7 20
```
##### 出力例3
```
0
```
どのようにペアを選んでも、合計価格が $20$ 円になるようにできないため答えは 0 になります。
##### 入力例4
```
1000000000000 1000000000001
```
##### 出力例4
```
500000000000
```
次のペアが選択できます: $(1,1000000000000) , (2,999999999999), (3,999999999998), \ldots, (500000000000,500000000001)$ . よって、そのようなペアはちょうど $500000000000$ 個あります。
:::
### ◎C. Bracket Subsequence
:::spoiler **クリックで展開**
TL: 2s ML: 256MB
#### ●問題
括弧列は、`(` と `)` の2種類の文字のみが使用された文字列です。正しい括弧列とは、`1` と `+` をそれぞれある個数・ある位置に挿入することで、正しい数式になる括弧列のことを指します。
例えば、`()()` や `(())` は、それぞれ `(1)+(1)` や `((1+1)+1)` に出来るので、正しい括弧列です。一方、 `)(` や `(` , `)` などは正しい括弧列ではありません。
また、部分列とは、列から0個以上の要素を選んで削除し、残った要素を元の順番で連結することで得られる列のことを指します。
さて、あなたは長さ $n$ の正しい括弧列 $s$ と、正の偶数 $k$ を貰いました。
$s$ の長さ $k$ の部分列で、正しい括弧列であるような物を見つけてください。
なお、このような部分列はこの問題の制約上で常に存在することが証明できます。
#### ●入力
1行目に、2つの整数 $n,k (2 \le k \le n \le 2 \times 10^5)$ が与えられます。$n,k$ は共に整数です。
2行目に、長さ $n$ の正しい括弧列が与えられます。
#### ●出力
文字列を1つ出力してください。これは、長さ $k$ の正しい括弧列であり、$s$ の部分列である必要があります。
答えは常に存在することが示せます。
#### ●入出力例
##### 入力例1
```
6 4
()(())
```
##### 出力例1
```
()()
```
##### 入力例2
```
8 8
(()(()))
```
##### 出力例2
```
(()(()))
```
:::
### ◎D. Array Restoration
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
最初に $n$ 個の整数からなる配列 $a$ が与えられ、位置は $1$ から $n$ で番号付けられています。
ちょうど $q$ 個のクエリによって配列に対して操作が行われます。 $i$ 番目のクエリでは、ある区間 $(l_i, r_i) (1 \leq l_i \leq r_i \leq n)$ が選ばれ、端を含めて $l_i$ から $r_i$ の位置にある要素の値が $i$ に変更されます。クエリの順番は変わらず、 $q$ 個のクエリ全てが適用されます。 また、各位置 $1$ から $n$ は少なくとも1つの区間に含まれています。
あなたに出題される問題は、$n$ 個の $1$ から $q$ の範囲の整数からなる配列が与えられたときに、前述したクエリによってその配列を得ることができるかどうかです。しかし、このままではあなたにとって簡単すぎると考えました。
なので、次のようにして問題を難しくします。 与えられた配列のいくつかの位置 (0箇所の可能性もありえます) を選び、それらの位置にある要素の値を $0$ にします。
あなたは、この配列を前述したクエリによって生成することができるかどうかを判定してください。また、生成できるのであれば元の配列を復元してください。
複数の配列があり得る場合は、いずれを出力しても構いません。
#### ●入力
最初の行に、2つの整数 $n, q (1 \leq n, q \leq 2 \cdot 10^5)$ として、配列に含まれる要素の数と行われるクエリの数が与えられます。
2行目には、$n$ 個の整数 $a_1, a_2, \ldots, a_n(0 \leq a_i \leq q)$ が与えられます。 これはクエリを適用した後に、いくつかの要素を $0$ にした配列です。 もしも位置 $j$ の要素が $0$ であれば、この位置の要素は $1$ から $q$ の任意の整数であった可能性があります。
#### ●出力
配列 $a$ が $q$ 個のクエリによって生成できる場合は `YES` と出力してください。 区間 $(l_i, r_i) (1 \leq l_i \leq r_i \leq n)$ はクエリごとに別々で決められ、各位置 $1$ から $n$ は少なくとも1つの区間に含まれています。
生成できない場合は `NO` と出力してください。
配列が生成できる場合は、2行目に $n$ 個の整数を出力してください。 $i$ 番目の数は生成された配列の $i$ 番目の要素で、 $1$ 以上 $q$ 以下の整数です。 この配列はちょうど $q$ 個のクエリによって得られるものである必要があります。
複数の配列があり得る場合は、そのなかのいずれを出力しても構いません。
#### ●入出力例
##### 入力例1
```
4 3
1 0 2 3
```
##### 出力例1
```
YES
1 2 2 3
```
$0$ を $1$ と置き換えることができます。ただし、 $3$ で置き換えることはできません。
##### 入力例2
```
3 10
10 10 10
```
##### 出力例2
```
YES
10 10 10
```
区間 $(1, 3) にクエリ 10 を行うまでのクエリはどのような区間を選択しようと関係ありません。
##### 入力例3
```
5 6
6 5 6 2 2
```
##### 出力例3
```
NO
```
この例はクエリの順番は変わらないことの一例です。最初に区間 $(1, 3)$ を $6$ にした後に区間 $(2, 2)$ を $5$ にすることはできません。クエリ $5$ はクエリ $6$ の前に適用されます。
##### 入力例4
```
3 5
0 0 0
```
##### 出力例4
```
YES
5 4 2
```
複数の答えが存在します。
:::
### ◎E. Down or Right
:::spoiler **クリックで展開**
TL: 1s ML: 256MB
#### ●問題
この問題は、インタラクティブ問題です。
ボブは、$n \times n$ のグリッドに住んでいます。各行は上から下へと順に $1,2,...,n$ と、各列は左から右へと順に $1,2,...,n$ と番号が付けられています。各マスは、ブロックで塞がれているか、通行可能かのどちらかです。あなたは、まず整数 $n$ を受け取ります。
ボブはこのマス目の上を移動します。 しかし、ボブはしたか右にしか移動できません。
あなたは、$4 \times n$ 回まで質問をすることができます。
形式は、"$?\ r_1\ c_1\ r_2\ c_2$" $(1 \le r_1 \le r_2 \le n,1 \le c_1 \le c_2 \le n)$ であり、ボブの返答はマス $(r_1,c_1)$ から $(r_2, c_2)$ に移動できる場合 `YES` となり、そうでない場合 `NO` となります。特に、2つのマスの内の少なくとも片方がブロックされていた場合、返答は必ず `NO` となります。
また、ボブは短い旅が嫌いなため、あなたの質問の2つのマスはマンハッタン距離で少なくとも $n-1$ 以上離れている必要があります。すなわち、以下の条件を満たしている必要があります。
- $(r_2-r_1)+(c_2-c_1) \ge n-1$
左上 $(1,1)$ のマスから、右下 $(n,n)$ のマスまで移動できることは保証されます。あなたの仕事は、左上のマスから右下のマスまでの移動方法を見つけることです。答として、あなたは "$!\ S$" を出力します。$S$ は、長さ $2n-2$ の文字列で、`D` と `R` のみからなります。`D` は $(x,y)$ から $(x+1,y)$ への移動を、`R` は $(x,y)$ から $(x,y+1)$ への移動を表しています。 $(1,1)$ からスタートし、$S$ の指示に従うことで $(n,n)$ に到達可能な場合、正解となります。答が複数ある場合、どれを出力しても正解となります。
#### ●入力
1行目に、1つの整数 $n\ (2 \le n \le 500)$ が与えられます。これはグリッドのサイズを表しています。
#### ●出力
答えを出力する準備が整ったら、"$!\ S$" を出力してください。$S$ は、長さ $2n-2$ の文字列で、`D`,`R` の2種類の文字から構成され、それぞれ下・右の移動を示しています。これは、$(1,1)$ から $(n,n)$ までの、通行可能なパスを表しています。
#### ●インタラクション
あなたは、答えを出力する前に $4n$ 回の質問をすることができます。質問の形式は、"$?\ r_1\ c_1\ r_2\ c_2$" $(1 \le r_1 \le r_2 \le n,1 \le c_1 \le c_2 \le n)$ であり、ボブがマス $(r_1,c_1)$ から $(r_2, c_2)$ に移動できる場合 `YES` が返り、そうでない場合 `NO` が返ります。
グリッドは最初に決定され、あなたのクエリの内容によって変化することはありません。
クエリを出力した後は、忘れずにflush出力をしてください。行わない場合、 Idleness limit exceeded や、他の不正解が返る可能性があります。より具体的には、以下を行ってください。
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- 他の言語の場合、ドキュメントを見てください。
クエリの返答として、`BAD` が `YES`や`NO` が返ってきた際、あなたが不正なクエリを行ったことを示しています。`BAD` を受け取った際には、即座に終了してください。この時、Wrong Answer となります。終了しない場合、任意のverdictとなる可能性があります。
#### ●入出力例
##### 入力例1
```
4
YES
NO
YES
YES
```
##### 出力例1
```
? 1 1 4 4
? 1 2 4 3
? 4 1 4 4
? 1 4 4 4
! RDRRDD
```
以下の図のようになります。
:::
## ◎ヒント・解説
### ◎A. Single Wildcard Pattern Matching
:::spoiler **◎ヒント1**
ワイルドカードが無い場合とある場合で場合分けしましょう。
:::
:::spoiler **◎ヒント2**
様々な解法がありますが、$n,m$ が大きいので、一切計算量を考えないとTLEになる恐れがあります。
:::
:::spoiler **◎ヒント3**
ワイルドカードがある場合は、WAが出がちです。
YESとなる十分条件を徹底的に列挙してみるのも有りです。
:::
:::spoiler **◎解説**
ワイルドカードがない場合は、$s,t$ が一致しているか調べるだけなので簡単です。
ワイルドカードがある場合は様々な方針が考えられますが、例として3つの方法を挙げておきます。
1. $s$ をワイルドカードの前後で切り、それぞれ $l,r$ とする。$l$ が $t$ の接頭辞と一致し、$r$ が $t$ の接尾辞と一致し、$|l|+|r| \ge |t|$ ならば `YES`。そうでなければ `NO`
2. $s,t$ が空でなく、両者の一番後ろの文字が一致している限り取り除く操作を続ける。$s,t$ の前後を反転して、同様の操作を行う。操作後、が`*`ならば `YES`。そうでなければ `NO`
3. ワイルドカードマッチングを行えるライブラリ(正規表現ライブラリなど)を使用する。意外と使用法を調べたりするのが面倒。
方針を決めたら実装を頑張るだけの問題なのですが、WAを出してしまいがちです。
以下の実装を提出して私も1回 WAとなってしまったので気を付けましょう。(何が間違っているか、わかりますか…？)
```python=
import sys
from sys import stdin
n,m = map(int,stdin.readline().split())
s = stdin.readline()[:-1]
t = stdin.readline()[:-1]
if "*" not in s:
if s == t:
print ("YES")
else:
print ("NO")
else:
l,r = s.split("*")
slen = len(l+r)
if slen > len(t):
print ("NO")
elif l == t[:len(l)] and t[-len(r):] == r:
print ("YES")
else:
print ("NO")
```
この回答は、$|r| = 0$ の時に、26行目の if 文の $t[-len(r):]$ の箇所がバグります。
:::
:::spoiler **◎実装例(Python)**
方針1で解いています。上のWAの例を基にしています。
```python=
import sys
from sys import stdin
n,m = map(int,stdin.readline().split())
s = stdin.readline()[:-1]
t = stdin.readline()[:-1]
if "*" not in s:
if s == t:
print ("YES")
else:
print ("NO")
else:
l,r = s.split("*")
slen = len(l+r)
tr = "" if len(r) == 0 else t[-len(r):]
if slen > len(t):
print ("NO")
elif l == t[:len(l)] and tr == r:
print ("YES")
else:
print ("NO")
```
:::
:::spoiler **◎実装例(C++)**
方針2で解いています。
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,m;
cin >> n >> m;
string s,t;
cin >> s >> t;
if (s.find("*") == string::npos){
if (s == t) cout << "YES" << endl;
else cout << "NO" << endl;
return 0;
}
while (s.size() > 0 && t.size() > 0 && s.back()==t.back()){
s.pop_back();
t.pop_back();
}
reverse(s.begin(),s.end());
reverse(t.begin(),t.end());
while (s.size() > 0 && t.size() > 0 && s.back()==t.back()){
s.pop_back();
t.pop_back();
}
if ((s.size() == 0) || (s == "*")) cout << "YES" << endl;
else cout << "NO" << endl;
}
```
:::
### ◎B. Pair of Toys
:::spoiler **◎ヒント1**
$a + b = k$ となる $a, b$ が存在するかどうかをまず考えてみましょう。
:::
:::spoiler **◎ヒント2**
存在する場合、 $a < b$ としたときに $a$ の最小値は何になるか考えてみましょう。
:::
:::spoiler **◎ヒント3**
$a < b$ で $a$ が最小のとき、 $(a+1, b-1)$ も答えになることがあります。
:::
:::spoiler **◎ヒント4**
$a = b$ は許されていないことに注意しましょう。
:::
:::spoiler **◎解説**
まず、 $n + (n - 1)$ が $k$ としてありえる最大、 $1 + 2$ が最小になることに注意しましょう。 この範囲外なら答えは $0$ になります。
$a$ の最小値は、 $\max(1, k - n)$ になります。 これは、b の最大としてありえるのが $n$ なので $k-n$ が単純に考えると最小ですが、 $0$ 以下になってはいけないので $1$ との max を取っています。
そのときの $b$ は $k - a$ になります。
後は他のペアがいくつあるかを考えます。
例えば、 $(n, k) = (9, 12)$ の場合は $(3, 9), (4, 8), (5, 7)$ と、両側から 1 ずつ縮めていくような形になります。なので、 区間 $[a, b]$ にある整数の個数を $2$ で割ったものになります。 ただし、 $(6, 6)$ は許されてないので切り捨てになります。
つまり、 $a, b$ を求めたら $\left\lfloor \frac{b - a + 1}{2} \right\rfloor$ が答えです。
:::
:::spoiler **◎実装例(python3)**
```python=
n, k = map(int, input().split())
a = max(1, k - n)
b = k - a
if b < a:
print(0)
else:
print((b - a + 1) // 2)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, k;
cin >> n >> k;
long long a = max(1LL, k - n), b = k - a;
if (b < a) {
cout << 0 << endl;
} else {
cout << (b - a + 1) / 2 << endl;
}
}
```
:::
### ◎C. Bracket Subsequence
:::spoiler **◎ヒント1**
$k$ 文字の正しい括弧列には、`(` と `)` が $k/2$ 個ずつ含まれます。
:::
:::spoiler **◎ヒント2**
正しい括弧列から、対応する括弧のペアを1つ取り除いても、正しい括弧列になります。よって、これを利用し、対応する括弧を消していくことで答となります。
ただし、もっと簡単な方法があります。
:::
:::spoiler **◎解説**
最初から $k/2$ 個の `(` と、最初から $k/2$ 個の `)` を抜き出し、元の順番で並べれば答えとなります。
理由を説明します。
括弧列が、正しい括弧列である必要十分条件は、以下のように言い換えられます。
- `(` と `)` の個数が等しい
- 任意の $i$ について、$i$ 文字目までに出現した `(` の個数が、 `)` の個数以上である。
さて、これを利用して上の解法が正しいことを証明します。
$k/2$ 番目の `(` が、$s$ の $j$ 文字目であったとします。$s$ は正しい括弧列なので、任意の $i (\le j)$ について、$i$ 文字目までに出現した `(` の個数が、 `)` の個数以上であることが分かります。この条件は、$j$ 文字目までに出現する `)` をどのように削除しても保たれます。
$j$ 文字目までの時点で、`(` が $k/2$ 個あるので、$j+1$ 文字目以降の `)` を $k/2$ 個になるまでとったとしても、 `)` の個数が `(` の個数を上回ることはありません。
よって以上の議論より、解法が正しいことが分かります。
:::
:::spoiler **◎実装例(Python)**
```python=
n,k = map(int,input().split())
s = input()
L = R = k//2
ans = []
for c in s:
if c == "(" and L > 0:
L -= 1
ans.append(c)
elif c == ")" and R > 0:
R -= 1
ans.append(c)
print ("".join(ans))
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,k;
cin >> n >> k;
string s,ans;
cin >> s;
int L = k/2;
int R = k/2;
for (char c : s){
if (c == '(' && L > 0){
ans += c;
L--;
}else if (c == ')' && R > 0){
ans += c;
R--;
}
}
cout << ans << endl;
}
```
:::
### ◎D. Array Restoration
:::spoiler **◎ヒント1**
まず、 $0$ がないときにその配列があり得るかどうか判定する方法を考えてみましょう。
:::
:::spoiler **◎ヒント2**
$a_l = a_r = x$ のとき、 区間 $(l, r)$ に $x$ 未満の数があってはいけません。
:::
:::spoiler **◎ヒント3**
C++ であれば set を、Python なら set と heapq を組み合わせてうまく使うとヒント2 を調べることができます。
セグメントツリーなどのデータ構造を用いれば簡単に調べられます。
:::
:::spoiler **◎ヒント4**
```
1 3
0
```
このテストケースの答えは１種類です。
:::
:::spoiler **◎解説**
ほとんどヒントを実装すればよいです。ヒント２を具体的にどのように実装するかと、 $0$ の扱いを解説します。
まず、各値について左端と右端の出現箇所を調べましょう。セグメントツリーのようなデータ構造を使う場合、 $0$ を適当な大きい値で初期化しておけば各値 $x$ について左端と右端の出現位置の間の最小値が $x$ より小さいかをチェックすることができます。
C++ で set を用いる場合には、左端の出現位置で set に入れ、右端で set から取り除くことにします。 そうすると、毎回 set の最小値を調べて今の位置の値よりも大きくないかをチェックすればよいです。 Python の場合は set で最小値を知ることができないので、 heapq 等を組み合わせてうまく行いましょう。
$0$ については基本的に隣接する値をそのままコピーすればよいですが、ヒント4 にある通り、最後に行うクエリ $q$ だけは必ず残っていることになるため他の位置になければ $q$ でどこかの $0$ を置き換える必要があります。
同様に、$0$ がないときに $q$ が同時に存在しなければ `NO` になります。
:::
:::spoiler **◎実装例(python3)**
```python=
import sys
import heapq
n, q = map(int, input().split())
a = list(map(int, input().split()))
ival = {}
in_heap = set()
heap = [0]
there_q = False
# 各値ごとの区間を求める
for i, x in enumerate(a):
if x == q:
there_q = True
if x == 0:
continue
if x not in ival:
ival[x] = [i, i]
ival[x][1] = i
events = [[] for i in range(n)]
for k, [l, r] in ival.items():
events[l].append(-k)
events[r].append(k)
for i in range(n):
for ev in events[i]:
in_heap.add(ev)
if ev < 0:
heapq.heappush(heap, ev)
while -heap[0] in in_heap:
heapq.heappop(heap)
if a[i] != 0 and -heap[0] > a[i]:
print("NO")
sys.exit()
for i in range(n):
if a[i] == 0:
if not there_q:
a[i] = q
there_q = True
elif i > 0:
a[i] = a[i - 1]
for i in range(n - 2, -1, -1):
if a[i] == 0:
a[i] = a[i + 1]
if not there_q:
print("NO")
else:
print("YES")
print(*a)
```
:::
:::spoiler **◎実装例(C++)**
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
bool there_q = false;
map<int, pair<int, int>> ival;
set<int> st({0});
for (int i = 0; i < n; i++) {
if (a[i] == 0) continue;
if (a[i] == q) there_q = true;
if (ival.count(a[i]) == 0)
ival[a[i]] = make_pair(i, i);
ival[a[i]].second = i;
}
vector<vector<int>> events(n);
for (auto &[k, iv] : ival) {
events[iv.first].push_back(-k);
events[iv.second].push_back(k);
}
for (int i = 0; i < n; i++) {
for (auto &ev : events[i]) {
if (ev < 0)
st.insert(-ev);
else
st.erase(ev);
}
if (a[i] != 0 && *prev(st.end()) > a[i]) {
cout << "NO" << endl;
return 0;
}
}
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
if (!there_q) {
a[i] = q;
there_q = true;
} else if (i > 0) {
a[i] = a[i - 1];
}
}
}
for (int i = n - 2; i >= 0; i--) {
if (a[i] == 0) {
a[i] = a[i + 1];
}
}
if (!there_q) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
for (int i = 0; i < n; i++) cout << a[i] << " ";
cout << endl;
}
}
```
:::
### ◎E. Down or Right
:::spoiler **◎ヒント1**
高々 $2n-2$ 回の質問で解けます。
:::
:::spoiler **◎ヒント2**
「左上・右下のマスの内どちらかをクエリに必ず含めなくてはならない」という条件があっても解けます。
:::
:::spoiler **◎ヒント3**
左上と右下からの距離が等しいマスを、「対角線上のマス」と呼ぶことにします。
ある対角線上のマス $(x_a,y_a)$ であり、$(1,1) \rightarrow (x_a,y_a) \rightarrow (n,n)$ の順の移動経路が存在するマスが少なくとも1つは存在します。
$(x_a,y_a)$ を一つ求め、同時に $(1,1) \rightarrow (x_a,y_a)$ のパスを見つける方法を考えましょう。
:::
:::spoiler **◎ヒント4**
ある対角線上のマス $(x_b,y_b)$ であり、$(1,1) \rightarrow (x_b,y_b) \rightarrow (n,n)$ の順の移動経路が存在するマスが少なくとも1つは存在します。
$(x_b,y_b)$ を一つ求め、同時に $(x_b,y_b) \rightarrow (n,n)$ を見つける方法を考えましょう。
:::
:::spoiler **◎ヒント5**
$(x_a,y_a) = (x_b,y_b)$ とする方法を考えましょう。
:::
:::spoiler **◎解説**
まず、ヒント3の実装を考えます。ヒント3は、以下のようにすれば実現できます。
- まず、$p = (1,1)$ とします。その後、以下の操作を、$p$ が対角線上のマスになるまで繰り返します。
- $p$ から 下に1回移動したマスを $p_d$ 、右に1回移動したマスを $p_r$ とします。$p_d$ が存在し、なおかつ $p_d \rightarrow (n,n)$ を質問したときの返答が `YES` の場合は $p \leftarrow p_d$ と更新します。そうでないとき、$p \leftarrow p_r$ とします。
上の操作を繰り返すとき、必ず $p$ は $(1,1) \rightarrow p \rightarrow (n,n)$ の経路が存在するマスとなるので、$p$ の変化を記録しておくことで、ヒント3が実現できます。
次に、ヒント4,5を考えます。ヒント3の実装とほぼ同じことをすれば、ヒント4は実現できるのですが、最終的に見つけた対角線上のマス $(x_b,y_b)$ が $(x_a,y_a)$ と等しくなければいけません。
この問題を解決するため、ヒント3を上記のアルゴリズムにより実現することで導出できる $(x_a,y_a)$ の性質を考えてみます。結論から言うと、この $(x_a,y_a)$ は、**$(1,1) \rightarrow (x_a,y_a) \rightarrow (n,n)$ の順の移動経路が存在する対角線上のマスのうち、最も左下のマス** になっています。証明は省略しますが、下と右の両方に進める時に下優先で進んでいることから、直感的にも正しいことは容易に分かると思います。
このことから、ヒント4を実装する際にも、**$(1,1) \rightarrow (x_b,y_b) \rightarrow (n,n)$ の順の移動経路が存在する対角線上のマスのうち、最も左下のマス** までの経路を求めてあげれば良いことが分かります。具体的には、以下のようにします。
- まず、$q = (n,n)$ とします。その後、以下の操作を、$q$ が対角線上のマスになるまで繰り返します。
- $q$ から 左に1回移動したマスを $p_l$ 、上に1回移動したマスを $p_u$ とします。$p_l$ が存在し、なおかつ $(1,1) \rightarrow p_l$ を質問したときの返答が `YES` の場合は $p \leftarrow p_l$ とします。そうでないとき、$p \leftarrow p_u$ とします。
後は、$q$ の変化を**逆順に**並べてあげれば、$(x_b,y_b) = (x_a,y_a)$ であるようなマス $(x_b,y_b)$ と、 $(x_b,y_b)$ から $(n,n)$ までの経路が求まります。
クエリの回数は、最大でも $2n-2$ 回です。
:::
:::spoiler **◎実装例(python)**
```python=
import sys
def query(r1,c1,r2,c2):
print ("?",r1,c1,r2,c2,flush=True)
cat = input()
if cat == "YES":
return True
elif cat == "NO":
return False
else:
sys.exit()
n = int(input())
x,y = 1,1
ans1 = []
while x+y != n+1:
if (x+1 <= n and query(x+1,y,n,n)):
x += 1
ans1.append("D")
else:
y += 1
ans1.append("R")
x,y = n,n
ans2 = []
while x+y != n+1:
if (y-1 >= 1 and query(1,1,x,y-1)):
y -= 1
ans2.append("R")
else:
x -= 1
ans2.append("D")
ans2.reverse()
ans = ans1 + ans2
print ("!","".join(ans),flush=True)
```
:::
Sign in with Wallet
Connect another wallet