AtCoder Beginner Contest 259 メモ(A-D)
今回の結果
3AC
3回ぶりにC問題をACできた。
今回はB,Dと数学の知識がいる問題があって、調べながら解いている分時間はかかった。
ランレングス圧縮ってC問題で出てくるんすね。
A - Growth Record
Difficulty: 34
問題文
高橋君は
また、以下のことが分かっています。
- 高橋君は
歳の誕生日(生まれた当日)から0 歳の誕生日までの間、毎年身長がX cmずつ伸びた。より厳密に書くと、D それぞれに対し、i=1,2,…,X 歳の誕生日からi−1 歳の誕生日までの間に身長がi cm伸びた。D - 高橋君は
歳の誕生日からX 歳の誕生日までの間、身長が変化していない。N
高橋君の
制約
0≤M<N≤100 1≤X≤N 1≤T≤200 1≤D≤100 - 高橋君の
歳の誕生日の時の身長は0 cm以上である1 - 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを整数として出力せよ。
入出力例
入力例 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は身長が変化していない時か、変化している時かで分けてそれぞれの処理・計算を書く。
-
の場合M \ge T
身長が変化していない=N才の誕生日の身長と同じ=T が答え -
の場合M < T
年間、身長が変化していることになるので、T-M が答えT-(X-M) \times D
B - Counterclockwise Rotation
Difficulty: 180
問題文
制約
1000≤a,b≤1000 1≤d≤360 - 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
求めるべき点を
なお、各出力について、解との絶対誤差または相対誤差が
入出力例
入力例 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
参加中に考えたこと
シンプルに座標の計算をするだけ。
と言っても三角関数は覚えてないので数学の座標回転について調べて、その通りにプログラムを書けば終わり。
数式としては、
になる。
radianへの変換はやったことがあるのでそこは過去のソースから持ってきた。
C - XX to XXX
Difficulty: 451
問題文
英小文字からなる
において同じ文字が S 文字連続しているところの間に、その文字と同じ文字を 2 つ挿入する。 すなわち、下記の 1 つの手順からなる操作を行う。 3
- 現在の
の長さを S とし、 N とする。 S=S_1 S_2 \cdots S_N 以上 1 以下の整数 N−1 であって、 i を満たすものを S_i =S_i+1 つ選択する。(ただし、そのような 1 が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。) i の S 文字目と i 文字目の間に文字 i+1 を S_i (=S_i+1) つ挿入する。その結果、 1 は長さ S の文字列 N+1 となる。 S_1S_2 \cdots S_iS_iS_{i+1} \cdots S_N
制約
-
とS はそれぞれ英小文字からなる長さT 以上2 以下の文字列2×10^5
入力
入力は以下の形式で標準入力から与えられる。
出力
Yes
を、そうでない場合は No
を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入出力例
入力例 1
abbaac
abbbbaaac
出力例 1
Yes
入力例 2
xyzz
xyyzz
出力例 2
No
参加中に考えたこと
操作内容を簡潔にすると、「Sの中の2文字以上連続する部分は3文字以上にできる」と言える。
Sの左から順に何の文字が何文字続くか、というのを持っていれば判定ができそう。
これってランレングス圧縮であることに気づき、S,Tをランレングス圧縮の形式で持ち、以下のチェックをする。
- SとTで出てくる文字列の順番が同じである
- 各文字の繰り返しの回数について、以下の条件を満たす
a. S側とT側の数が同じ
b. S<T の場合は Sの数が2つ以上である
ランレングス圧縮については参考になるコードを手元から探せなかったので、これもネットで検索。
1回WAが出たが、修正も出来てACまでできた。
考察・感想
制約に、
と S はそれぞれ英小文字からなる T
とあるのに、
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
と書かれているのが分からなかった。
言語によってはWAになるケースがあるのだろうか?
D - Circumferences
Difficulty: 947
問題文
制約
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 - 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
出力
点 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つの円が交差・隣接しているかを判断する方法をネットで探すが、調べて見つけた方法がちょっと手間がかかりそうだったので一旦置いといて、ゴールまでに必要な流れを考える。
- 点Sと点Tがどの円の円周上の点かを調べる
- N個ある各円についてどの円と交差または隣接しているかを調べる(
なので全探索でも問題ない)N<3000 - 点Sがある円からDFSでTに辿り着けるかを調べる
やることが多いのと、調べないと分からない部分が多いのでこれは間に合わない。。
考察・感想
この問題からは得られた知見が多い。
まず、2つの円の位置関係を調べるには円周と中心の座標を使って以下の5つのパターンに分けられるということ。
- 離れている
(d > r1 + r2) - 外接する
(d = r1 + r2) - 2点で交わる
(|r1-r2| < d < r1 + r2) - 内接する
(d = |r1 - r2|) - 一方の円の内部にもう一方の円がある
(d < |r1-r2|)
この記事あたりを参考にした。
次に、ある点が円周の上にあるかどうかは、
最後に、小数を使うと誤差が生じることがあるので整数で処理できるものはなるだけ整数で処理をすること。
今回の場合ではある点が円周の上にあるかどうかを調べるところで、
Discussion