BETA

AtCoder Beginner Contest 162 反省会

投稿日:2020-04-14
最終更新:2020-04-14

反省会

きりみんちゃんに触発されてAtCorderを1年ぶりにやりました。言語はPythonです。
技術書典8の「AtCoder の歩き方」を読んだよ

ABが通せて、パフォーマンス73でした。先が思いやられます。

反省点

  • 標準入力は文字列だぞ
  • PythonなのにCで提出するな
  • コードを別の問題から提出するな
  • コードテストを使え
  • 飲酒コーディングは沼

標準入力は文字列だぞ

inputって文字列が返ってくるんですね。数値をintに変換せずにREになりました。

PythonなのにCで提出するな

言語選択が途中でCに変わっているのに気づかず提出してました。

コードを別の問題から提出するな

DをCで提出してREになって???になってました。

コードテストを使え

使わずに提出してREになって???になってました。

飲酒コーディングは沼

お供はメッツァコロナ プレステージ カベルネソーヴィニヨン
旬な名前だったので名前買いしたやつです。

コンテスト後にCとD問題を通せたので、アウトプットも兼ねて書いたのが下記です。

C問題 Sum of gcd of Tuples (Easy)

import math  
from itertools import product  

x = int(input())  

s = 0  
for a, b, c in product(range(1, x+1), repeat=3):  
  s += math.gcd(math.gcd(a, b), c)  
print(s)  

math.gcdは2つの値の最小公約数を求めます。
3つの最小公約数はmath.gcdで求めた値と残りで、再び最小公約数を求めればいいです。

はじめは、math.gcdは引数を2つしかとらないのでreduceを使って書けばいいと思いました。

import math  
from functools import reduce  
from itertools import product  

x = int(input())  

s = 0  
for i in product(range(1, x+1), repeat=3):  
  s += reduce(math.gcd, i)  
print(s)  

しかし、これだとTLEになります。
ちなみに、PyPy3だと通ります(それでも2倍ほど遅い)。

D問題 RGB Triplets

from itertools import product  


N = int(input())  
S = input()  

R_i = [i for i, s in enumerate(S) if s == "R"]  
G_i = [i for i, s in enumerate(S) if s == "G"]  
B_i = {i for i, s in enumerate(S) if s == "B"}  

R = len(R_i)  
G = len(G_i)  
B = len(B_i)  

xs = map(sorted, product(R_i, G_i))  

s = 0  
for x in xs:  
    k = 2 * x[1] - x[0]  # 2j-i  
    if k in B_i:  
        s += 1  
    i = 2 * x[0] - x[1]  # 2j-k  
    if i in B_i:  
        s += 1  
    j = (x[0] + x[1]) / 2  # (i+k)/2  
    if j in B_i:  
        s += 1  

print(R * G * B - s)  

考えたこと

条件1

条件は$S_i ≠ S_j$ かつ $S_i ≠ S_k$ かつ $S_j ≠ S_k$です。

例えば、
$(S_i, S_j, S_k) = (R, G, B)$なら条件を満たすので⭕️
$(S_i, S_j, S_k) = (R, R, G)$なら$S_i ≠ S_j$を満たさないので❌

from itertools import permutations  

list(permutations("RGB", 3))  

出力

[('R', 'G', 'B'),  
 ('R', 'B', 'G'),  
 ('G', 'R', 'B'),  
 ('G', 'B', 'R'),  
 ('B', 'R', 'G'),  
 ('B', 'G', 'R')]  

これらのいずれかが該当します。

したがって、Rのまとまりと、Gのまとまりと、Bのまとまりを作り、1つずつ選んで3つ並べれば、条件を満たさない組みが出ることはないです。例えば、$(R, R, B)$は出ません。

Rと GとBを別々のまとまりにすると、例えばR同士は区別がつかないのでindexで得ることにしました。後述するindexの条件でも使えるので丁度いいです。

R_i = [i for i, s in enumerate(S) if s == "R"]  # Rのindexのまとまり  
G_i = [i for i, s in enumerate(S) if s == "G"]  # Gのindexのまとまり  
B_i = {i for i, s in enumerate(S) if s == "B"}  # Bのindexのまとまり  

Rのまとまりと、Gのまとまりと、Bのまとまりから1つずつ選んで並べるので、Rの個数×G×の個数×Bの個数で総数が求まります。

そのため各RGB個数を求めます。

R = len(R_i)  
G = len(G_i)  
B = len(B_i)  

条件1を満たす総数は$R×G×B$です。

条件2

条件は$j - i ≠ k - j$です。

例えば、$i$について式変形すれば、

$j - i ≠ k - j$
$i ≠ 2j - k$

$j$について式変形すれば、

$j - i ≠ k - j$
$2j ≠ i + k$
$j ≠ (i + k) / 2$

$k$について式変形すれば、

$j - i ≠ k - j$
$k ≠ 2j - i$

$(i, j, k)$の関係が上の条件から決まることがわかります。

つまり、$i$も$j$も$k$も2つ決まれば残りの1つが決まります。

例えば、$i, j$が決まると$k = 2j - i$から$k$が求められます。
$k = 2j - i$で求めた$k$は条件$k ≠ 2j - i$を満たしません。

したがって、満たさない$k$を数えて、全体の総数$R×G×B$から引いていけばいいと思われます。

また、$i, j$の2つが決まればいいので、計算量は$O(n^3)$から$O(n^2)$とすることができます。

ネストしたfor文はproductで表せます。

product(R_i, G_i)  

RGBのうち2つのindexを使えばいいので、今回はR_iG_iを使いました。

余ったB_iB_iの要素に$i$、$j$、$k$が含まれているかの確認に使います。

そのため集合としてB_iに代入しています。

B_i = {i for i, s in enumerate(S) if s == "B"}  

i in B_ij in B_ik in B_i

これらは$O(1)$で要素確認可能です。リストでやるとTLEで死にます。

条件3

条件は$i < j < k$です。

$(i, j, k) = (2, 4, 7)$なら条件を満たすので⭕️
$(i, j, k) = (3, 1, 5)$なら$i < j$を満たさないので❌

R_iG_iはRとGのindexを持っていますが、それぞれindexが被ることはありません。

from itertools import product  

S = "GRGR"  

R_i = [1, 3]  
G_i = [0, 2]  

list(product(R_i, G_i))  

出力

[(1, 0), (1, 2), (3, 0), (3, 2)]  # (R, G), (R, G), (R, G), (R, G)  

productはそのままだと順番が$(i < j < k)$を満たしていない部分があります。

また、RとGの並び方は$(R, G)$と$(G, R)$の二つが考えられますが、productは$(R, G)$の一つしか考えていません。

上の例だと、$(1, 2)$は逆にすると$(2, 1)$で$(G, R)$となります。しかしこれは$i < j < k$を満たしていません。これより、$(1, 2)$の逆は考える必要がないとわかります。
また、$(1, 0), (3, 0), (3, 2)$は$(R, G)$ですが、$i < j < k$を満たしていません。indexを逆にすると$(0, 1), (0, 3), (2, 3)$の$(G, R)$となり、$i < j < k$を満たしています。したがって、$i < j < k$の条件を考慮すると一意に定まります。

$i < j < k$の条件を満たすにはsortすれば良さそうです。

list(map(sorted, product(R_i, G_i)))  

出力

[(0, 1), (1, 2), (0, 3), (2, 3)]  # (G, R), (R, G), (G, R), (G, R)  

注意点

R_iG_iを選びましたが、この2つが$(i, j)$であるかはわかりません。
$(i, k)$のこともあれば、$(j, k)$であることもあるでしょう。

したがって
Bが$i$のときは$i = 2j - k$
Bが$j$のときは$j = (i + k) / 2$
Bが$k$のときは$k = 2j - i$
を満たした場合、それぞれ総数$R×G×B$から引くことになります。

xs = map(sorted, product(R_i, G_i))  

s = 0  
for x in xs:  
    k = 2 * x[1] - x[0]  # 2j-i  
    if k in B_i:  
        s += 1  
    i = 2 * x[0] - x[1]  # 2j-k  
    if i in B_i:  
        s += 1  
    j = (x[0] + x[1]) / 2  # (i+k)/2  
    if j in B_i:  
        s += 1  
print(R * G * B - s)  

参考文献

AtCoder ABC 162 D - RGB Triplets (400 点) - けんちょんの競プロ精進記録
pythonの高速化のために、用途別にcollection型(list/tuple/dictionary/set)の計算量をまとめる - Qiita

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

A03kiの技術ブログ

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう