【AtCoder】ABC162 (A~D) 参戦記

2年のブランクの後にAtcoderという競技プログラミングを再開した

昔はC++を使っていたけど、今回からPythonで参加する

実行時間は遅いがコードが簡潔だしPythonは他の分野でも広く使えるので良い勉強の機会になりそうなので

結果

順位:10430位中3598位

得点:1000点(1)

ペナルティ付き最終解答時間:85:53

パフォーマンス:901

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

各問題の結果
得点 WA回数 解答時点での経過時間
A 100点 0 1:16
B 200点 0 4:05
C 300点 0 16:42
D 400点 1 80:53
E 500点 - -
F 600点 - -

レート変化

749→769 (+20)

7級のまま

f:id:monhime:20200413120531j:plain:w500

f:id:monhime:20200413120536j:plain:w400

解答

A: Lucky 7

A - Lucky 7

問題要約

3桁の整数$N$のいずれかの桁に7はあるか

解答

文字列として扱って条件分岐ですぐ

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

ABC162 A問題 解答

 

atcoder.jp

B: FizzBuzz Sum

B - FizzBuzz Sum

問題要約

数列$a_i\,(i=1,2,\cdot)$が次の用に定められている

$i$が3でも5でも割り切れたら$a_i=FizzBuzz$

$i$が3で割り切れたら$a_i=Fizz$

$i$が5で割り切れたら$a_i=Buzz$

そうではないなら$a_i=i$

このとき、数列$a_i$の$N$項目までの数字の和を求めよ

解答

3でも5でも割り切れない数を足していく

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

ABC162 B問題 解答

 

atcoder.jp

C: Sum of gcd of Tuples (Easy)

C - Sum of gcd of Tuples (Easy)

問題要約

$\displaystyle\sum_{a=1}^K\sum_{b=1}^K\sum_{c=1}^Kgcd(a,\,b,\,c) $の値を求めよ

($gcd(a,\,b,\,c)$は$a,\,b,\,c$最大公約数)

解答

$a,b,c$のあり得る全組み合わせ ($K^3$) を計算すると、$ K $の最大値は200なので、$8\times 10^6 $回計算することになる

C/C++ならいけるだろうが、Pythonだと間に合わなそう

それに無駄な計算が多い

そこで、同じ数字の組合わせをまとめて計算する

  • a,b,cが全て異なるとき

並べ方は$3\mathrm{!}=6$通りなので、gcd(a,b,c)に6を掛ける

  • a,b,cのうち2つだけが同じ値のとき

並べ方は残り1文字をどの位置に置くかを考えて3通りなので、gcd(a,b,c)に3を掛ける

  • a,b,cの3つが同じ値のとき

1通りだけなので、gcd(a,b,c)の値をそのまま加える

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

ABC162 C問題 解答

 

複数の値の最大公約数を求める関数を下のサイトからお借りした

Pythonで最大公約数と最小公倍数を算出・取得 | note.nkmk.me

atcoder.jp

D: RGB Triplets

D - RGB Triplets

問題要約

'R'、'G'、'B'のみからなる長さ$N$の文字列$S$について、次の条件を満たす組 $(i,\,j,\,k)\,(1\leq i < j < k\leq N)$ のを求めよ

$S$の$i,\,j,\,k$文字目 $(j-i\neq k-j)$ が互いに異なる

左から数えて2文字目と1文字目の間隔が3文字目と2文字目の間隔が異なるように異なる3つ文字を取ってくるとき、その取り方を求めよということ

解答

$i,\,j,\,k$の全組み合わせについて条件を満たすか確かめるのが最初に思い浮かぶが、間に合わない(実行時間2.2s(打ち切り)でTLE)

D問題なんだしそんな単純な解き方で解かせるつもりは無いだろうから、一捻りしないとけない


そこで、「異なる3文字から1文字ずつ選ぶ選び方」から「その選び方のうち2文字目と1文字目の距離と3文字目と2文字目の距離が同じになる選び方」を引いた

前者の「異なる3文字から1文字ずつ選ぶ選び方」は、各文字の出現回数の積になる

後者の「その選び方のうち2文字目と1文字目の距離と3文字目と2文字目の距離が同じになる選び方」は、距離が1から((文字列の長さ-1)//2+1)のそれぞれの場合について、文字列を左から順に3文字取ってきて、その3文字とも文字の種類が違うものをカウントしていく

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

ABC162D

 

atcoder.jp

感想

冒頭でも書いたとおり、長いブランクを経て久しぶりに参加したコンテストで、今回初めてPythonで参戦した

コードの長さがC/C++の3分の1程度まで減らせて、A問題は特に30秒で書き終えてちょっとテストして1分程度で提出できてしまうし、無駄なエラーが出たりしないから実装していて非常に楽


ABCは毎週末に開催されいているので、これから毎回出ようと思う

AtCoder Scoresのサイトの精進グラフは実際のレートの伸びとけっこう相関あるようで、今は時間の許す限り過去問を解いて精進グラフを伸ばしている

かと言って急ぎすぎるのも良くないので、300点問題を埋め終わったら毎日2問くらいのペースで400点問題を解いていきたい

f:id:monhime:20200413151750j:plain:w500

AtCoder Scores