🥾

AtCoder Beginner Contest 259 メモ(A-D)

2022/07/11に公開

今回の結果

3AC

3回ぶりにC問題をACできた。
今回はB,Dと数学の知識がいる問題があって、調べながら解いている分時間はかかった。
ランレングス圧縮ってC問題で出てくるんすね。

A - Growth Record

https://atcoder.jp/contests/abc259/tasks/abc259_a

Difficulty: 34

問題文

高橋君は N 歳の誕生日を迎えました。この時の彼の身長は T cmです。
また、以下のことが分かっています。

  • 高橋君は 0 歳の誕生日(生まれた当日)から X 歳の誕生日までの間、毎年身長が D cmずつ伸びた。より厳密に書くと、i=1,2,…,X それぞれに対し、i−1 歳の誕生日から i 歳の誕生日までの間に身長が D cm伸びた。
  • 高橋君は X 歳の誕生日から N 歳の誕生日までの間、身長が変化していない。

高橋君の M 歳の誕生日の時の身長が何cmだったかを求めてください。

制約

  • 0≤M<N≤100
  • 1≤X≤N
  • 1≤T≤200
  • 1≤D≤100
  • 高橋君の 0 歳の誕生日の時の身長は 1 cm以上である
  • 入力はすべて整数

入力

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

N M X T D

出力

答えを整数として出力せよ。

入出力例

入力例 1

38 20 17 168 3

出力例 1

168

入力例 2

1 0 1 3 2

出力例 2

1

入力例 3

100 10 100 180 1

出力例 3

90

参加中に考えたこと

変数が5つもあるのでメモを取って整理する。
MとTの関係から、Mは身長が変化していない時か、変化している時かで分けてそれぞれの処理・計算を書く。

  1. M \ge T の場合
    身長が変化していない=N才の誕生日の身長と同じ=T が答え

  2. M < T の場合
    T-M年間、身長が変化していることになるので、T-(X-M) \times D が答え

B - Counterclockwise Rotation

https://atcoder.jp/contests/abc259/tasks/abc259_b

Difficulty: 180

問題文

x 軸の正の向きが右、y 軸の正の向きが上であるような xy 座標平面において、点 (a,b) を原点を中心として反時計回りに d 度回転させた点を求めてください。

制約

  • 1000≤a,b≤1000
  • 1≤d≤360
  • 入力はすべて整数

入力

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

a b d

出力

求めるべき点を (a^′,b^′) とするとき、 a^′b^′ をこの順に空白区切りで出力せよ。
なお、各出力について、解との絶対誤差または相対誤差が 10^{−6} 以下であれば正解として扱われる。

入出力例

入力例 1

2 2 180

出力例 1

-2 -2

入力例 2

5 0 120

出力例 2

-2.49999999999999911182 4.33012701892219364908

入力例 3

0 0 11

出力例 3

0.00000000000000000000 0.00000000000000000000

入力例 4

15 5 360

出力例 4

15.00000000000000177636 4.99999999999999555911

入力例 5

-505 191 278

出力例 5

118.85878514480690171240 526.66743699786547949770

参加中に考えたこと

シンプルに座標の計算をするだけ。
と言っても三角関数は覚えてないので数学の座標回転について調べて、その通りにプログラムを書けば終わり。
数式としては、
(a^′,b^′) = (a \space cos(d) - b \space sin(d), \enspace a \space sin(d) + b \space cos(d))
になる。
radianへの変換はやったことがあるのでそこは過去のソースから持ってきた。

C - XX to XXX

https://atcoder.jp/contests/abc259/tasks/abc259_c

Difficulty: 451

問題文

英小文字からなる 2 つの文字列 S,T が与えられます。 次の操作を好きな回数( 0 回でも良い)行うことで、ST と一致させることができるかを判定してください。

S において同じ文字が 2 文字連続しているところの間に、その文字と同じ文字を 1 つ挿入する。 すなわち、下記の 3 つの手順からなる操作を行う。

  1. 現在の S の長さを N とし、S=S_1 S_2 \cdots S_N とする。
  2. 1 以上 N−1 以下の整数 i であって、S_i =S_i+1 を満たすものを 1 つ選択する。(ただし、そのような i が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。)
  3. Si 文字目と i+1 文字目の間に文字 S_i (=S_i+1)1 つ挿入する。その結果、S は長さ N+1 の文字列 S_1S_2 \cdots S_iS_iS_{i+1} \cdots S_N となる。

制約

  • ST はそれぞれ英小文字からなる長さ 2 以上 2×10^5 以下の文字列

入力

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

S
T

出力

ST と一致させることができる場合は Yes を、そうでない場合は No を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入出力例

入力例 1

abbaac
abbbbaaac

出力例 1

Yes

入力例 2

xyzz
xyyzz

出力例 2

No

参加中に考えたこと

操作内容を簡潔にすると、「Sの中の2文字以上連続する部分は3文字以上にできる」と言える。
Sの左から順に何の文字が何文字続くか、というのを持っていれば判定ができそう。
これってランレングス圧縮であることに気づき、S,Tをランレングス圧縮の形式で持ち、以下のチェックをする。

  1. SとTで出てくる文字列の順番が同じである
  2. 各文字の繰り返しの回数について、以下の条件を満たす
    a. S側とT側の数が同じ
    b. S<T の場合は Sの数が2つ以上である

ランレングス圧縮については参考になるコードを手元から探せなかったので、これもネットで検索。
1回WAが出たが、修正も出来てACまでできた。

考察・感想

制約に、

ST はそれぞれ英小文字からなる

とあるのに、

ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

と書かれているのが分からなかった。
言語によってはWAになるケースがあるのだろうか?

D - Circumferences

https://atcoder.jp/contests/abc259/tasks/abc259_d

Difficulty: 947

問題文

xy -平面上の N 個の円が与えられます。 i=1,2,…,N について、i 番目の円は点 (x_i,y_i) を中心とする半径 r_i の円です。

N 個の円のうち少なくとも 1 つ以上の円の円周上にある点のみを通って、点 (s_x,s_y) から点 (t_x,t_y) に行くことができるかどうかを判定してください。

制約

  • 1≤N≤3000
  • −10^9≤x_i,y_i≤10^9
  • 1≤r_i ≤10^9
  • (s_x ,s_y)N 個の円のうち少なくとも 1 つ以上の円の円周上にある
  • (t_x ,t_y)N 個の円のうち少なくとも 1 つ以上の円の円周上にある
  • 入力はすべて整数

入力

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

N
s_x s_y t_x t_y
x_1 y_1 r_1
x_2 y_2 r_2
\vdots
x_N y_N r_N

出力

(s_x,s_y) から点 (t_x,t_y) に行くことができる場合は Yes を、そうでない場合は No を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。

入出力例

入力例 1

4
0 -2 3 3
0 0 2
2 0 2
2 3 1
-3 3 3

出力例 1

Yes

入力例 2

3
0 1 0 3
0 0 1
0 0 2
0 0 3

出力例 2

No

参加中に考えたこと

今までのD問題に比べて数学の知識が必要そう。
まずN個ある円の関係性を調べるところから。
2つの円が交差・隣接しているかを判断する方法をネットで探すが、調べて見つけた方法がちょっと手間がかかりそうだったので一旦置いといて、ゴールまでに必要な流れを考える。

  1. 点Sと点Tがどの円の円周上の点かを調べる
  2. N個ある各円についてどの円と交差または隣接しているかを調べる( N<3000 なので全探索でも問題ない)
  3. 点Sがある円からDFSでTに辿り着けるかを調べる

やることが多いのと、調べないと分からない部分が多いのでこれは間に合わない。。

考察・感想

この問題からは得られた知見が多い。
まず、2つの円の位置関係を調べるには円周と中心の座標を使って以下の5つのパターンに分けられるということ。

  1. 離れている (d > r1 + r2)
  2. 外接する (d = r1 + r2)
  3. 2点で交わる (|r1-r2| < d < r1 + r2)
  4. 内接する (d = |r1 - r2|)
  5. 一方の円の内部にもう一方の円がある (d < |r1-r2|)

この記事あたりを参考にした。
https://qiita.com/tydesign/items/7cb4d189451095b4d667
https://manabitimes.jp/math/745

次に、ある点が円周の上にあるかどうかは、 (x_i-p_x)^2 + (y_i-p_y)^2 = ri^2 を満たしているかで判定ができること。

最後に、小数を使うと誤差が生じることがあるので整数で処理できるものはなるだけ整数で処理をすること。
今回の場合ではある点が円周の上にあるかどうかを調べるところで、\sqrt{(x_i-p_x)^2 + (y_i-p_y)^2} = ri としてdouble型にするとWAすることがある。

Discussion