【AtCoder】ABC178 (A~E) 参戦記

3ヶ月ぶりにコンテストに出た

いい出来だったので記録に残す

結果

順位:9661人中1930位

得点:1500点 (4)

ペナルティ付き最終解答時間:94:25

パフォーマンス:1219

※()内の数字はWAの回数

各問題の結果
得点 WA回数 解答時点での経過時間
A 100点 0 1:00
B 200点 0 3:04
C 300点 1 8:37
D 400点 0 29:50
E 500点 3 74:25
F 600点 - -

レート変化

875→919 (+44)

f:id:monhime:20200914074552j:plain:w400

f:id:monhime:20200914074557j:plain:w400

5完したけど問題自体が易化してるので、そこまでパフォーマンス高くない

とりあえず及第点は取れてるしこの調子で行きたい

解答

A-Not

A - Not

問題要約

0以上1以下の整数$x$が与えられる。$x$が0なら1を、1なら0を出力せよ。

解答

Shortest狙ってる訳でもないので普通に書いた

コードを見る(クリックして下さい)

ABC178 A問題 解答

 

Submission #16672266 - AtCoder Beginner Contest 178

B-Product Max

B - Product Max

問題要約

整数$a,\,b,\,c,\,d$が与えられる。$a\leq x\leq b,\,c\leq y\leq d$を満たす整数$x,\,y$について、$x\times y$の最大値を求めよ。

解答

4つの整数は正とは限らない。

条件分岐はややこしいしミスりそうなので、解答としてあり得る4通り ($ a\times b,\,a\times c,\,b\times c,\,b\times d $) の最大値を求めた。

コードを見る(クリックして下さい)

ABC178 B問題 解答

 

Submission #16677950 - AtCoder Beginner Contest 178

C-Ubiquity

C - Ubiquity

問題要約

長さ$N$の整数の数列で、以下の条件を満たすものはいくつあるか。$10^9 +7$ で割った余りを出力せよ。

・$0\leq A_i \leq 9$

・$A_i=0 $なる$ i $が存在する

・$A_i=9 $なる$ i $が存在する

解法

長さ$ N$で、各要素が$a$以上$b$以下 ($a\leq b $) の整数の数列の数を$S_{0-9}$と表すと、答えは$ S_{0-9}-S_{1-9}-S_{0-8}+S_{1-8} $

$S_{0-9}=10^N$, $ S_{1-9}=S_{0-8}=9^N $, $ S_{1-9}=8^N $より、求める場合の数は$10^N-2*9^N+8^N$。

解答

答えは$10^9+7$で割った余りを出力するので、pow()関数を用いる。 各項について余りを求めた後、全体で余りを求め直すことを忘れないように。(筆者はそこで1WAした。)

コードを見る(クリックして下さい)

ABC178 C問題 解答

 

Submission #16685114 - AtCoder Beginner Contest 178

D-Redistribution

D - Redistribution

問題要約

整数$ S $が与えられる。全ての項が3以上の整数で、その総和が$ S $ であるような数列はいくつあるか。答えを$10^9+7$で割った余りを求めよ。

解法

条件を満たす数列の項数は最大$\lfloor \frac{S}{3}\rfloor$。

項数が$ k\,(1\leq k \leq \lfloor \frac{S}{3}\rfloor) $のときを考える。全ての要素が3である数列と比較して、総和は$S-3k$だけ多くなる。これより、項数$ k $のときの数列の場合の数は、$S-3k$を重複を許して$k$個にグループ分けする仕方の総数$ \frac{(S-2k-1)!}{(S-3k)!(k-1)!} = {}_{S-2k-1} C_{S-3k} = {}_{S-2k-1} C_{k-1} $に等しい($S-3k$個のボールと$k-1$個の仕切りの並べ方を考える)。

以上より、求める場合の数は $ \sum_{k=1} ^{k=\lfloor \frac{S}{3}\rfloor} {}_{S-2k-1} C_{k-1} $。

解答

組合せは逆元使って余りを高速で求めるいつものライブラリを使う。

各$k$について、余りを求めながら答えを更新していく。

コードを見る(クリックして下さい)

ABC178 D問題 解答

 

Submission #16733716 - AtCoder Beginner Contest 178

E-Dist Max

E - Dist Max

問題要約

二次元平面上に$ N$ 個の点があり、$ i $番目の点の座標は$(x_i,\,y_i)$である。同じ座標に複数の点があることもある。異なる2点間のマンハッタン距離として考えられる最大の値はいくつか。

解法

$i$番目の点と$j$番目の点とのマンハッタン距離は$|x_i-x_j|+|y_i-y_j|$で表され、ある点からマンハッタン距離が等しい点の集合は45°または-45°の直線上に並ぶ。

よって、ある点Aと点Bの組み合わせが$ N$個の点の集合の中で最も大きいマンハッタン距離をとるとき、その2点は「-45°の直線$y=-x+k$を上 ($k=\infty$) から下げていったときに最初に当たる点と下 ($k=-\infty$) から上げていったときに最初に当たる点」または「45°の直線$y=x+k$を上 ($k=\infty$) から下げていったときに最初に当たる点と下 ($k=-\infty$) から上げていったときに最初に当たる点」のどちらかになる。

つまり、$ N$個の点の集合に対し、「-45°の直線$y=-x+k$を上 ($k=\infty$) から下げていったときに最初に当たる点と下 ($k=-\infty$) から上げていったときに最初に当たる点とのマンハッタン距離」と「45°の直線$y=x+k$を上 ($k=\infty$) から下げていったときに最初に当たる点と下 ($k=-\infty$) から上げていったときに最初に当たる点とのマンハッタン距離」のうち大きいほうが、求める最大のマンハッタン距離になる。

解答

実装がかなり汚い(Pythonっぽくない)が、ACならヨシ!

「-45°の直線$y=-x+k$を下 ($k=-\infty$) から上げていったときに最初に当たる点」は、全ての点の$x+y$を求めてその値 ($k$) で昇順ソートすれば最初の値になる。同じ直線上に複数の値があっても、マンハッタン距離は同じなるか、45°の直線で拾えるので問題ない。(この辺りの厳密な説明がむずい。説明できなくてもそんな感じがする。)

コードを見る(クリックして下さい)

ABC178 E問題 解答

 

Submission #16711687 - AtCoder Beginner Contest 178

感想

今回の問題は数学系の問題が集まっていた

実装が軽めだけど思いつくのに時間がかかる良い問題だった

初期のAtCoderは実装重めでパズルみが無いけど、最近の問題はけっこう楽しい


先週からAtCoderの過去問を埋め直し、灰・茶diffは埋め終えた

(精進グラフが青になった!)

f:id:monhime:20200914074601j:plain:w400

今は緑diffを埋めているが、初期の試験管問題は今のAtCoderと内容がずれてるので飛ばすことにした

しばらくはStreak気にせず最近の水diffを繰り返し解いて、類題が出題されたら確実に解けるようにしておきたい


そういえば先週末、ACL・ARCが4週分生えていた

次のRatedコンテストは3週間後

毎日1問解けばかなり力が付きそう

頑張るぞ