ABC467参加記

はじめに

こんにちは。 Caffeineholic です。

冷房をガンガンに効かせて記事を書いていますが、モチベーションとレートまで冷えてしまわないかが心配なところです。休日は生活サイクルが乱れがちで、朝まで作業して昼に寝て夕方に起きてまた作業する、なんて日が珍しくなくなってきています。昼寝って夏の季語なんですって。変なの。最近はADTで問題を解いたり、アルゴリズム紹介の記事を読んだりしてはいるのですが、ライブラリをどこまで整えればいいのかがわからず困っています。（グラフClassなんてのを作ろうとしてたけどどうなんだ…？とか）

ICPCやARCに参加して、考察力、実装力を鍛える必要があるなと再認識したので、知らないアルゴリズムの勉強と平行して重い問題を継続的に解いていきたいですね。

今回もABCにrated参加しましたので、各問題について感想と考察の内容を共有できればと思います。皆解くのが早くて、下の結果サマリに私の名前が載りませんね。

結果サマリ

ABC467
WCPC参加人数: 6人
各問題の最速解答者(ペナルティなし):

問題	参加者名	タイム	言語
A	Nsubaru	1:21	Java
B	Twil3	3:48	Rust
C	ShoboiNamae	10:54	C++
D	Twil3	62:44	Rust
E	-	-	-
F	-	-	-
G	-	-	-

今週の出題

A問題

問題ページ: A問題

問題文を表示

問題文

以下の式で計算される値を $BMI[kg/m^2]$ と言います。体重 $[kg] \div$ 身長 $[m] \div$ 身長 $[m]$

日本では、 $BMI$ が $25kg/m^2$ 以上の人は肥満とされます。身長 $H[cm]$ 、体重 $W[kg]$ の人が日本で肥満とされるかどうかを判定してください。

制約

$1 \le H \le 300$
$1 \le W \le 300$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$H \ W$

出力

身長 $H[cm]$ 、体重 $W[kg]$ の人が日本で肥満とされるならば Yes を、そうでないならば No を 1 行で出力せよ。

if文書くだけだな、とパパっと済ませて提出したら、まさかの2WA!! 小数点誤差を避けるために、判定部分に除算が含まれる場合はなるべく式変形して除算を排除しましょうね。計算に使われる値について、身長の単位が入力部分そのままの $[m]$ ではなく $[cm]$ であるところもケアレスミスポイントです。

B問題

問題ページ: B問題

問題文を表示

問題文

高橋君は $N$ 軒の店で買い物をしました。はじめ、高橋君は $10000$ 円持っていました。

$i$ 軒目の店では $A_i$ 円の商品を買って $B_i$ 円支払いました。ここで $A_i \le B_i$ が成り立ちます。そして、 $S_i = \text{"keep"}$ の時、高橋君はお釣りを受け取らず、 $S_i = \text{"take"}$ の場合、お釣りを受け取りました。

高橋君が全ての店でお釣りを受け取っていた場合に比べて損した金額を求めてください。厳密に述べると、高橋君の最終的な所持金を $X$ 円、高橋君が全ての店でお釣りを受け取っていた場合の最終的な所持金を $Y$ 円とした時、 $Y - X$ を求めてください。

制約

$1 \le N \le 100$
$1 \le A_i \le B_i \le 100$
$S_i$ は keep または take
$N, A_i, B_i$ は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1 \ B_1 \ S_1$
$A_2 \ B_2 \ S_2$
$\vdots$
$A_N \ B_N \ S_N$

出力

高橋君が全ての店でお釣りを受け取っていた場合に比べて損した金額を出力せよ。

特に多くを語る必要はない問題です。

全ての店でお釣りを受け取っていた場合に比べて損した金額は、受け取らなかったお釣りの合計代金そのままです。 $S_{i}$ が keep であるときの $B_{i} - A_{i}$ の総和が答えになりますね。

C問題

問題ページ: C問題

問題文を表示

問題文

※ C 問題の問題文は E 問題と同じです。制約のみが異なります。

$0$ 以上 $M-1$ 以下の整数からなる整数列 $A=(A_1,A_2,\ldots,A_N)$ 、 $B=(B_1,B_2,\ldots,B_{N-1})$ が与えられます。 $A,B$ の長さはそれぞれ $N, N-1$ です。

$A$ に対して以下の操作を好きな回数行うことができます。

$1$ 以上 $N$ 以下の整数 $i$ を $1$ つ選び、 $A_i$ に $1$ を加える。

以下の条件を満たすようにするために必要な操作回数の最小値を求めてください。なお、問題の制約下では、必ず条件を満たすようにできることが証明できます。

$i=1,2,\ldots,N-1$ について、 $A_i+A_{i+1}$ を $M$ で割った余りは $B_i$ に等しい。

制約

$2 \le N \le 2 \times 10^5$
$M = 2$
$0 \le A_i \le M-1$
$0 \le B_i \le M-1$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N \ M$
$A_1 \ A_2 \ \ldots \ A_N$
$B_1 \ B_2 \ \ldots \ B_{N-1}$

出力

答えを 1 行で出力せよ。

少し苦労したC問題です。問題文を要約すると、「 $B$ の $i$ 番目は $A$ の $i$ 番目と $i+1$ 番目の要素について、和を取って $2$ で割ったあまりを表している」という状態にするために、ある要素に1加算するという「操作」を何回しなければいけないか求めよ、ということです。前提として、 $M=2$ であることから、各要素に対する「操作」の回数は $0$ または $1$ です。

最初に考えたことは、貪欲に配列 $A$ の要素を書き換えて行くことで最小の操作回数を達成できないかということでした。

最初に考えた貪欲解（不正解）

$A$ の要素を前から2つずつ見ていき、その2つの和を2で割ったあまりが対応する位置のBの要素と異なれば、見ている要素のうち右側に $1$ を足す。足した数を保存しておき、操作回数として出力する。また、後ろから2つずつ見ていくという処理でもう一度 ( 見ている要素のうち左側と言い換えて ) 操作回数を求めなおし、良かったほうを出力する。

これでは両端の要素に「操作」を行うのが最適である場合を考慮できていません。また見ている2つの要素のうちどちらを選択するのが最適なのかを毎回考えるようにするは、 $O(2^N)$ かかってしまいます。ここまでから、 端の値が固定されていた場合 を考えると前から順に処理をしていくことで「操作」をするべき項は一意に定まるということに気づけました。ということは、 $A_{1}=0$ の場合と $A_{1}=0$ の場合両方について、 $A$ の $i$ 番目までが決定している前提で $A$ の $i+1$ 番目に「操作」するべきか判断するという処理を行えばよいということになります。

D問題

問題ページ: D問題

問題文を表示

問題文

$xy$ 平面上に以下の条件を全て満たす 2 個の円 $C_1, C_2$ は存在しますか？ただし $C_1, C_2$ は同一である可能性があります。

異なる 2 点 $(P_x, P_y), (Q_x, Q_y)$ は $C_1$ の円周上にある。
異なる 2 点 $(R_x, R_y), (S_x, S_y)$ は $C_2$ の円周上にある。
$C_1$ と $C_2$ は中心が一致する。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 5 \times 10^4$
$-10^9 \le P_x, P_y, Q_x, Q_y, R_x, R_y, S_x, S_y \le 10^9$
$(P_x, P_y) \neq (Q_x, Q_y)$
$(R_x, R_y) \neq (S_x, S_y)$
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各テストケース $case_t$ は以下の形式で与えられる。

$P_x \ P_y \ Q_x \ Q_y \ R_x \ R_y \ S_x \ S_y$

出力

$T$ 行出力せよ。 $t$ 行目には $t$ 番目のテストケースの答えを出力せよ。各テストケースでは、条件を全て満たす 2 個の円 $C_1, C_2$ が存在する場合は Yes を、存在しない場合は No を出力せよ。

D問題です。要約すると、

2つの点 $P$ と $Q$ が円 $C_{1}$ の周上にある。2つの点 $R$ と $S$ が円 $C_{2}$ の周上にある。このとき $C_{1}$ と $C_{2}$ の中心が一致するかどうかを判定せよという問題です。

少し数学の知識が問われるものになっていましたが、手元に以下の図を書けたか否かで大きく解像度が変わったのではないかと思います。

$C_{1}$ の中心は赤い線、 $C_{2}$ の中心は青い線の上にしかなり得ないので、その直線の方程式を求めて交差しているかを判定すればよいです。

E問題

問題ページ: E問題

問題文を表示

問題文

※ E 問題の問題文は C 問題と同じです。制約のみが異なります。

$0$ 以上 $M-1$ 以下の整数からなる整数列 $A=(A_1,A_2,\ldots,A_N)$ 、 $B=(B_1,B_2,\ldots,B_{N - 1})$ が与えられます。 $A,B$ の長さはそれぞれ $N, N-1$ です。

$A$ に対して以下の操作を好きな回数行うことができます。

$1$ 以上 $N$ 以下の整数 $i$ を $1$ つ選び、 $A_i$ に $1$ を加える。

$i=1,2,\ldots,N-1$ について、 $A_i+A_{i+1}$ を $M$ で割った余りは $B_i$ に等しい。

制約

$2 \le N \le 2 \times 10^5$
$3 \le M \le 10^9$
$0 \le A_i \le M-1$
$0 \le B_i \le M-1$
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N \ M$
$A_1 \ A_2 \ \ldots \ A_N$
$B_1 \ B_2 \ \ldots \ B_{N-1}$

出力

答えを 1 行で出力せよ。

難しかったですね。解説を読んでも実装できる気がしませんでした。

最後に

E問題が難しかったおかげで、時間のかかった4完でもレートは増えています。 A問題のペナルティがなければもっと…といったところでしょうか。Caffeineholicでした。ではまた。