競プロ講習会2022 前期3回　Web資料

# 競プロ講習会2022 前期3回　Web資料 ## ◎第3回の参加方法について今回も、好きな時間に問題を解いておくことができるようにします。講習会開始後30分は問題を解く時間に充てますが、ちゃんと時間を取って解きたい人は以下の方法で事前に参加してください。まず、Codeforcesにログインします。その後、K-LMSに公開したコンテストリンクを開きます。 KeioAICKyoproCourseContest #3 に、**Virtual participation**します。 (※この機能は、好きな時間を選んでコンテストに参加できる機能です) 開始したい時間を入力し、Registar for virtual participationを押します。指定した時間になったらコンテストが始まるので、問題を解きます。コンテストの時間終了後、講習会前であっても解き直しなど自由に行っていただいて構いません。また、参加中であってもweb資料のヒント・解説は参照してかまいません。 Slackの公開チャンネルやDMでの質問も受け付けますのでお気軽にどうぞ(すぐに答えられるとは限りませんがご了承ください)。 #### ◎問題セット https://codeforces.com/contestInvitation/5cc1c433045c7b63fbb7f74ffba1a2a57d6ff409 #### ◎公式解説 ##### A〜G問題 https://codeforces.com/blog/entry/59430 ##### H問題 https://codeforces.com/blog/entry/92739 ## ◎問題訳(意訳あり注意) ### ◎A. Remove Duplicates TL:1s ML:256MB #### ●問題 Petya は $n$ 個の整数からなる配列 $a$ を持っています。彼は、この配列から重複をなくしたいです。 Petya は重複をなくすとき、各数値について最も右に現れる要素だけを残して、残された要素の相対的な順番は変えたくありません。最終的に得られる配列を出力してください。 #### ●入力 1行目に、整数 $n(1 \le n \le 50)$ が与えられます。これは Petya の配列の要素の数です。 2行目に、空白区切りで $n$ 個の整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 1000)$ が与えられます。これは Petya の配列です。 #### ●出力 1行目に、整数 $x$ を出力してください。 $x$ は、重複をなくした後の配列の要素数です。 2行目に、$x$ 個の整数を空白区切りで出力してください。各整数は重複をなくした後の配列の要素です。 #### ●入出力例 ##### 入力例1 ``` 6 1 5 5 1 6 1 ``` ##### 出力例1 ``` 3 5 6 1 ``` 1が3回現れているので2つ取り除き、一番右のものだけ残すことになります。 5についても2回現れているので、右側のものだけ残すことになります。 ``` (1) (5) 5 (1) 6 1 ``` 括弧で囲まれている要素が取り除くことになる要素です。 ##### 入力例2 ``` 5 2 4 2 4 4 ``` ##### 出力例2 ``` 2 2 4 ``` 1番目の2と、2,4番目の4を取り除くことになります。 ##### 入力例3 ``` 5 6 6 6 6 6 ``` ##### 出力例3 ``` 1 6 ``` 1, 2, 3, 4番目の6を取り除くことになります。 ### ◎B. File Name TL:1s ML:256MB #### ●問題 Polycarpは"Codehorses"というサイトでファイルを送ろうとしています。しかし、ファイル名に"x"が3つ以上連続で現れる場合、送信ができない仕様です。現在のファイル名が与えられるので、ファイルを送信するためにPolycarpは文字を任意の位置からいくつか選んで削除します。削除する必要がある最小の文字数を求めてください。ただし、最初から削除する必要がない場合は答えは0となります。 #### ●入力 1行目に、整数$n(3 \le n \le 100)$ が与えられます。これは現在のファイル名の長さです。 2行目に、長さ$n$の文字列$s$が与えられます。これは、現在のファイル名です。 #### ●出力 "xxx"を部分文字列として含まないために削除する必要がある最小の文字数を1行目に出力し、改行してください。ただし、最初から削除する必要がない場合は`0`を出力してください。 #### ●入出力例 ##### 入力例1 ``` 6 xxxiii ``` ##### 出力例1 ``` 1 ``` 最初の"xxx"からどれか1文字を削除することで送信可能になります。 ##### 入力例2 ``` 5 xxoxx ``` ##### 出力例2 ``` 0 ``` ##### 入力例3 ``` 10 xxxxxxxxxx ``` ##### 出力例3 ``` 8 ``` ### ◎C. Letters TL:4s ML:256MB #### ●問題大学に $n$ 棟の寮があり、それぞれ $1$ から $n$ と番号付けされています。$i$ 番目の寮には $a_i$ 個の部屋があり、$i$ 番目の寮の部屋は $1$ から $a_i$ で番号付けされています。配達員が手紙を配達するとき、宛先に寮番号と部屋番号が書かれておらず、代わりにすべての寮の部屋をまとめた部屋番号が書かれていることがあります。この場合、すべての部屋は $1$ から $a_1 + a_2 + \cdots + a_n$ で番号付けされていて、$1$ 番目の寮から順番に番号がついています。例えば、$n = 2, a_1 = 3, a_2 = 5$ の場合を考えます。このとき、手紙の宛先には $1$ から $8$ のいずれかが書かれています。$7$ が書かれているときには、2つ目の寮の4番目の部屋を意味しています。すべての寮をまとめた部屋番号が書かれた $m$ 個の手紙について、どの寮のどの部屋番号を宛先にしたものであるかを求めてください。 #### ●入力 1行目に、2つの整数 $n, m(1 \leq n, m \leq 2 \cdot 10^5)$ が与えられます。それぞれ寮の数と手紙の数です。 2行目に、$a_1, a_2, \ldots, a_n(1 \leq a_i \leq 10^{10})$ が与えられます。各 $a_i$ は $i$ 番目の寮にある部屋の数を表しています。 3行目に、$b_1, b_2, \ldots, b_m(1 \leq b_j \leq a_1 + a_2 + \cdots + a_n)$ が与えられます。$b_j$ は、$j$ 番目の手紙に書かれた (すべての寮の部屋に対しての) 部屋番号です。$b_j$ は昇順に与えられます。 #### ●出力 $m$ 行にわたって出力してください。各手紙について、2つの整数 $f, k$ を出力してください。$f (1 \leq f \leq n)$ は寮の番号で、$k(1 \leq k \leq a_f)$ はその寮での部屋番号です。 #### ●入出力例 ##### 入力例1 ``` 3 6 10 15 12 1 9 12 23 26 37 ``` ##### 出力例1 ``` 1 1 1 9 2 2 2 13 3 1 3 12 ``` - 1番目の手紙は、1番目の寮の1番目の部屋が宛先です。 - 2番目の手紙は、1番目の寮の9番目の部屋が宛先です。 - 3番目の手紙は、2番目の寮の2番目の部屋が宛先です。 - 4番目の手紙は、2番目の寮の13番目の部屋が宛先です。 - 5番目の手紙は、3番目の寮の1番目の部屋が宛先です。 - 6番目の手紙は、3番目の寮の12番目の部屋が宛先です。 ##### 入力例2 ``` 2 3 5 10000000000 5 6 9999999999 ``` ##### 出力例2 ``` 1 5 2 1 2 9999999994 ``` ### ◎D. Almost Arithmetic Progression TL:1s ML:256MB #### ●問題 Polycarpは等差数列が好きです。彼は、長さ $n$ の数列 $b = [b_1,b_2,...,b_n]$ を持っています。彼は、好きな整数$k(0 \le k \le n)$を選び、数列 $b$ から $k$ 個の要素を選びます。そして、選んだ各要素について1を加える、または1を引く操作のうちどちらか片方を行います。(ある要素からは引き、ある要素には加えることが可能です。言い換えると、各要素への操作は独立に選択できます。) 操作後の $b$ が等差数列になった時、$k$ として考えられる最小値を求めてください。ただし、どのように操作しても等差数列にならない場合は、`-1`を出力してください。 ※等差数列とは数列$a = [a_1,a_2,...,a_n]$は、全ての$i(1 \le i < n)$について$a_{i+1}-a_i$が等しい時、またその場合に限り等差数列です。この定義に基づくと、長さが$1,2$の全ての数列は等差数列です。 #### ●入力 1行目には、一つの整数$n(1 \le n \le 100000)$ が与えられます。これは、 $b$ の長さです。 2行目には、 $b_1,b_2,...b_n(1 \le b_i \le 10^9)$ がこの順で空白区切りで与えられます。 #### ●出力 $b$ が操作後に等差数列となった場合、 $k$ として考えられる最小値を求め、1行目に出力し、改行してください。ただし、どのように操作しても等差数列にならない場合は、`-1`を出力してください。 #### ●入出力例 ##### 入力例1 ``` 4 24 21 14 10 ``` ##### 出力例1 ``` 3 ``` ##### 入力例2 ``` 2 500 500 ``` ##### 出力例2 ``` 0 ``` ##### 入力例3 ``` 3 14 5 1 ``` ##### 出力例3 ``` -1 ``` ##### 入力例4 ``` 5 1 3 6 9 12 ``` ##### 出力例4 ``` 1 ``` ### ◎E. Bus Video System TL:1s ML:256MB #### ●問題 Berland のバスには監視カメラのシステムが備え付けられており、バス停での乗車人数の変化を記録しています。現在のバス停に到着する直前の乗客が $x$ 人、出発した直後の乗客が $y$ 人のとき、システムは$y - x$ を記録します。試験走行を1つのバスと $n$ 個のバス停について行いました。すると、システムは整数列 $a_1, a_2, \ldots, a_n$ を記録しました。$a_i$ は $i$ 番目のバス停で記録した数値で、バス停には到着する順番に番号が付けられています。最初のバス停に止まる直前の乗車人数として、何通りの可能性があるかを求めてください。ただし、同時にバスに乗ることができる人数は $w$ とします。つまり、どんなときもバスには $0$ 人以上 $w$ 人以下しか乗っていません。 #### ●入力 1行目に、2つの整数 $n, w(1 \leq n \leq 1000, 1 \leq w \leq 10^9)$ が与えられます。それぞれバス停の数とバスの乗車可能人数です。 2行目に、$a_1, a_2, \ldots, a_n(-10^6 \leq a_i \leq 10^6)$ が与えられます。 $a_i$ はシステムが $i$ 番目のバス停で記録した数値です。 #### ●出力最初のバス停に到着する直前に乗っている人数としてありえる人数が何通りあるかを出力してください。もしも記録された数値に矛盾がある場合 (乗客が $0$ 人未満や $w$ 人よりも多くなるタイミングがある場合) には $0$ を出力してください。 #### ●入出力例 ##### 入力例1 ``` 3 5 2 1 -3 ``` ##### 出力例1 ``` 3 ``` 最初の乗車人数として、0人、1人、2人がありえます。 ##### 入力例2 ``` 2 4 -1 1 ``` ##### 出力例2 ``` 4 ``` 1、2、3、4人がありえます。 ##### 入力例3 ``` 4 10 2 4 1 2 ``` ##### 出力例3 ``` 2 ``` 0、1人がありえます。 ### ◎F. Mentors TL:3s ML:256MB #### ●問題 BerSoft社では、$n$ 人のプログラマが働いています。 $i$ 人目のプログラマは $r_i$ のスキル持っています。プログラマ $a$ は、プログラマ $b$ よりもスキルが真に大きく $(r_a>r_b)$ 、かつ $b$ と喧嘩をしていない場合に限り $b$ のメンターをすることができます。各プログラマのスキルと、喧嘩をしている $k$ 組のペアが与えられます。各 $i(1 \le i \le n)$ について、$i$ がメンターをすることができる人数を求めてください。 #### ●入力 1行目には２つの整数 $n,k (2 \le n \le 10^5, 0 \le k \le \rm{min}(2 \times 10^5, \frac{n(n-1)}{2}) )$ が与えられる。$n$ はプログラマの数で、$k$ は喧嘩しているペアの数です。 2行目には、$r_1,r_2,...,r_n(1 \le r_i \le 10^9)$ がスペース区切りで与えられます。$r_i$ はプログラマ $i$ のスキルです。続く $k$ 行には、喧嘩をしているペアの情報が与えられます。各情報は２つの整数 $x,y (1 \le x,y \le n, x \neq y)$ で与えられ、これはプログラマ $x$ と $y$ が喧嘩をしていることを示します。$x\ y$ が入力に含まれていた場合、$x\ y$がもう一つ含まれていたり、$y\ x$が含まれていることはないことが保証されます。 #### ●出力 $n$ この整数 $x_1,x_2,...,x_n$ をスペース区切りで1行に出力し、最後に改行してください。ここで、 $x_i$ はプログラマ $i$ がメンターをすることができる人数です。(プログラマ$i$ のメンターをすることができる人数ではないことに注意してください。) #### ●入出力例 ##### 入力例1 ``` 4 2 10 4 10 15 1 2 4 3 ``` ##### 出力例1 ``` 0 0 1 2 ``` ##### 入力例2 ``` 10 4 5 4 1 5 4 3 7 1 2 5 4 6 2 1 10 8 3 5 ``` ##### 出力例2 ``` 5 4 0 5 3 3 9 0 2 5 ``` ### ◎G. Petya's Exams TL:1s ML:256MB #### ●問題 Petya は大学で勉強していて、今年度はあと $n$ 日の special daysで終了します。 Petya はその間に $m$ 個の試験に合格する必要があります。この問題で、special days は $1$ から $n$ で番号付けされています。各試験について、3つのパラメータがあります。 - $s_i$ は $i$ 番目の試験の問題が公開される日 - $d_i$ は $i$ 番目の試験日 ($s_i < d_i$) - $c_i$ は $i$ 番目の試験へ向けての準備を Petya がする必要のある日数で、準備は $s_i$ 日目から $d_i - 1$ 日目の間に行うことができます。それぞれの日に、Petya は3種類の活動を行うことができます。「何もせずに休みを取る」、「ちょうど1つの試験を受ける」、「ちょうど1つの試験に向けての準備をする」の3種類です。よって、複数種類の試験の準備や受験を1日で行うことはできません。2つの活動を1日で混ぜて行う事もできません。$i$ 番目の試験に向けての準備を $j$ 日目に行うとき、$s_i \leq j < d_i$ です。試験に向けての準備の間に休みを取ったり、異なる試験に向けての準備を連続する日に行うことができます。つまり、ある試験に向けての準備を連続して行う必要はありません。 Petya がすべての試験に向けて準備して合格するためのスケジュールを見つけるか、不可能かどうかを判定してください。 #### ●入力 1行目に、2つの整数 $n, m(2 \leq n \leq 100, 1 \leq m \leq n)$ が与えられます。special days の日数と試験の数です。続いての $m$ 行には、3つの整数 $s_i, d_i, c_i (1 \leq s_i < d_i \leq n, 1 \leq c_i \leq n)$ が与えられます。それぞれ、$i$ 番目の試験問題が公開される日、試験日、Petya が準備するのに必要な日数です。すべての試験は異なる日に行われることが保証されています。異なる試験の問題は同じ日に公開されることや、ある試験が行われる日に他の試験の問題が公開されることがあります。 #### ●出力もしもすべての試験の準備をして合格することができない場合、`-1` を出力してください。もしも可能であれば、$n$ 個の整数を空白区切りで出力してください。 $j$ 番目の整数は、 - $(m + 1)$ のとき、$j$ 日目に試験を受けます(同じ日に複数の試験は開催されません) - 0 のとき、$j$ 日目に Petya は休みます - $i (1 \leq i \leq m)$ のとき、$j$ 日目に Petya は $i$ 番目の試験に向けて準備します。**各試験に向けての準備を行う日数は、準備に必要な日数と一致している必要があります。** 各試験は入力で現れる順番に $1$ から $m$ で番号付けされています。複数のスケジュールが考えられる場合、任意の1つを出力してください。 #### ●入出力例 ##### 入力例1 ``` 5 2 1 3 1 1 5 1 ``` ##### 出力例1 ``` 1 2 3 0 3 ``` 1日目に試験1に向けて準備し、2日目に試験2に向けて準備すると、３日目に試験１を合格して5日目に試験2に合格することができます。 4日目は休みます。このスケジュールですべての試験に合格できます。 ##### 入力例2 ``` 3 2 1 3 1 1 2 1 ``` ##### 出力例2 ``` -1 ``` 3日間で2つの試験があります。2日間は試験を受けないといけないので準備に使えるのは1日だけですが、どちらの試験も1日の準備が必要なので日数が足りません。したがって、この例ではすべての試験に合格することができません。 ##### 入力例3 ``` 10 3 4 7 2 1 10 3 8 9 1 ``` ##### 出力例3 ``` 10 3 4 7 2 1 10 3 8 9 1 ``` ### ◎H. AquaMoon and Permutations TL:2s ML:256MB #### ●問題 Cirnoは $n \times n$のサイズのラテン法格$a$を持っています。 Cirnoは、$n$ 個の長さ$n$の順列を追加で用意し、ラテン方格の下に付け足しました。操作後、$a$ のサイズは $2n \times n$ となります。 ($n+1$行目から$2n$行目まではラテン方格をなすとは限らないことに注意してください。) この時、全ての $k(1\le k \le n)$ について、$a[i][k] = a[i+n][k]$ を満たす $i(1 \le i \le n)$ が存在することが確認できました。また、全ての $i,j(1 \le i,j \le 2n, i \neq j)$ のペアに関して、 $a[i][k] \neq a[j][k]$ となるような $k(1 \le k \le n)$ が存在することも確認できました。そして、$a$ の行を好きな順序で並べ替えました。この時点での$a$を$A$ とします。 $A$ が入力として与えられます。$A$ から $n$ 個の行を抜き出して元の順番で並べた時、ラテン法格をなすような抜き出し方の総数を $\rm{mod}\ 998244353$ で求めなさい。また、そのような抜き出し方の例を一つ構築しなさい。 ※順列とはこの問題において、長さ$n$ の順列とは、長さ$n$の数列であって、$1$以上$n$以下の整数を全て一つずつ要素に含む数列のことを指します。 ※ラテン方格とは $n \times n$のサイズのラテン方格とは、どの行・列を抜き出しても必ず長さ$n$の順列になっているような行列のことを指します。 #### ●入力本問題はマルチテストケースです。 1行目に、テストケースの数 $t(1 \le t \le 100)$ が与えられます。 2行目からは、各テストケースの入力が与えられます。各テストケースの最初の行には、整数 $n(5 \le n \le 500)$ が与えられます。続く $2n$ 行には、$A$ が与えられます。全てのテストケースにおける $n$ の総和は $500$ を超えないことが保証されます。 #### ●出力各テストケース2行出力してください。 1行目には、条件を満たす抜き出し方の総数を$\rm{mod}\ 998244353$ で出力してください。 2行目には、条件を満たす抜き出す方の一例を求め、その時抜き出した $n$ 個の行のindexをスペース区切りで出力して下さい。複数答えがある場合、どれを出力しても正解となります。 #### ●入出力例 ##### 入力例1 ``` 3 7 1 2 3 4 5 6 7 2 3 4 5 6 7 1 3 4 5 6 7 1 2 4 5 6 7 1 2 3 5 6 7 1 2 3 4 6 7 1 2 3 4 5 7 1 2 3 4 5 6 1 2 3 4 5 7 6 1 3 4 5 6 7 2 1 4 5 6 7 3 2 1 5 6 7 4 2 3 1 6 7 5 2 3 4 1 7 6 2 3 4 5 1 7 2 3 4 5 6 5 4 5 1 2 3 3 5 2 4 1 1 2 3 4 5 5 2 4 1 3 3 4 5 1 2 2 3 4 5 1 1 3 5 2 4 4 1 3 5 2 2 4 1 3 5 5 1 2 3 4 6 2 3 4 5 6 1 3 1 2 6 4 5 6 1 2 3 4 5 5 6 1 3 2 4 4 3 6 5 2 1 5 6 1 2 3 4 4 5 6 1 2 3 3 4 5 6 1 2 1 2 3 4 5 6 2 5 4 1 6 3 3 2 5 4 1 6 1 4 3 6 5 2 ``` ##### 出力例1 ``` 1 1 2 3 4 5 6 7 2 1 3 5 6 10 4 1 3 6 7 8 9 ``` 2番めのテストケースでは、[1,3,5,6,10],[2,4,7,8,9] の2通りの抜き出し方がありますが、そのどちらを出力しても正解になります。 ## ◎ヒント ### ヒントに関しての諸注意各問題のポイントをヒントという形で紹介しています。コンテスト中であっても、詰まってしまったらぜひご確認ください。コンテスト後に復習する際に活用していただいてもいいです。序盤の問題に関しては一部実装を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. Remove Duplicates :::spoiler **ヒント1** 一番右に現れるかどうかはどのようにして判定できるでしょうか。 ::: :::spoiler **ヒント2** その要素よりも右に同じ値が現れないことを確認すればよいです。 ::: :::spoiler **ヒント3** 一番右に現れる要素であるとわかったらリストやvectorに加え記録しておきましょう。 ::: #### 実装のステップ (C++/python) :::spoiler **入力の受け取り** ```python= #python n = int(input()) a = list(map(int, input().split())) ``` ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } } ``` ::: :::spoiler **ヒント2の実装** 2重ループのようにして実装します。フラグ変数を持って、見つけたらフラグを立てましょう。 ```python= #python for i in range(n): found = False for j in range(i + 1, n): if a[i] == a[j]: found = True if not found: # 同じ数値が右にないとき # ここに処理を書く ``` ```cpp= // C++ for (int i = 0; i < n; i++) { bool found = false; for (int j = i + 1; j < n; j++) { if (a[i] == a[j]) { found = true; } } if (!found) { // ここに処理を書く } } ``` ::: :::spoiler **ヒント3の実装** 答えを記録するリストやvectorを用意して、次のようにして記録できます。 ```python= #python res = [] # x を記録したいとき res.append(x) ``` ```cpp= //C++ vector<int> res; // x を記録したいとき res.push_back(x); ``` ::: ### ◎B. File Name :::spoiler **ヒント1** x以外は削除しなくて良いです。 ::: :::spoiler **ヒント2** 実際に消す操作を実装するのではなく、どのような条件を満たす要素を消せばよいのかを考えましょう。 ::: :::spoiler **ヒント3** $s_i = s_{i+1} = s_{i+2} = \rm{'x'}$ となるような全ての $i$ を削除すればよいです。 ::: #### 実装のステップ（C++/python) :::spoiler **全体の実装方針** 以下のようなコードを書くことで実現できます。 1. 入力を受け取る。 2. 変数ans を用意しておき、0にセットしておく。 3. 各 $i(1 \le i \le n-2)$ について、$s_i = s_{i+1} = s_{i+2} = \rm{'x'}$ を満たすか判定し、満たすならば ansに1を加える。 4. ansを出力する。 ::: :::spoiler **入力の受け取り** ```python= #python n = int(input()) s = input() ``` ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int n; string s; cin >> n; cin >> s; } ``` ::: :::spoiler **繰り返し処理の実装** ```python= #python ans = 0 for i in range(n-2): if 条件式: #s[i]=s[i+1]=s[i+2]='x'を満たすか？の条件式を書く ans += 1 ``` ```cpp= //C++ int ans = 0; for (int i=0; i < n-2 ; i++){ if (条件式){ //s[i]=s[i+1]=s[i+2]='x'を満たすか？の条件式を書く ans++; } } ``` ::: :::spoiler **条件式を書く際の注意** python,C++の両方で、等しいかどうかを条件式内で判定する際は ==(イコール2個)を使用します。=(イコール1個)は代入を意味するので注意してください。また、A=B=C か？を判定したい場合、pythonでは ```python= #python if A==B==C: #内容 ``` のように書けますが、C++では条件式を分割してandでつなげる必要があることに注意してください。具体的には、 ```cpp= //C++ if (A==B && B==C){ //内容 } ``` のように書く必要があります。 ::: ### ◎C. Letters :::spoiler **ヒント0** C++を使用している場合、intだとオーバーフローします。 ::: :::spoiler **ヒント1** 何番目の寮の部屋なのかはどのようにして見つけられるでしょうか。 ::: :::spoiler **ヒント2** それぞれの寮の最後の部屋の部屋番号を計算しておくと利用できます。 ::: :::spoiler **ヒント3** 手紙に書かれた部屋番号が昇順であることを利用できます。利用しない場合は二分探索などを使わないと、実行時間制限に引っかかる可能性があります。 ::: :::spoiler **ヒント4** 寮を特定した後、その寮での部屋番号はどのように計算できるでしょうか。 ::: #### 実装の方針 (C++/Python) :::spoiler **全体の実装方針** 1. 各寮について、最後の部屋の部屋番号がすべての寮を通して何番かを計算します。 2. 最初の寮から見ていき、手紙に書かれた番号が最後の部屋の番号以下であればその寮の部屋です。 3. 部屋番号を計算します。 4. 次の手紙の寮は、さっきの手紙の寮以降の部屋が宛先になっていることを利用して効率的に探します。 ::: :::spoiler **入力の受け取り** ```python= #python n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) ``` ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<long long> a(n), b(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; } ``` ::: :::spoiler **最後の部屋の番号の計算** ```python= #python last_room = [0 for _ in range(n + 1)] for i in range(n): last_room[i + 1] += a[i] + last_room[i] ``` ```cpp= //C++ vector<long long> last_room(n + 1, 0); for (int i = 0; i < n; i++) { last_room[i + 1] += a[i] + last_room[i]; } ``` ::: :::spoiler **調べる寮の管理** ```python= #python dormitory = 0 for i in range(m): while b[i] > last_room[dormitory]: dormitory += 1 # これで dormitory が 0-indexed で i番目の手紙の宛先の寮の番号になる ``` ```cpp= //C++ int dormitory = 0; for (int i = 0; i < m; i++) { while (b[i] > last_room[dormitory]) { dormitory++; } } ``` ::: ### ◎D. Almost Arithmetic Progression :::spoiler **ヒント1** 数学的に解決するのは難しいです。 ::: :::spoiler **ヒント2** 等差数列は、1項目と2項目が決まれば、残りが全て自動的に決定します。 ::: :::spoiler **ヒント3** 操作後、$b_0$,$b_1$の状態としてあり得るのはそれぞれ 1増えた・変化なし・1減ったの3通りしかありえないので、操作後の$b$ の最初の2項として考えられるのは最大でも9通りしかありえません。 ::: :::spoiler **ヒント4** 最初の2項を9通り全探索しましょう。 ::: ### ◎E. Bus Video System :::spoiler **ヒント1** あるバス停までに、最初のバス停から何人増減したかを計算しましょう。 ::: :::spoiler **ヒント2** 5人減っていた場合、最初のバスには最低5人は乗っている必要があります。 ::: :::spoiler **ヒント3** 上限についても同様のことが言えます。 ::: ### ◎F. Mentors :::spoiler **ヒント1** 愚直に全てのペアを調べると、計算回数が $10^{10}$回を超え、TLEとなります。 ::: :::spoiler **ヒント2** うまく値の足し引きをすることで、効率よく答えを出す方法を考えましょう。 ::: :::spoiler **ヒント3** まず、エンジニアをスキルが小さい順に並べ、小さい方から見るのが効果的です。 ::: :::spoiler **ヒント4** 人$i$ よりも、スキルが小さい人の数を求める方法を考えましょう。 ::: :::spoiler **ヒント5** 更にそこから、喧嘩をしている人数を引きましょう。 ::: ### ◎G. Petya's Exams :::spoiler **ヒント1** すべての試験に合格する必要があり、合格できる試験数の最大化ではありません。 ::: :::spoiler **ヒント2** ある日に対策する試験は、どのような試験だと損をしないでしょうか。 ::: ### ◎H. AquaMoon and Permutations :::spoiler **この問題について** この問題は、物足りない方向けに設置した超難問です。ヒントはありませんが、是非挑戦してみてください！！ ::: ## ◎解説 ### ◎A. Remove Duplicates ヒントに載せた実装例を組み合わせ、記録する処理と出力部分を加えると解くことができます。ここでは解答例を掲載します。他の解法として、set で既出かどうかを管理しながら右から見ていくことでも解けます。 :::spoiler **Pythonでの解答例** ```python= #python n = int(input()) a = list(map(int, input().split())) res = [] for i in range(n): found = False for j in range(i + 1, n): if a[i] == a[j]: found = True if not found: res.append(a[i]) print(len(res)) for x in res: print(x, end=' ') print() ``` ::: :::spoiler **C++での解答例** ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<int> res; for (int i = 0; i < n; i++) { bool found = false; for (int j = i + 1; j < n; j++) { if (a[i] == a[j]) { found = true; } } if (!found) { res.push_back(a[i]); } } cout << res.size() << endl; for (int i = 0; i < res.size(); i++) { cout << res[i] << " "; } cout << endl; } ``` ::: ### ◎B. File Name すべきこと、実装方針についてはヒントに掲載をしたのでまずそちらをご覧ください。ここでは解答例を掲載します。 :::spoiler **pythonでの解答例** ```python= #python n = int(input()) s = input() ans = 0 for i in range(n-2): if s[i] == s[i+1] == s[i+2] == "x": ans += 1 print (ans) ``` ::: :::spoiler **C++での解答例** ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int n; string s; cin >> n; cin >> s; int ans = 0; for (int i=0; i < n; ++i){ if (s[i]=='x' && s[i+1]=='x' && s[i+2]=='x'){ ans++; } } cout << ans << '\n'; } ``` ::: ### ◎C. Letters ヒントに掲載した実装例を組み合わせ、部屋番号を計算する処理を追加すると解くことができます。ここでは解答例を掲載します。 :::spoiler **Pythonでの解答例** ```python= #python n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) last_room = [0 for _ in range(n + 1)] for i in range(n): last_room[i + 1] += a[i] + last_room[i] dormitory = 0 for i in range(m): while b[i] > last_room[dormitory]: dormitory += 1 print(dormitory, b[i] - last_room[dormitory - 1]) ``` ::: :::spoiler **C++での解答例** ```cpp= //C++ #include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<long long> a(n), b(m); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; vector<long long> last_room(n + 1, 0); for (int i = 0; i < n; i++) { last_room[i + 1] += a[i] + last_room[i]; } int dormitory = 0; for (int i = 0; i < m; i++) { while (b[i] > last_room[dormitory]) { dormitory++; } cout << dormitory << " " << b[i] - last_room[dormitory - 1] << endl; } } ``` ::: ### ◎D. Almost Arithmetic Progression 等差数列は最初の2項が決まれば残りが全て決まるという性質を利用します。操作後の $b_1$ の状態は、1増える・変化なし・1減るの3通りです。 $b_2$ にも同じことが言えます。つまり、最初の2項の状態は掛け合わせて9通りしかありえません。この9通り全てを決め打ち全探索します。より具体的には、以下のように処理を行います。 1. 操作後の$b$の最初の2項の状態を決め打ちする。 2. 最初の2項から、等差数列全体を構成する。 3. $b$ からその等差数列が構成可能か調べる。(各項の差の絶対値が1以下か調べる) 4. 構成可能ならば、操作回数(変化した要素の個数)を求める。 ### ◎E. Bus Video System 最初のバス停からの増減を各バス停について計算し、その最小値と最大値を記録します。例えば、それぞれを $(B_{min}, B_{max})$ とすると、最初のバス停では $0$ なので $B_{min} \leq 0$ です。すると、最初に乗っている人数は最低でも $-B_{min}$ 人であって、最大でも $w - B_{max}$ 人であることがわかります。よって、通り数は基本的には $(w - B_{max}) - (-B_{min}) + 1$ になります。$w - B_{max} < -B_{min}$ であれば、0通りになります。 ### ◎F. Mentors 愚直に全てのペアを試すと、計算回数が $10^{10}$ を超え、TLEするので高速に解く必要があります。まず、人をスキルが小さい順に並べ替えます。人$i$よりもスキルが小さい人の数は、「直前までに見た人数」-「直前までに見たスキルが$r_i$の人数」で求められます。前者は単純にカウンタを使ってカウントすることで、後者はC++のmap・pythonのdictなどを利用することで求められます。ここから更に、「人$i$よりもスキルが低い」かつ「$i$と喧嘩している」人数を引くことで答えとなります。これは予め喧嘩のデータを読み込んだ際に処理しておくことができます。 ### ◎G. Petya's Exams すべての試験に合格する必要があるので、試験の準備はすべての試験について必ず行うことになります。このとき、試験日が最も近い試験の対策をすると損をしないことがわかります。例えば、ある条件を満たすスケジュールがあるときに、2つの試験 $i, j$ で $d_i < d_j$ かつ $j$ の準備を $i$ の準備よりも先に行っているとき、$j$ の準備が $s_i$ 以降であればこの2つの準備を入れ替えても条件を満たします。よって、今準備するべき日数が残っている試験について、もっとも試験日が近いものを管理することができれば、貪欲に取っていくことで解くことができます。 ### ◎H. AquaMoon and Permutations https://spd-9x2.hatenablog.com/entry/2022/02/26/060722 を参照してください。