競プロ講習会2022 前期1回

# 競プロ講習会2022 前期1回 ##### 問題セット https://codeforces.com/gym/378751 ##### 公式解説・A,B,D　　　なし・C,E　　　　https://bubblecup.org/Content/Media/FinalsEditorial2020.pdf ## 問題訳 (※分かりやすさのためかなり意訳しています) ### A. A+B (Trial Problem) #### 問題あなたは、2つの整数 $a,b$ を与えられます。$a+b$ を出力してください。 #### 入力 1行目には、1つの整数 $t\ (1 \le t \le 10^4)$ が与えられます。これは、入力にあるテストケースの数です。以後, $t$ 行に渡ってテストケースが与えられます。それぞれのテストケースでは、2つの整数 $a,b\ (-1000 \le a,b \le 1000)$ が与えられます。 #### 出力 $t$ 行に渡って出力してください. $i$ 行目には、 $i$ 番目のテストケースの答えを出力し、最後には改行をしてください。 #### 入出力例1 ##### 入力例1 ``` 4 1 5 314 15 -99 99 123 987 ``` ##### 出力例1 ``` 6 329 0 1110 ``` ### B. Square? #### 問題正方形の紙を、垂直か水平な方向に切ることで2つの長方形を作ったと Vasya は言っています。切ったあとの2つの長方形について、それぞれの縦と横の長さが与えられます。元の紙が正方形であった可能性があるかどうかを調べてください。言い換えると、「与えられた2つの長方形を組み合わせて正方形を作れるかどうかを判定してください」という問題になります。 #### 入力 1行目には、1つの整数 $t\ (1 \le t \le 10^4)$ が与えられます。これは、入力にあるテストケースの数です。以後、$t$ 個のテストケースが与えられます。各テストケースが次のように2行で与えられます。 1行目には、2つの整数 $a_1, b_1\ (1 \leq a_1, b_1 \leq 100)$ が与えられます。これは、1つ目の長方形の縦と横の長さです。 2行目には、2つの整数 $a_2, b_2\ (1 \leq a_2, b_2 \leq 100)$ が与えられます。これは、2つ目の長方形の縦と横の長さです。それぞれの長方形は正方形の紙を切ったときそのままの向きではなく、元の正方形での幅が切った後の長方形の高さとして与えられている可能性があることに注意してください。 #### 出力 $t$ 行に渡って出力してください。各行では、元の紙が正方形である可能性がありえる場合には `YES` を、ありえない場合には `NO` を出力してください。 `YES` と `NO` の大文字小文字は区別されないので、`Yes` や `No` と出力しても問題ありません。 #### 入出力例1 ##### 入力例1 ``` 3 2 3 3 1 3 2 1 3 3 3 1 3 ``` ##### 出力例1 ``` Yes Yes No ``` ### C. Years #### 問題宇宙探査の途中で、人類はとある惑星で生命の痕跡を見つけました。幸運にも、その惑星に暮らしていたすべて生命体の生年と、没年が記録された本を見つけました。面白いことに、その本に書かれている年は $(1,10^9)$ に収まっています！科学者たちはこの生命体の個体数が最大となった時の値と、その年を知りたいと思っています。この問題を解いてください！ #### 入力 1行目には、本に書かれた生命体の総数 $n\ (1 \le n \le 10^5)$ が与えられます。続く $n$ 行には、生命体の生年と没年が与えられます。具体的には、$i+1$行目には2つの整数 $b_i,d_i\ (1 \le b_i \le d_i \le 10^9)$ が与えられます。これは、$i$ 番目の生命体が $b_i$年の末に生まれ、$d_i$ 年の初頭に亡くなったことを示しています。 #### 出力 2つの整数 $y\ k$ をこの順で半角スペース区切りで出力してください。 $y$ は個体数が最大となった年、$k$ はその時の個体数です。 $y$ として考えられるものが複数ある場合、最小のものを出力してください。 #### 入出力例1 ##### 入力例1 ``` 3 1 5 2 4 5 6 ``` ##### 出力例1 ``` 2 2 ``` #### 入出力例2 ##### 入力例2 ``` 4 3 4 4 5 4 6 8 10 ``` ##### 出力例2 ``` 4 2 ``` ### D. Skier #### 問題スキー板をつけている人が雪の積もった平原の上にいます。その人の移動は、`S`, `N`, `W`, `E` で表され、それぞれ南、北、西、東に1メートル移動することに対応します。その人がまだ通っていない道を移動するときには5秒かかり、既に通ったことにある道を移動するときには既に雪が踏み均されているため1秒で移動できます。与えられた文字列の通りに移動したとき、何秒かかるかを求めてください。 #### 入力 1行目には、1つの整数 $t\ (1 \le t \le 10^4)$ が与えられます。これは、入力にあるテストケースの数です。以後、$t$ 個のテストケースが与えられます。各テストケースは空でない、`S`, `N`, `W`, `E` からなる文字列で与えられます。文字列の長さは $10^5$ を超えません。 $t$ 個のテストケースで与えられる文字列の長さの合計は $10^5$ を超えません。 #### 出力各テストケースに対して、何秒で与えられた文字列に従って移動できるかを出力しなさい。 #### 入出力例 ##### 入力例 ``` 5 NNN NS WWEN WWEE NWNWS ``` ##### 出力例 ``` 15 6 16 12 25 ``` ### E. Ancient Language #### 問題科学者たちは、古代人が書いた古い本を見つけました。バラバラにはなっていましたが、幸いなことに破れはなく紙にはページ番号が書いてありました。言語学者はこれは辞書かもしれないと考えました。不思議なことに、この本は英語のアルファベット小文字の中の一部の文字を使って書かれています。ページの情報が与えられるので、古代人の言語におけるアルファベットの順番を求めてください。 #### 入力 1行目には2つの整数 $n,k\ (1 \le n,k \le 10^3)$ が与えられます。 $n$ は、発見された紙の枚数です。各紙には、ちょうど $k$ 個の単語が書かれています。続いて、各紙の情報が $n$グループ分与えられます。グループ $i$ の最初の行には、整数 $p_i$ が与えられます。 $p_i$ は紙 $i$ のページ番号です。続く $k$ 行には、紙 $i$ に書かれている単語が与えられます。各単語の長さは100以下です。 #### 出力古代人が使っていたアルファベットを、辞書順に出力してください。本が辞書でない場合、辞書順が定まらない場合があります。この場合は `IMPOSSIBLE` と出力してください。 ## ヒント ### ヒントに関しての諸注意各問題のポイントをヒントという形で紹介しています。コンテスト中であっても、詰まってしまったらぜひご確認ください。コンテスト後に復習する際に活用していただいてもいいです。一部の問題に関しては実装を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に含まれない文字を含んだコードを提出するとエラーになることがありますので注意してください。 ### A. A+B (Trial Problem) :::spoiler **テストケースとは？** Codeforcesでは、多くの問題が「複数テストケース」のスタイルを取っています。「複数テストケース」では、問題文の問題を複数個解いてからプログラムを終了することが要求されます。多くの場合は、入力の1行目に解くべき問題の個数 $t$ が与えられます。その後 $t$ 個の問題を解いてからプログラムを終了しなくてはいけません。より具体的には、以下の「何をすればいいか？」で説明します。 ::: :::spoiler **何をすればいいか？** 　まず、問題の入出力例1の部分を見てみましょう。(以下にコピーしてあります) ##### 入力例1 ``` 4 1 5 314 15 -99 99 123 987 ``` ##### 出力例1 ``` 6 329 0 1110 ``` 入力例の1行目に書かれている「4」はこの入出力例におけるテストケースの数です。そして2～5行目には、4つの問題の入力が書かれています。出力例の4つの数は、この4つの問題の答えに対応しています。 (※例えば、入力例の2行目 $1\ 5$ は、$1 + 5 = 6$ であり、出力例の1行目の $6$ と対応しています。) 「入力例1のような入力を受け取ったら、出力例1のような出力をするプログラムを書け」というのが本問題で求められていることです。 ::: :::spoiler **入出力の受け取り方** 入力は「標準入力ストリーム」から受け取り、出力は「標準出力ストリーム」に行います。各言語で入出力の方法は大きく異なるので、以上のワードを含めて検索すると良いと思います。 ::: :::spoiler **どうしても詰まった時は** 始めたての頃は入出力や複数テストケースへの対応でかなり苦しむと思います。本ページ下部の解説に、python と C++での実装を載せているので、コンテスト中でもぜひ参照してください。また、質問も大歓迎なのでお気軽に質問してください。 ::: ### B. Square? ::: spoiler **ヒント1** 実際に紙を組み合わせるようにリアルに考えるのではなく、単純な数式で判定できないか考えましょう。 ::: ::: spoiler **ヒント2** 答がYESであると仮定して、矛盾していないかを調べましょう。 ::: ::: spoiler **ヒント3** もし答がYESなら、元々の正方形の1辺の長さは入力の内容から当てることができます。 ::: ::: spoiler **ヒント4** もし答がYESなら、$a_1,b_1$ のうちで長い方が長方形の1辺の長さです。 ::: ::: spoiler **ヒント5** 長方形の1辺の長さを $L$ としたとき、答がYESであるためには、$a_2,b_2$ のうちで長いほうも $L$ である必要があります。 ::: ::: spoiler **ヒント6** 答がYESであるためには、2つの長方形の短いほうの長さの和は、$L$ になっている必要があります。 ::: ::: spoiler **実装例** ここでは、具体的な実装例を紹介します。一部処理を歯抜けにしてあるので、埋めることで正解できます。 (pythonで提出時は日本語を全部消してください！！) ```python= # python t = int(input()) for _ in range(t): a1,b1 = map(int,input().split()) a2,b2 = map(int,input().split()) ans = "YES" #YESと仮定すると… L = max(a1,b1) #正方形の長さは、a1,b1の内で大きいほう #ここでもし、max(a2,b2)がLと等しくないのなら、ansを"NO"にする。 #ここでもし、min(a1,b1)+min(a2,b2) がLと等しくないのなら、ansを"NO"にする。 print (ans) #ansを出力する. ``` ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for (int loop = 0 ; loop < t ; ++loop){ int a1,a2,b1,b2; cin >> a1 >> b1; cin >> a2 >> b2; string ans = "YES"; //YESと仮定すると… int L = max(a1,b1); //#正方形の長さは、a1,b1の内で大きいほう //ここでもし、max(a2,b2)がLと等しくないのなら、ansを"NO"にする。 //ここでもし、min(a1,b1)+min(a2,b2) がLと等しくないのなら、ansを"NO"にする。 cout << ans << '\n'; } } ``` ::: ### C. Years :::spoiler **ヒント1** 個体数さえわかればいいので、誕生と死亡が紐ついている必要はないです。つまり、誕生は単に個体数が1だけ増えるイベント。死亡は、個体数が1だけ減るイベントと考えればよいです。 ::: :::spoiler **ヒント2** 誕生、死亡イベントをまとめて時系列順にソートしましょう。 ::: :::spoiler **ヒント3** ソート時は年の初めと末、誕生と死亡を区別する必要があります。 ::: :::spoiler **ヒント4** (イベントの起こる年,そのイベントによる人数変化) のペア(タプル) で昇順ソートすればいいです。 ::: ### D. Skier :::spoiler **ヒント1** 道はマス目の「間」にあります。マス目自体が道なわけではないので注意しましょう。 ::: :::spoiler **ヒント2** 通った道をsetなどで管理しましょう。 ::: ### E. Ancient Language :::spoiler **制約について** 本問題の入力サイズは最大で $10^8$ 文字以上となっています。実際は最大ケースが入っていないので、それよりも小さいですが… 本問題は、内容は教育的でよいのですが、テストケースや制約の面で質に問題があると言えるかもしれません。解法が正しい(と思われる)のにTLEする場合、下の「入出力に関する注意」をご覧ください。 ::: :::spoiler **入出力に関する注意** 本問題の入力サイズは非常に大きいです。 python3, もしくはpypy3では入力が遅いため通常の入出力を使うとまずTLEします。以下の記事などを参考に高速なioを利用しましょう。 https://www.geeksforgeeks.org/fast-i-o-for-competitive-programming-in-python/ C++でも、cinを使うとTLEするかもしれませんので、scanf等を利用しましょう。 ::: :::spoiler **ヒント1** まずページを並べ直して、単語リストを一つにまとめ上げましょう。 ::: :::spoiler **ヒント2** 隣り合う単語にのみ注目すればよいです。 ::: :::spoiler **ヒント3** 隣接単語の情報から有向グラフを構築します。 ::: :::spoiler **ヒント4** 最後は、トポロジカルソートをします。 ::: ## 解説 ### 解説に関してこちらに各問題の解説を掲載してます。基本的にバーチャルコンテスト終了後に読むことを推奨しますが、詰まってしまった場合は自分の判断で参照していただいて構いません。また、一部の問題ではpython,C++での実装を掲載してあります。 ### A. A+B (Trial Problem) 二つの整数を受け取り、出力するだけの問題です。競技プログラミングを一切やったことがない方々もいると思いますので、今回はセットに含めることにしました。注意として、各テストケースの答えは改行区切りで出力し、出力の一番最後にも改行を入れる必要があります。以下、実装を紹介します。 :::spoiler **pythonの例** ```python= #python t = int(input()) for _ in range(t): a,b = map(int,input().split()) print (a+b) ``` ::: :::spoiler **C++の例** ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for (int loop = 0 ; loop < t ; ++loop){ int a,b; cin >> a >> b; cout << a+b << '\n'; } } ``` ::: ### B. Square? 答えがYESであると仮定したとき、それが正しいかどうかを確かめます。まず、二つの紙の長いほうの辺は、元々の正方形の正方形の一辺の長さと一致しているはずです。そして、短辺の長さの和は正方形の一辺の長さになっているはずです。この2つが成り立っていれば、うまく並べることで正方形になるとわかるので矛盾している場合、答えをNOにすればよいです。以下、実装を紹介します。 (※pythonで提出する際は、全角文字をすべて削除してください！) :::spoiler **pythonの例** ```python= #python # python t = int(input()) for _ in range(t): a1,b1 = map(int,input().split()) a2,b2 = map(int,input().split()) ans = "YES" #YESと仮定すると… L = max(a1,b1) #正方形の長さは、a1,b1の内で大きいほう #ここでもし、max(a2,b2)がLと等しくないのなら、ansを"NO"にする。 if max(a2,b2) != L: ans = "NO" #ここでもし、min(a1,b1)+min(a2,b2) がLと等しくないのなら、ansを"NO"にする。 if min(a1,b1) + min(a2,b2) != L: ans = "NO" print (ans) #ansを出力する. ``` ::: :::spoiler **C++の例** ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; for (int loop = 0 ; loop < t ; ++loop){ int a1,a2,b1,b2; cin >> a1 >> b1; cin >> a2 >> b2; string ans = "YES"; //YESと仮定すると… int L = max(a1,b1); //#正方形の長さは、a1,b1の内で大きいほう //ここでもし、max(a2,b2)がLと等しくないのなら、ansを"NO"にする。 if (max(a2,b2) != L){ ans = "NO"; } //ここでもし、min(a1,b1)+min(a2,b2) がLと等しくないのなら、ansを"NO"にする。 if ( min(a1,b1)+min(a2,b2) != L ){ ans = "NO"; } cout << ans << '\n'; //ansを出力 } } ``` ::: ### C. Years 「どの個体が誕生・死亡したか」は単に個体数のみを考える場合は重要ではありません。ここでは、誕生は人数が+1されるイベント、死亡は人数が-1されるイベントとみなせばよいです。 (イベントが起きた年, 人数の変化) をペア(タプル)にして昇順ソートすることで、イベントを起きた順に並べることができます。ペアの昇順ソートとは、各ペアを以下の規則に沿って並べ替えることを指します。・1項目が小さい方が前に来る・1項目が同じペア同士の場合、2項目が小さい方が前に来る。このような並べ方は、pythonではタプルをリストに入れてソート、C++では std::pair を std::vectorに入れてソートすることで実現できます。この問題の設定においては、$y$ 年に死亡するイベントと、 $y$ 年に誕生するイベントは、前者の方が先に起こることになっています。死亡・誕生それぞれに対応するペア(タプル)はそれぞれ、 $(y,-1)\ (y,+1)$ です。 $-1 < +1$ なので、ソートした際には死亡の方が先に来ます。これは問題の設定とうまく適合しているため、これでよいことが分かります。以下に実装例を示します。 (※pythonで提出する際は、全角文字をすべて削除してください！) :::spoiler **pythonの例** ```python= #python import sys from sys import stdin n = int(stdin.readline()) lis = [] for i in range(n): b,d = map(int,stdin.readline().split()) lis.append( (b,+1) ) lis.append( (d,-1) ) lis.sort() maxnum = 0 #人口の最大値 maxyear = 0 #最大を達成した年 now = 0 #現在の人口 for y,diff in lis: now += diff if now > maxnum: maxyear = y maxnum = now print (maxyear,maxnum) ``` ::: :::spoiler **C++の例** ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<pair<int,int>> lis; for (int i=0; i < n; ++i){ int b,d; cin >> b >> d; lis.push_back(make_pair(b,1)); lis.push_back(make_pair(d,-1)); } sort(lis.begin(),lis.end()); int maxnum = 0; //人口の最大値 int maxyear = 0; //最大を達成した年 int now = 0; //現在の人口 for (auto y_diff : lis){ int y = y_diff.first; int diff = y_diff.second; now += diff; if (now > maxnum){ maxyear = y; maxnum = now; } } cout << maxyear << ' ' << maxnum << '\n'; } ``` ::: ### D. Skier 全ての道をsetなど、要素の追加と発見を高速に行えるデータ構造で管理しつつ、随時通ったかどうか判定すればよいです。 :::spoiler **pythonでの実装例** ```python= import sys from sys import stdin tt = int(stdin.readline()) for loop in range(tt): S = list(stdin.readline()[:-1]) st = set() ans = 0 x,y = 0,0 for i in S: nx,ny = x,y if i == "N": nx += 1 elif i == "S": nx -= 1 elif i == "W": ny += 1 else: ny -= 1 lx = x rx = nx ly = y ry = ny if (lx,ly) > (rx,ry): lx,ly,rx,ry = rx,ry,lx,ly tup =(lx,rx,ly,ry) if tup in st: ans += 1 else: ans += 5 st.add(tup) x,y = nx,ny print (ans) ``` ::: ### E. Ancient Language まず、ページを番号順に並べ直し、単語を辞書に書かれていた順に並べます。この操作によってできた単語列を $S$ とします。次に、隣接する単語 $S_i , S_{i+1}$ から文字の順番についての情報を得て、グラフを構築します。まず、$S$ の中に一度でも登場する文字を頂点とした辺の無いグラフを作っておきます。ここに辺を追加していきます。・$S_i$ と $S_{i+1}$ が同一の場合　　→特に情報はありません・$S_i$ と $S_{i+1}$ が異なり、かつ $S_i$ が $S_{i+1}$ の接頭辞の場合　　→特に文字の順番に関する情報はありません・$S_i$ と $S_{i+1}$ が異なり、かつ $S_{i+1}$ が $S_i$ の接頭辞の場合　　→このような状況は辞書ではありえないので、`IMPOSSIBLE`を出力し、終了します。・以上のどちらでもない場合　　$S_i$ の $j$ 文字目と、$S_{i+1}$ の $j$ 文字目が異なるような最小の $j$ を求めます。前者を $S_{i,j}$ 後者を $S_{i+1,j}$ と呼ぶことにします。$S_{i,j}$の方が辞書順で先に来ていないとまずいので、グラフ上で頂点$S_{i,j}$ から頂点$S_{i+1,j}$ へ辺を引きます。グラフを構築後、トポロジカルソートを行うことでアルファベットの順番を求めることができます。グラフがDAGでない場合、答えは`IMPOSSIBLE`です。・トポロジカルソートに関しては以下を参照(中身はちゃんとしています) https://qiita.com/Morifolium/items/6c8f0a188af2f9620db2 ・pythonでの実装例 https://codeforces.com/gym/378751/submission/154465129