5/10 競プロ講習会Cクラスバチャ解説

# 10/18 競プロ講習会バチャヒント/解説 ## ヒント集 --- ### ABC134-A　Dodecagon Aクラスの人に解いてほしい問題です。整数の入力・四則演算・出力ができれば解くことができます。鹿本の47P〜を参考にしましょう。 pythonを使用して入力を受け取る際、整数一つを受けとるのならば ```python= r = input() r = int(r) ``` と書くことができます。(鹿本49Pの例は、２つ整数を受け取るのでsplitが必要な訳です) --- ### ABC195-A　Health M Death Aクラスの人に解いてほしい問題です。鹿本の56Pに書いてある、例題3を参考にしましょう。 --- ### ABC214-B　How Many? Bクラスの人に解いてほしい問題です。鹿本3-6節の内容が分かっていれば解けます。数学的に考えるのではなく、コンピュータの計算性能をフルに活用して解く方法を考えましょう。 --- ### ABC268-B　Prefix? Bクラスの人に解いてほしい問題です。鹿本3-5節の内容がわかっていれば解けます。検索などをフル活用しましょう。 --- ### ABC116-C　Grand Garden 以降はCクラスの人向け問題です。茶diffです。 :::spoiler **ヒント1** 最適性の証明は難しいです。サンプルをよく見て勘で方針を見つけるのもいいと思います。 ::: :::spoiler **ヒント2** 制約は小さいので、最適方針がわからなくても動的計画法で解けます。 ::: --- ### AGC033-B　LRUD Game 結構難しい。水diff :::spoiler **ヒント1** 縦と横は独立に考えられるので、1次元の問題が解ければOKです。 ::: :::spoiler **ヒント2** 後ろから考えましょう。 ::: --- ### AGC025-B　RGB Coloring 今出たら水diffくらいかも・・・ :::spoiler **ヒント1** mod 数え上げ初心者の人は、以下の記事を見ましょう。 https://drken1215.hatenablog.com/entry/2018/06/08/210000 https://algo-logic.info/combination/ ::: :::spoiler **ヒント2** 色を変えると分かりやすくなります。緑→ムラサキと読み替えてみましょう ::: --- ### ARC122-D　XOR Game diffは高いですが、典型問題です。 :::spoiler **ヒント1** スコアの値が $V$ 以下になるか？という問題を考えましょう。Bob の視点に立ったほうがわかりやすいです。 ::: :::spoiler **ヒント2** ヒント1に関する必要十分条件が出たら、具体的にスコア $V$ の値を求めましょう。上位bitから決めていく方針は典型です。 ::: :::spoiler **ヒント3** 最後の1手はデータ構造を用います。Library Checkerの「Set Xor-Min」なども参照してください。 https://judge.yosupo.jp/problem/set_xor_min ::: --- ### ARC121-D　1 or 2 diffは高いですが、典型問題です。その2 :::spoiler **ヒント1** 「1つまたは2つ」という条件を統一的に扱えないか考えてみましょう。 ::: :::spoiler **ヒント2** 飴を1つだけ選ぶということを、おいしさ0の飴とともに2つ選ぶと解釈しても変わりません。 ::: :::spoiler **ヒント3** 飴はおいしさの昇順に並んでいるとしてよいです。最大値と最小値の差を最小化するには、どのように飴を分けるとよいでしょう？直感的に考えたあと、証明もできると素晴らしいです（ACには必要ありませんが）。 ::: --- ### AGC006-F　Blackout AGC-Fなのでヤバそうですが、普通に解ける問題なので是非挑戦！！ AGC-BやARC-C においてあっても全く問題無さそう。 :::spoiler **ヒント1** グリッドの問題だと思いこんでいると解けません。 ::: :::spoiler **ヒント2** コーナーケースに注意！！ ::: --- --- --- ## 解説 (ネタバレに注意！！) --- ### ABC134-A　Dodecagon ::: spoiler **クリックで展開** 入力受け取り、計算結果を出力する問題です。 pythonの実装例 ```python= r = input() #入力を文字列型として受け取る r = int(r) #受け取った値を整数型にする ans = 3*r*r #答えを計算 print (ans) #計算結果を出力 ``` C++の実装例 ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ int r; //入力を受け取るための変数rを宣言 cin >> r; //入力を受け取る int ans = 3 * r * r; //答えを計算 cout << ans << endl; //計算結果を出力 } ``` ::: --- ### ABC195-A　Health M Death ::: spoiler **クリックで展開** $M$ の倍数か？ ↔ $M$で割ったあまりが0か？を利用します。 pythonの実装例 ```python= M,H = input().split() #入力を文字列型として受け取る M = int(M) #受け取った値を整数型にする H = int(H) #受け取った値を整数型にする if (H % M == 0): #HがMで割り切れたら… print ("Yes") #Yesを出力 else: #そうではなかったら print ("No") #Noを出力 ``` C++の実装例 ```cpp= #include <bits/stdc++.h> using namespace std; int main(){ int M,H; //入力を受け取るための変数を宣言 cin >> M >> H; //入力を受け取る if (H % M == 0){ //HがMで割り切れたら… cout << "Yes" << endl; //Yesを出力 }else{ //そうではなかったら cout << "No" << endl; //Noを出力 } } ``` ::: --- ### ABC214-B　How Many? ::: spoiler **クリックで展開** $a,b,c$ を3重ループで全探索することで解けます。ループの回数は概ね $100^3 = 10^6$ 回なので、制限時間の2sに余裕で間に合います。 (概ね10^9オーダーが限界と覚えておいてください。) pythonの実装例 https://atcoder.jp/contests/abc214/submissions/25020154 C++の実装例 https://atcoder.jp/contests/abc214/submissions/29607169 ::: --- ### ABC268-B　Prefix? ::: spoiler **クリックで展開** forループで前の文字からチェックしていけば良いです。文字列操作をうまく使っても解けます。 pythonの実装例 https://atcoder.jp/contests/abc268/submissions/34726780 C++の例 (公式) https://atcoder.jp/contests/abc268/editorial/4780 C++の例（C\+\+20から実装されている「std::basic_string::starts_with」を用いた実装） ```cpp= #include <iostream> int main() { std::string s, t; std::cin >> s >> t; if (t.starts_with(s)) { std::cout << "Yes" << std::endl; } else { std::cout << "No" << std::endl; } } ``` ::: --- ### ABC116-C　Grand Garden ::: spoiler **クリックで展開** 左端から考えていきましょう。左端は $h_1$ 回操作されるので、$l=1$ の操作は $h_1$ 回です。左から2番目は、なるべく左端と一緒に操作するのが最適です。なぜなら、左端だけに対して行う操作、$l=2$の操作が両方ある場合、それらを合わせることで1回操作を減らせるからです。よって、$l=2$ の操作は $h_1 \le h_2$ のときは $h_2-h_1$ 回、そうでなければ $0$ 回です。これは、3項目以降にも同じことが言えるので、結論として答えは $\sum_{i=1}^{n-1} \mathrm{min}(h_{i+1}-h_i,0)$ です。 ::: --- ### AGC033-B　LRUD Game ::: spoiler **クリックで展開** 縦と横に分解して考えることができます。縦のゲーム・横のゲームの内、片方でも高橋くんが勝てるのならば高橋くんの勝ちです。一次元に分解すると、高橋くん・青木くんの内片方が連続で操作する場合が発生することに注意しましょう。 1次元版の問題を、後ろから考えていきます。 $[l_i,r_i]$ = $i$ ターンの操作が始まる前に、この区間にコマが置いてあれば青木くんが勝てる区間とします。 $[l_i,r_i]$ から、$[l_{i-1},r_{i-1}]$ を求めます。 $i-1$ターン目が青木くんの場合、$[l_i,r_i]$に逆操作した場合としない場合の和集合が $[l_{i-1},r_{i-1}]$ となります。言い換えると、「操作するかしないかを適切に選んだ時、$[l_i,r_i]$に入れることができる区間」を求めればokです。一方で、$i-1$ターン目が高橋くんの場合、$[l_i,r_i]$に逆操作した場合としない場合の積集合が $[l_{i-1},r_{i-1}]$ となります。言い換えると、「操作するかしないか、どちらを選んだとしても$[l_i,r_i]$に入ってしまう区間」を求めればokです。 ::: --- ### AGC025-B　RGB Coloring ::: spoiler **クリックで展開** 緑→ムラサキと言い換えると、以下のように言い換えられます。「まず、各ブロックに赤い絵の具を塗るか決め、塗っていく。$塗った個数 \times A$点を得る」「次に、各ブロックに青い絵の具を塗るか決め、塗っていく。この時、既に赤く塗ったブロックに塗ると、ムラサキ色に見えるようになる。$塗った個数 \times B$点を得る」ムラサキ色のブロックは合計で $A+B$ 点になっているので、この言い換えは元の問題と同値であることが分かります。赤と青を独立に考えられるようになったので、赤の個数を全探索すると、自動的に青の個数も決まり、後は単純な二項係数の積と和で求められます。この辺は公式解説をチェックしましょう。 ::: --- ### ARC122-D　XOR Game ::: spoiler **クリックで展開** スコアについて、以下のことが成り立ちます。証明はほぼ明らかです。「最終的なスコアが $V$ 以下である $\Leftrightarrow$ $2N$ 個の整数を整数のペア $N$ 個に分ける方法であって、どのペアの XOR も $V$ 以下である。」したがって、以下の問題を解けば良いことになります。「$2N$ 個の整数を整数のペア $N$ 個に分ける。ペアになった整数の XOR の最大値を最小化せよ。」この問題の答えを上位bitから決めていくことにします。二分探索と思ってもよいです。（この手の問題で答えを上位bitから決めていくのは典型です。）現在 $L$ bit目を決めているとします。$L$ bit目が $0$ である整数の部分集合を $A$、$1$ である整数の部分集合を $B$ とします。 $|A|, |B|$ がともに偶数ならば、$A$ の要素は $A$ の要素と、$B$ の要素は $B$ の要素と組ませることによって $L$ bit目を $0$ にすることができます。このとき $A$ と $B$ それぞれについて $L-1$ bit目の答えを計算し、そのうち大きい方を答えとすればよいです。そうでないとき、$A$ の要素と $B$ の要素からなるペアを少なくとも $1$ つ作らなくてはなりません。$L$ bit目は必ず $1$ となってしまいますが、その上でそのペアの XOR をできる限り小さくしたいです。つまり、次のような問題が解ければ良いです。「各 $a \in A$ について、$\displaystyle \min_{b\in B} a\oplus b$ を求めよ」これは Binary Trie と呼ばれるデータ構造を用いて高速に解くことができます。 ::: --- ### ARC121-D　1 or 2 ::: spoiler **クリックで展開** まず「1つか2つの飴を選ぶ」ではなく「2つの飴を選ぶ」場合の問題を解いてみます。（飴が偶数個あることは仮定します。）この場合、小さい方から $i$ 番目の飴と、大きい方から $i$ 番目の飴を選ぶことが最適です。なぜなら、$a\leq b\leq c\leq d$ に対して次の不等式が成り立つからです。 - $\max(a + d, b + c) \leq \max(a + c, b + d)$ （交差を解消したほうが最大値が小さい） - $\min(a + d, b + c) \geq \min(a + c, b + d)$ （交差を解消したほうが最小値が大きい）したがって、この場合は $\mathrm{O}(N\log N)$ 時間で問題を解くことができます。（ソートの計算量）元の問題に戻ります。実は次のような言い換えをすることで、元の問題を上の問題に帰着することができます。「飴を1つ選ぶということは、その飴とおいしさ0の飴2つを選ぶことと同じである。」したがって、おいしさ0の飴をいくつ追加するかを全探索することによってこの問題を解くことができます。時間計算量は $\mathrm{O}(N^2\log N)$ や $\mathrm{O}(N^2)$ になります。 ::: --- ### AGC006-F　Blackout 公式解説を見てね貴重な自力で解けるAGC-F なので粘ってみてもいいです https://img.atcoder.jp/data/agc/006/editorial.pdf