# 競プロ講習会2022 前期2回　Web資料 ## 第2回の参加方法について 今回からは、好きな時間に問題を解いておくことができるようにします。 講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。 まず、Codeforcesにログインします。 その後、K-LMSに公開したコンテストリンクを開きます。 KeioAICKyoproCourseContest #2 に、**Virtual participation**します。 (※この機能は、好きな時間を選んでコンテストに参加できる機能です) 開始したい時間を入力し、Registar for virtual participationを押します。 指定した時間になったらコンテストが始まるので、問題を解きます。 コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。 また、参加中であってもweb資料のヒント・解説は参照してかまいません。 Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。 #### 問題セット https://codeforces.com/gym/380178 #### 公式解説 ##### A問題 https://codeforces.com/blog/entry/102101 ##### B～H問題 https://codeforces.com/blog/entry/66307 ## 問題訳 ### A. Division? TL:1s ML:256MB #### 問題 Codeforcesは、参加者をレーティングによって4つのdivisionに分けています。 ・Division 1 は、 $1900 \le \rm{rating}$ ・Division 2 は、 $1600 \le \rm{rating} \le 1899$ ・Division 3 は、 $1400 \le \rm{rating} \le 1599$ ・Division 4 は、 $\rm{rating} \le 1399$ レーティングが与えられるので、そのレーティングの参加者がどのDivisionにあたるか答えてください。 #### 入力 1行目に、テストケースの数 $t (1 \le t \le 10^4)$ が与えられます。 続く $t$ 行に、$\rm{rating} (-5000 \le \rm{rating} \le 5000)$ が与えられます。 #### 出力 各行に一つのテストケースに対する答えを出力し、改行してください。 各テストケースの答えは、"Division $X$" という文字列となります。$X$には対応するDivisionの番号を入れてください。 #### 入出力例 ##### 入力例1 ``` 7 -789 1299 1300 1399 1400 1679 2300 ``` ##### 出力例1 ``` Division 4 Division 4 Division 4 Division 4 Division 3 Division 2 Division 1 ``` ### B. Diverse Strings TL:1s ML:256MB #### 問題 文字列がアルファベット順で連続した文字しか含まず、同じ文字が2回以上出現しないときに、その文字列を `diverse` であると呼びます。 例えば、`fced`, `xyz`, `r` は同じ文字が2回以上現れず、`cdef`, `xyz`, `r` とアルファベット順で連続したものしか現れないので `diverse` です。 逆に、`az`, `aa`, `bad`, `babc` は `diverse` ではありません。`a` と `z` はアルファベット順で連続していないことに注意してください。 いくつかの文字列が与えられるので、それぞれに対して `diverse` であれば `Yes`、そうでなければ `No` を出力してください。 #### 入力 一行目に処理する必要のある文字列の個数として整数 $n\, (1 \leq n \leq 100)$ が与えられます。 続く $n$ 行には $1$ 行につき $1$ つの英小文字からなる文字列が含まれていて、その長さは $1$ 文字以上 $100$ 文字以下です。 #### 出力 入力で与えられた文字列 $1$ つにつき $1$ 行、合わせて $n$ 行出力しなさい。 各行は、対応する文字列が `diverse` なら `Yes`、そうでなければ `No` を出力しなさい。大文字と小文字の区別はないので `yeS`, `no`, `yES` のように出力してもよい。 #### 入出力例 ##### 入力例1 ``` 8 fced xyz r dabcef az aa bad babc ``` ##### 出力例1 ``` Yes Yes Yes Yes No No No No ``` ### C. Parity Alternated Deletions TL:2s ML:256MB #### 問題 Polycarpは, 長さ $n$ の整数列 $a$ を持っています. 彼は, この列でゲームをします. ゲームは複数回の操作からなります. 最初の操作では, 彼は任意の要素を $1$ つ選び, 削除します(操作後, 列の長さは $n-1$ になります). それ以降は, 以下の制約が付いた操作を行います. ・直前に削除した要素と偶奇が異なる要素を $1$ つ選び, 削除する. PolyCarp が操作できなくなったら, そこでゲームは終わりです. PolyCarpは, 削除されずに残った要素の総和を最小化したいです. 適切に操作したとき, 達成できる最小値を求めなさい. なお, 列全体が削除されてしまった場合, 残った要素の総和は0とします. #### 入力 最初の行には, 1つの整数 $n(1 \le n \le 2000)$ が与えられる. 2行目には, $n$ 個の整数 $a_1,a_2,...a_n (0 \le a_i \le 10^6)$ が与えられる. #### 出力 達成できる最小値を $1$ 行に出力してください. その後, 改行してください. #### 入出力例 ##### 入力例1 ``` 5 1 5 7 8 2 ``` ##### 出力例1 ``` 0 ``` ##### 入力例2 ``` 6 5 1 2 4 6 3 ``` ##### 出力例2 ``` 0 ``` ##### 入力例3 ``` 2 1000000 1000000 ``` ##### 出力例3 ``` 1000000 ``` ### D. Two Shuffled Sequences TL:2s ML:256MB #### 問題 狭義単調増加な数列と狭義単調減少な数列の2つが最初に存在します。 狭義単調増加数列とは $[x_1 < x_2 < \cdots < x_k]$ となっている数列で、狭義単調減少数列は $[y_1 > y_2 > \cdots > y_l]$ のようになっている数列です。空文字列や1つしか要素が存在しない数列は狭義単調増加かつ狭義単調減少であることに注意してください。 例えば、$[1, 4, 5]$ は狭義単調増加ですが $[1, 4, 4]$ は狭義単調増加ではありません。 この2つの数列はある1つの数列 $a$ に合体し、シャッフルされました。例えば、単調増加数列 $[1, 3, 4]$ と単調減少数列 $[10, 4, 2]$ から得られる $a$ としては $[1, 2, 3, 4, 4, 10]$ や $[4, 2, 1, 10, 4, 3]$ がありえます。 この $a$ が入力として与えられるので、最初の2つの数列としてありえるもののうちどれか1組を見つけることがあなたの課題です。1つは狭義単調増加で、もう1つは狭義単調減少である必要があります。 空の数列や、1つしか要素のない数列も許されることに注意してください。 もしも入力された $a$ が得られるような2つの数列が存在しないときには `NO` と出力してください。 #### 入力 1行目には、数列 $a$ の要素数 $n\,(1 \leq n \leq 2\cdot 10^5)$ が与えられます。 2行目には $n$ 個の整数 $a_1, a_2, \ldots, a_n \, (0 \leq a_i \leq 2 \cdot 10^5)$ が与えられます。$a_i$ は数列 $a$ の $i$ 番目の要素です。 #### 出力 もしも入力に矛盾があり、最初の2つの数列としてありえるものが存在しないときには `NO` と出力してください。 そうでなければ最初の行に `YES` と出力し、2つの適切な数列を出力してください。空文字列や1つしか要素のない数列でも問題ありません。 2つの数列は次のような形式で出力してください。 2行目には $n_i$ として、狭義単調増加な数列の要素数を出力してください。 $n_i$ は $0$ でもよいです。この場合、単調増加数列は空になります。 3行目には、$n_i$ 個の整数 $inc_1, inc_2, \ldots, inc_{n_i}$ を昇順に出力してください$(inc_1 < inc_2 < \cdots < inc_{n_i})$ 。$n_i = 0$ の場合にはこの行は空にしたまま改行を行ってください。 4行目には $n_d$ として、狭義単調減少な数列の要素数を出力してください。$n_d$ は $0$ でもよいです。 5行目には $n_d$ 個の整数 $dec_1, dec_2, \ldots, dec_{n_d}$ を降順に出力してください $(dec_1 > dec_2 > \cdots > dec_{n_d})$。$n_d = 0$ の場合はこの行を空にしたまま改行を行ってください。 $n_i + n_d = n$ であって、2つの出力された数列を並び替えると与えられた数列 $a$ になっている必要があります。 #### 入出力例 ##### 入力例1 ``` 7 7 2 7 3 3 1 4 ``` ##### 出力例1 ``` YES 2 3 7 5 7 4 3 2 1 ``` ##### 入力例2 ``` 5 4 3 1 5 3 ``` ##### 出力例2 ``` YES 1 3 4 5 4 3 1 ``` ##### 入力例3 ``` 5 1 1 2 1 2 ``` ##### 出力例3 ``` NO ``` ##### 入力例4 ``` 5 0 1 2 3 4 ``` ##### 出力例4 ``` YES 0 5 4 3 2 1 0 ``` ### E. Equalize Them All TL:2s ML:256MB #### 問題 あなたは, 長さ $n$ の整数列 $a$ をもらいました. あなたは, 以下の2種類の操作を好きな順で, 好きな回数だけ行うことができます. 1. $|i-j| = 1$ を満たす 添字のペア $(i,j)$ を選び, $a_i$ を $a_i+|a_i-a_j|$ で置き換える. 2. $|i-j| = 1$ を満たす 添字のペア $(i,j)$ を選び, $a_i$ を $a_i-|a_i-a_j|$ で置き換える. なお, $|x|$ は $x$ の絶対値を示しています. あなたは, 数列の要素を全て同じにしなくてはなりません. 必要な操作回数の最小値を求め, それを達成する具体的な操作を$1$つ構成してください. ==なお, 構成した操作において数列内の要素の絶対値が$10^{18}$を超えないようにしてください. 本問題の制約下では以上の条件を満たす有限回の操作が必ず存在することが証明できます.== ​ #### 入力 最初の行には, 1つの整数 $n(1 \le n \le 2\times10^5)$ が与えられる. 2行目には, $n$ 個の整数 $a_1,a_2,...a_n (0 \le a_i \le 2\times10^5)$ が与えられる. #### 出力 $1$ 行目には, 数列の要素をすべて等しくするのに必要な操作回数の最小値 $k$ を出力してください. 続く $k$ 行には, 構成した操作列の操作を順番に出力してください. 具体的には, $p+1$行目に $t_p\ i_p\ j_p$をこの順番で空白区切りで出力してください. $t_p,i_p,j_p$ は, $p$ 回目の操作を表す $3$ つの整数です. $t_p$ は, 操作$1$,操作$2$ のどちらを行ったかをそれぞれ$1,2$で表します. $i_p,j_p$ は,それぞれの操作において選択した添字のペアです. $|i_p-j_p| = 1\ (1 \le i_p,j_p \le n)$ を満たしている必要があります. ​ 答えが複数考えられる場合, どれを出力しても構いません. #### 入出力例 ##### 入力例1 ``` 5 2 4 6 6 6 ``` ##### 出力例1 ``` 2 1 2 3 1 1 2 ``` ##### 入力例2 ``` 3 2 8 10 ``` ##### 出力例2 ``` 2 2 2 1 2 3 2 ``` ##### 入力例3 ``` 4 1 1 1 1 ``` ##### 出力例3 ``` 0 ``` ### F. Median String TL:2s ML:256MB #### 問題 $k$ 個の英小文字からなる文字列 $s$ と $t$ が与えられます。$s$ は辞書順で $t$ よりも小さいです。 ちょうど $k$ 文字の英小文字からなる文字列で、辞書順で $s$ と $t$ の間 ($s$ と $t$ を含む) になるものすべてを辞書順に並べたリストを考えます。 例えば、$k = 2$, `s = "az"`, `t = "bf"` とします。このとき、リストは `["az", "ba", "bb", "bc", "bd", "be", "bf"]` となります。 あなたは、リストの中心にある文字列を出力してください。先程の例では `"bc"` になります。 正確には、リストに含まれる文字列が $n$ 個であれば $\lceil \frac{n}{2} \rceil$ 番目の文字列を出力してください。 ==リストに含まれる文字列の数は奇数になることが保証されます。== #### 入力 1行目に $k\, (1 \leq k \leq 2 \cdot 10^5)$ として 文字列の長さが与えられます。 2行目と3行目にそれぞれ $k$ 文字の英小文字からなる文字列 $s$, $t$ が与えられます。 $s$ は辞書順で $t$ よりも小さいことが保証されます。 #### 出力 次の条件を満たす、$k$ 個の英小文字からなる文字列を1つ出力してください。 - ちょうど $k$ 文字の文字列であって、辞書順で $s$ 以上 $t$ 以下のものすべて並べたリストの中心になる文字列 #### 入出力例 ##### 入力例1 ``` 2 az bf ``` ##### 出力例1 ``` bc ``` ##### 入力例2 ``` 5 afogk asdji ``` ##### 出力例2 ``` alvuw ``` ##### 入力例3 ``` 6 nijfvj tvqhwp ``` ##### 出力例3 ``` qoztvz ``` ### G. Graph Without Long Direted Paths TL:2s ML:256MB #### 問題 あなたは, $n$ 頂点 $m$ 辺の連結な無向グラフをもらいました. このグラフには, 自己ループと多重辺が含まれないことが保障されます. あなたは, このグラフの各辺に向きを付けて有向グラフにしたいです. ただし,有向グラフにした時に長さ2以上のパスが存在してはいけません. そのような辺の向きの付け方が存在するか判定し, 存在する場合は $1$ つ構成してください. #### 入力 $1$ 行目には, $2$ つの整数 $n\ m(2 \le n \le 2\times10^5 , n-1 \le m \le 2\times10^5)$ がこの順番で与えられます. 続く $m$ 行にグラフの辺の情報が与えられます. $i+1$ 行目には2つの整数 $u_i\ v_i(1 \le u_i,v_i \le n,u_i \neq v_i)$ が与えられます. $u_i\ v_i$ は, 辺 $i$ が 頂点$u_i$ と $v_i$ を結んでいることを示しています. 多重辺は存在せず, グラフ全体が連結であることが保証されます. #### 出力 もし, 問題文の条件を満たす辺の向きの付け方が存在しないならば, `NO`と出力して下さい. そうでなければ, $1$ 行目に`YES`と出力してください. その後, $2$行目に長さ$m$のバイナリ文字列$s$を出力してください. 辺$i$に $u_i\rightarrow v_i$ の向きを付けた場合, $s$ の $i$ 文字目は $0$ , $u_i\leftarrow v_i$ の向きを付けた場合, $s$ の $i$ 文字目は $1$ にしてください. 答えが複数ある場合, どれを出力しても構いません. #### 入出力例 ##### 入力例1 ``` 6 5 1 5 2 1 1 4 3 1 6 1 ``` ##### 出力例1 ``` YES 10100 ``` 入力例1の無向グラフ ![](https://i.imgur.com/TLCi8dt.png) 出力例1の有向グラフ ![](https://i.imgur.com/N0SB78t.png) ### H. Two Merged Sequences TL:2s ML:256MB #### 問題 狭義単調増加数列と狭義単調減少数列の2つが最初に存在します。 狭義単調増加数列とは $[x_1 < x_2 < \cdots < x_k]$ となっている数列で、狭義単調減少数列は $[y_1 > y_2 > \cdots > y_l]$ のようになっている数列です。空文字列や1つしか要素が存在しない数列は狭義単調増加かつ狭義単調減少であることに注意してください。 単調増加数列の要素を単調減少数列の要素の間に挿入していきます(このとき、単調減少数列の最初の要素よりも前と、最後の要素よりも後にも挿入できます)。**このとき、挿入した後に順番が変わってはいけません。** 例えば、$[1, 3, 4]$ と $[10, 4, 2]$ から $[10, 1, 3, 4, 2, 4]$ や $[1, 3, 4, 10, 4, 2]$ を作ることができます。しかし、$[1, 10, 4, 4, 3, 2]$ は $[1, 3, 4]$ から挿入した数値の順番が $[1, 4, 3]$ となり変わってしまっているため作ることができません。 挿入することで得られた数列 $a$ が入力として与えられるので、最初の2つの数列として適切な任意の組を1つ探してください。1つの数列は狭義単調増加で、もう一方は狭義単調減少である必要があります。空の数列や1つしか要素のない数列は狭義単調増加かつ狭義単調減少な数列と考えられます。 もしも入力に矛盾があり、どのような2つの狭義単調増加数列と狭義単調減少数列からも数列 $a$ が作れないときには `NO` と出力してください。 #### 入力 1行目には、$n\, (1 \leq n \leq 2 \cdot 10^5)$ として数列 $a$ の要素数が与えられます。 2行目には、$n$ 個の整数 $a_1, a_2, \ldots, a_n (0 \leq a_i \leq 2 \cdot 10^5)$ が与えられます。 $a_i$ は数列 $a$ の $i$ 番目の要素です。 #### 出力 もしも入力に矛盾があり、最初の2つの数列の組としてあり得るものが存在しないときには `NO` と出力してください。 そうでなければ、最初の行に `YES` と出力してください。 2行目には $n$ 個の整数 $res_1, res_2, \ldots, res_n$ を出力してください。$res_i$ は $0$ もしくは $1$ であって、$a$ の $i$ 番目の要素が狭義単調増加数列に含まれる場合には $0$、狭義単調減少数列に含まれる場合には $1$ になります。 #### 入出力例 ##### 入力例1 ``` 9 5 1 3 6 8 2 9 0 10 ``` ##### 出力例1 ``` YES 1 0 0 0 0 1 0 1 0 ``` ##### 入力例2 ``` 5 1 2 4 0 2 ``` ##### 出力例2 ``` NO ``` ## ヒント ### ヒントに関しての諸注意 各問題のポイントをヒントという形で紹介しています。 コンテスト中であっても、詰まってしまったらぜひご確認ください。 コンテスト後に復習する際に活用していただいてもいいです。 序盤の問題に関しては一部実装をpython,C++で紹介しています. ただし詰まりそうな部分に絞って書いてあるので, 繋ぎ合わせれば正解になるわけではありません。ご注意ください. pythonに関して, Codeforcesでは以下の5つの実行環境を利用できます. ・python 2.7.18 ・python 3.8.10 ・PyPy 2.7.13 (7.3.0) ・PyPy 3.6.9 (7.3.0) ・PyPy 3.7.10 (7.3.5, 64bit) ヒントは、PyPy3.6.9 (7.3.0) もしくは PyPy 3.7.10 (7.3.5, 64bit) を利用することを前提に書いています. なお, Codeforcesのpython環境では, ASCIIに含まれない文字を含んだコードを提出するとエラーになることがありますので注意してください. C++に関しては、以下のヘッダが記述されていることを前提にしています. ご注意ください. ```cpp= #include <bits/stdc++.h> using namespace std; ``` ### A. Division? :::spoiler **やるべきこと** 問題文の訳と入出力例を見て何をするコードを書けばよいのか、まず把握しましょう。 問題で問われている内容は、いわゆる条件分岐です。 条件分岐とは、変数の状態によって実行する命令を変えることを指します。 多くの言語では、この機能は if文 として実装されています。 「if文 <使用している言語名>」などで検索しましょう。 python, C++に関しては以下の実装のステップのところで必要な文法を個別に解説しています。 ::: #### 実装のステップ（C++/python) :::spoiler **入力の受け取り** この問題では、テストケースの個数 $t$ と 各テストケースの $\rm{rating}$ を受け取る必要があります。 1行に入力された1つの整数 $t$ を受け取る方法をpython, C++で以下に掲載します。 $\rm{rating}$ に関しても、同様に受け取ることができます。 ```python= # python での実装 # input() は標準入力から1行分の入力を文字列として受け取り、返す関数 # int() は、引数(括弧内に入れた要素) を整数型に変換し、返す関数 # 以下の行の実行後、標準入力から受け取った整数が整数型としてtに入ることになる。 t = int(input()) ``` ```cpp= #include <bits/stdc++.h> using namespace std; int main() { // C++での実装 // int型変数tの宣言。 int t; // 標準入力から整数を一つ受け取り、tに代入する。 cin >> t; } ``` ::: ::: spoiler **複数テストケースへの対応** 本問題では、複数個のテストケースに答える必要があります。 これは、以下のような構造のコードを書くことで解決することができます。 1. 標準入力からテストケースの個数 $t$ を受け取る。 2. 変数 $i$ を用意し、$i = 0$ とする。(この変数をループカウンタと呼びます) 3. $i$ が $t$ 以上なら、プログラムを終了する。 4. 標準入力からテストケースを1つ分受け取り、問題の答えを標準出力に出力する。 5. $i$ を1増やす 6. 3.に戻る これと同等の機能を簡潔に実装できるようにしたのが、for文です。 python,C++ 共に用意されているので、利用しましょう。 for文に関しては、ちゃんとした知識を持っていた方が良いのでしっかり検索しましょう。 以下に、$i$ をループカウンタとして、 $t$ 回ループするコードを掲載しておきます。 ```python= # python の実装例 # ここで、あらかじめtは受け取っておく(省略) for i in range(t): #ここにt回繰り返したい処理を書く #複数行にわたって書いてもいい #インデント(左の空白)がある限り、ループの効果範囲内になる #ここにはループから抜けた後の処理を書く ``` ```cpp= #include <bits/stdc++.h> using namespace std; int main() { // C++の実装例 //ここで、あらかじめtは受け取っておく(省略) for (int i=0 ; i<t ; ++i){ //ここにt回繰り返したい処理を書く //複数行にわたって書いてもいい //ブロック(括弧)を閉じない限り、ループの効果範囲内になる } // ここにはループから抜けた後の処理を書く } ``` ::: ::: spoiler **各テストケースへの回答** 各テストケースに関しては、if文で分岐を実装することで解答できます。 「if文 <使用している言語名>」などで検索しましょう。 今回の問題では、以下のようなロジックを記述する必要があります。 1. ratingが1900以上ならば、"Division 1" と出力する。 2. そうでなく、ratingが1600以上ならば、"Division 2" と出力する。 3. そうでなく、ratingが1400以上ならば、"Division 3" と出力する。 4. そうでないならば、 "Division 4" と出力する。 1は、if文 2,3は、else if文 (pythonではelif文) 4は、else 文 で実現できます。 これの実装を載せるとほぼ答えになってしまうので、解説の方にコードを載せておきます。 ::: ### B. Diverse Strings :::spoiler **やるべきこと** 次を調べる必要があります。 - 同じ文字が2回以上出現しないこと - 含まれる文字がアルファベット順で連続していること ::: :::spoiler **解説しない方針** C/C++では、英小文字の変数を `c` と置くと `c - 'a'` とすることで `a-z` を `0-25` に変換することができます。 0で初期化された26要素の配列を `int cnt[26] = {};` のように用意して出現回数を調べると上の2つをチェックできます。 2つ目は、うまく状態を管理してループするなどする必要があります。 ::: :::spoiler **ヒント1** 2回以上出現するかどうかは set を用いて確認できます。 ::: :::spoiler **ヒント2** アルファベット順で連続しているとき、最初と最後のアルファベットの間にあるアルファベットの種類数は文字列の長さに等しくなります。 ::: #### 実装のステップ（C++/python) :::spoiler **入力の受け取り** ##### python ```python= s = input() ``` ##### C++ ```cpp= #include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; } ``` ::: :::spoiler **for文で1文字ずつsetに入れる** ##### python ```python= s = input() st = set() for i in range(len(s)): # setに既に入っているかチェック if (s[i] in st): #既にstに入っている pass else: st.add(s[i]) ``` ##### C++ ```cpp= #include <bits/stdc++.h> using namespace std; int main() { string s; cin >> s; set<char> st; for (int i = 0; i < s.size(); i++) { // setに既に入っているかチェック if (st.find(s[i]) != st.end()) { // 既にsetに入っている } else { st.insert(s[i]); } } } ``` ::: :::spoiler **setから最初と最後のアルファベットを取る** ##### python ```python= # ~~~~~~~~~~省略~~~~~~~~~~~ fst = min(st) lst = max(st) ``` ##### C++ ```cpp= #include <bits/stdc++.h> using namespace std; int main() { // ~~~~~~~~~~省略~~~~~~~~~~~ // 最初のアルファベット char fst = *st.begin(); // 最後のアルファベット char lst = *prev(st.end()); } ``` ::: :::spoiler **文字列の長さと、アルファベットの種類数** ##### python ```python= # ~~~~~~~~~~省略~~~~~~~~~~~ # 文字列の長さ ln = len(s) # 間にあるアルファベットの種類数 num_of_kind = ord(lst)-ord(fst)+1 ``` ##### C++ ```cpp= #include <bits/stdc++.h> using namespace std; int main() { // ~~~~~~~~~~省略~~~~~~~~~~~ // 文字列の長さ char len = s.size(); // 間にあるアルファベットの種類数 char num_of_kind = lst - fst + 1; } ``` ::: ### C. Parity Alternated Deletions :::spoiler **ヒント1** 数列$a$を偶奇ごとに2つの数列, $even,odd$ に分けましょう. ::: :::spoiler **ヒント2** 偶奇それぞれから, 最大いくつ取れるでしょうか. ::: :::spoiler **ヒント2.1** $odd,even$のうち, 要素が少ないほうは必ず空になります. 要素数が同じときは, 両方とも空になります. ::: :::spoiler **ヒント2.2** $odd,even$の要素数が異なる場合を考えます. 要素数が少ない側の要素数を $k$ とします. つまり, $k = min(|odd|,|even|)$ です. この時,もう片側からは最大でk+1個取れます. ::: :::spoiler **ヒント3** 取れる個数が決まっている時, 残った要素の総和を最小にするにはどのように取るのが最適でしょうか？ ::: :::spoiler **ヒント3.2** 大きいほうから取っていくのが最適です. ::: :::spoiler **ヒント3.3** 数列を「大きい順」にするには, ソートをする必要があります. ::: #### 実装のステップ (python/C++) :::spoiler **ヒント1の実装** $n$と数列$a$を受け取り, 2つの数列$even,odd$ に分ける部分までの実装です. ##### python ```python= #入力を受け取っています n = int(input()) a = list(map(int,input().split())) #2つのリストodd,evenに各要素を分けています odd = [] even = [] for i in range(n): if a[i] % 2 == 1: #2で割った余りが1なら奇数 odd.append(a[i]) else: even.append(a[i]) ``` ##### C++ ```cpp= int main(){ //入力を受け取っています int n; cin >> n; vector<int> a(n); for (int i=0 ; i < n ; i++) cin >> a[i]; //2つのvector odd,evenに各要素を分けています vector<int> odd(0); vector<int> even(0); for (int i=0 ; i < n ; i++){ if (a[i] % 2 == 1) odd.push_back(a[i]); //2で割った余りが1なら奇数 else even.push_back(a[i]); } } ``` ::: :::spoiler **ヒント2の実装** $k = min(|odd|,|even|)$ を計算する部分の実装です. ##### python ```python= # ~~~~~~~~~~省略~~~~~~~~~~~ #len(L) とすると, リストLの長さが得られます. #min(x,y) とすることでxとyの最小値を計算できます. k = min( len(odd) , len(even) ) ``` ##### C++ ```cpp= int main(){ // ~~~~~~~~~~省略~~~~~~~~~~~ //L.size() とすると, vector Lの長さが得られます. //min(x,y) とすることでxとyの最小値を計算できます. int k = min(odd.size() , even.size()); } ``` ::: :::spoiler **ヒント3の実装** 大きい順にodd,evenを並び替える部分の実装です. ##### python ```python= # ~~~~~~~~~~省略~~~~~~~~~~~ # sortをすると昇順(小さい順)に並び替えられる. odd.sort() even.sort() # 降順(大きい順)にするために,前後を反転する. odd.reverse() even.reverse() ``` ##### C++ ```cpp= int main(){ // ~~~~~~~~~~省略~~~~~~~~~~~ // sortをすると昇順(小さい順)に並び替えられる. sort(odd.begin(),odd.end()); sort(even.begin(),even.end()); // 降順(大きい順)にするために,前後を反転する. reverse(odd.begin(),odd.end()); reverse(even.begin(),even.end()); } ``` ::: ### D. Two Shuffled Sequences :::spoiler **ヒント1** 数列を並び替えて考えても問題ありません。 ::: :::spoiler **ヒント2** 入出力例を見たりして、答えが存在しない条件を適当に考えてみましょう。 ::: :::spoiler **ヒント3** その条件が満たされないとき、必ず答えは存在するでしょうか。(必要十分条件でしょうか) ::: ### E. Equalize Them All :::spoiler **ヒント1** 2種類の操作を適当な2つの数に対して行ってみて、どのような結果になるか実験してみましょう。 ::: :::spoiler **ヒント2** 絶対に行わなければいけない操作回数の下限を考えてみましょう ::: :::spoiler **ヒント3** 具体的な構成はやや複雑な実装になります。なるべくシンプルに間違えない方法を考えましょう。 ::: ### F. Median String :::spoiler **ヒント1** 英小文字ではなく、`"0", "1", ..., "9"` からなる文字列で考えてみましょう。 ::: :::spoiler **ヒント2** リストの中心を簡単に求められないでしょうか。 ::: :::spoiler **ヒント3** 配列の1要素に1桁の数字を対応させて足し算を実装しましょう。 ::: :::spoiler **ヒント4** 次に、2で割る処理も実装しましょう。 ::: ### G. Grph Without Long Direted Paths :::spoiler **ヒント1** `NO`となるのはどのような時か考えましょう. ::: :::spoiler **ヒント2** 奇数長のサイクルがないグラフは二部グラフです. ::: :::spoiler **ヒント3** グラフ全体を, 同じ色の頂点が隣接しないように2色に塗り分けましょう. ::: ### H. Two Merged Sequences :::spoiler **ヒント1** 動的計画法を用いて解くことができます。 ::: :::spoiler **ヒント2** 先頭から見ていき、狭義単調増加数列と狭義単調減少数列のどちらに振り分けるかを考えましょう。 ::: :::spoiler **ヒント3** 今見ている要素を狭義単調増加(減少)数列に振り分けたとき、を扱うDP配列を考えてみましょう。 ::: ## 解説 実装に関しては、A問題のみ掲載しています。 それ以外の問題に関して、B,C問題はヒントの方に断片的コードを用意しておりますので参考にしてください。 また、後ほど要望があった問題・言語に関しては模範解答実装を用意しようと思います。 欲しい方が居ましたら、Slackまでどうぞ。 ### A. Division? ヒントの方にかなりの情報を載せていますので、ぜひそちらを読んでから参照してください。 こちらでは、実装だけを掲載しています。 ```python= # pythonでの実装 t = int(input()) for i in range(t): rating = int(input()) if 1900 <= rating: print ("Division 1") elif 1600 <= rating: print ("Division 2") elif 1400 <= rating: print ("Division 3") else: print ("Division 4") ``` ```cpp= #include <bits/stdc++.h> using namespace std; int main() { // C++の実装例 int t; cin >> t; for (int i=0 ; i<t ; ++i){ int rating; cin >> rating; if (1900 <= rating){ cout << "Division 1" << '\n'; }else if (1600 <= rating){ cout << "Division 2" << '\n'; }else if (1400 <= rating){ cout << "Division 3" << '\n'; }else{ cout << "Division 4" << '\n'; } } } ``` ### B. Diverse Strings まず、同じ文字が2回以上出現しないことは set などを用いることで確認できます。 その後、アルファベット順で連続しているかどうかはアルファベット順で最後の文字と最初の文字の位置の差と文字列の長さを比較することで確認できます。 例えば、`adefbc` の場合はアルファベット順で最初の文字は `a`、最後の文字は `f` なので位置の差は $5$ であって連続している場合は $6$ 文字である必要があるとわかります。 C++などでは `'f' - 'a'` のようにして位置の差を求められます。 pythonではord関数を用いて、askiiコードに文字を変換してから引き算する必要があります。 ### C. Parity Alternated Deletions 数列 $a$ を $2$ つの数列 $odd$ と $even$ に偶奇ごとに分けます. ここで, $k = min( |odd|,|even| )$ とすると, $odd,even$ それぞれから $k$ 個は必ず削除できます. (ここで, $|x|$ は数列 $x$ の長さを表します.) また, $odd,even$の内要素数が多いほうから取り始めることで, そちら側からさらに $1$ つを削除できます. 削除する時, それぞれの数列で大きいほうから削除した方が, 残りの要素の総和は小さくなります. よって答えは, 以下のように求めることができます. 1. 数列 $a$ の総和 $sum$ を計算する. 2. $a$ を $odd$ と $even$ に分ける. 3. $odd,even$ を降順にソートする. 4. $k (= min( |odd|,|even| ) )$ を計算する. 5. $sum$ から, $odd,even$ の最初$k$ 項の総和を引く. 6. $odd$ に $k+1$ 項目が存在すれば, $sum$からその値を引く. 7. $even$に $k+1$ 項目が存在すれば, $sum$からその値を引く. 8. $sum$ が答えである. ### D. Two Shuffled Sequences まず、狭義単調増加数列と狭義単調減少数列には同じ数が1度しか現れません。 なので、数列 $a$ に含まれる数が何回現れるかをチェックし、$3$ 回以上現れる数が存在する場合には `NO` になります。 それ以外の場合は、2回現れる数値を1つずつ使って狭義単調減少数列を作ります。 そして残りの数で狭義単調増加数列を作ることで条件を満たす2つの数列の組が出来上がります。 例えば、入力例1の場合には $[7, 2, 7, 3, 3, 1, 4]$ で2回現れる $3, 7$ で狭義単調減少数列 $[7, 3]$ を作ります。 そして残った $[7, 2, 3, 1, 4]$ を昇順に並べると狭義単調増加数列 $[1, 2, 3, 4, 7]$ となり、この組が答えの1つになります。 ### E. Equalize Them All まず, $a_i \neq a_j$を満たす $i,j$ について, 操作のタイプを適切に選ぶことで1回の操作で必ず $a_i$ を $a_j$ と等しい値にできることを示します. $a_i < a_j$ の場合, 操作1を選ぶと $a_i := a_i + |a_i-a_j| = a_i + (-a_i+a_j) = a_j$ となり, $a_i$ を $a_j$ と等しくできます. また, $a_i > a_j$ の場合, 操作2を選ぶと $a_i := a_i - |a_i-a_j| = a_i - (a_i + a_j) = a_j$ となり, $a_i$ を $a_j$ と等しくできます. よって, 数列$a$ に最も多く現れる整数 $x$ の出現回数を $cnt_x$ とした時, 操作回数 $n-cnt_x$ が操作回数の自明な最小値になります. そして, この最小値を達成する具体的な操作列を以下のようにして構成できます. まず, $x$ の出現位置を $1$ つ見つけて $pos_x$ とする. $i = pos_x-1,pox_x-2,...,1$ について, $a[i]\neq x$ ならば, $j = i+1$ として操作を行い, $a_i$ を $a_{i+1}$ と等しい値(すなわち$x$) にする. $i = pos_x+1,pox_x+2,...,n$ について, $a[i]\neq x$ ならば, $j = i-1$ として操作を行い, $a_i$ を $a_{i-1}$ と等しい値(すなわち$x$) にする. $x$ でない要素$1$つについて$1$回しか操作を行っていないので, $n-cnt_x$ 回の操作回数となります. ### F. Median String 文字列の辞書順なので難しく見えます。まず、単純にただの10進法の数として考えてみます。 すると、2つの数 $7$ と $13$ の間の数全てからなるリストは $[07, 08, 09, 10, 11, 12, 13]$ と見ると、文字列としても辞書順になっていることがわかります。 そして中心の値は $\frac{7 + 13}{2} = 10$ と求めることができます。 同様にして、文字列の場合でも $26$ 進法の数として考え、2つの数を足して2で割ることで答えを求めることができます。 繰り上がりや繰り下がりに注意して実装しましょう。 ### G. Graph Without Long Directed Paths グラフに奇数長のサイクルがあった場合, サイクル内のどこかで必ず長さ$2$のパスができてしまいます. よって, グラフに奇数長のサイクルがない, すなわち二部グラフであることは構成できる必要条件です. この条件は実は十分条件にもなっていて、具体的には以下のように構成できます. グラフを赤・青に塗り分ける. ただし, 辺で直接結ばれた頂点同士が同じ色であってはいけない. そして, 全ての辺を 赤→青 の向きにする. 二部フラフの判定, 二部グラフの塗り分けは, DFSで行うことができます. ### H. Two Merged Sequences 先頭から見ながら動的計画法を用いることで解くことができます。 先頭から見ていきながら、各 $a_i$ を狭義単調増加数列か狭義単調減少数列のどちらかに振り分けていきます。 途中で持っておくべき情報としては、増加数列の最後の数と減少数列の最後の数であり、前者はできるだけ小さく、後者はできるだけ大きい方が嬉しいです。 単純にこのペアを `dp[i] := (増加数列の最後、減少数列の最後)` のようにして持つにはどちらを優先するべきかわからなくなります。 ただ、$a_i$ を増加数列に振り分けた場合は増加数列の最後の数が固定されるので、減少数列の最後の数を最大化することだけ考えれば良くなり、減少数列に振り分けるときも同様になります。 よって、次のようなDP配列を考えればよいです。 `dp1[i] := a[i] を増加数列に振り分けたとき、減少数列の末尾の最大値` `dp2[i] := a[i] を減少数列に振り分けたとき、増加数列の末尾の最小値` 後は遷移を考えます。 $a_{i-1}$ と $a_i$ をどちらに振り分けるかで 4 通りの遷移があります。 - どちらも増加数列に振り分けるとき (条件: $a_{i-1} < a_i$) - $dp1[i] = \max(dp1[i],\, dp1[i - 1])$ - どちらも減少数列に振り分けるとき (条件: $a_{i-1} > a_i$) - $dp2[i] = \min(dp2[i],\, dp2[i - 1])$ - $a_{i-1}$ は減少、$a_i$ は増加 (条件: $dp2[i-1] < a_i$) - $dp1[i] = \max(dp1[i],\, a_{i-1})$ - $a_{i-1}$ は増加、$a_i$ は減少 (条件: $dp1[i-1] > a_i$) - $dp2[i] = \min(dp2[i],\,a_{i-1})$ DP配列の初期値は、dp1については $\max$ で更新するので $-\infty$、dp2は $\min$ なので $\infty$ で設定し、$dp1[0] = \infty, dp2[0] = -\infty$ とします。