AtCoder ABC175

Posted on Aug 20, 2020

atcoder python go

最初プログラミングを勉強し始めた時はひたらすら書く練習をしたくて、AtCoderを通して計算量や数学など学んでいました。ただアプリケーションを開発するスキルがつくわけではないので最近は少し休んでいました。

Goの書き方もわかってきたので久しぶりにやってみたのですが、面白いですね。当時はPythonしか書けなかったので、Goと比較しながら簡単なA, Bだけ解いてみました。

ABC175A

3つしか数字がないので2^3 = 8通りなのでロジック考えるより場合分けした方が生産的ですね。

s = input()

if s == "RRR":
    print(3)
elif s == "RRS" or s == "SRR":
    print(2)
elif s == "SSS":
    print(0)
else:
    print(1)

Go - ABC175A/Rainy Season

package main

import "fmt"

func main() {
	var n string
	fmt.Scan(&n)

	switch n {
	case "RRR":
		fmt.Println(3)
	case "RRS", "SRR":
		fmt.Println(2)
	case "SSS":
		fmt.Println(0)
	default:
		fmt.Println(1)
	}
}

ABC175B

三角形なので次の定理を満たせばいいですね

a + b > c
a + c > b
b + c > a

データは100個なので、この手の問題はブルートフォースが最適です。 O(N^3)ですが最悪100^3なので十分高速です。

a != b != c の条件がありますが、sortして数字が一緒ならスキップすることで確認が不要になります。またsortは O(nlogn)ですが、そもそもO(N^3)で満たすので問題ありません。

Python - ABC175B/Making Triangle

n = int(input())
L = list(map(int, input().split()))

L.sort()

cnt = 0
for i in range(n):
    for j in range(i, n):
        if L[i] == L[j]:
            continue
        for k in range(j, n):
            if L[j] == L[k]:
                continue
            if L[i]+L[j] > L[k]:
                cnt += 1

print(cnt)

Go - ABC175B/Making Triangle

package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)

	l := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&l[i])
	}
	sort.Ints(l)

	var cnt int
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			if l[i] == l[j] {
				continue
			}
			for k := j + 1; k < n; k++ {
				if l[j] == l[k] {
					continue
				}
				if l[i]+l[j] > l[k] {
					cnt++
				}
			}
		}
	}
	fmt.Println(cnt)
}

まとめ

特に面白かったのは実行結果です。

ABC175	python	go
A	33ms, 9MB	7ms, 1.7MB
B	73ms, 9MB	7ms, 1.8MB

やっぱりコンパイル言語には勝てないですね。

パフォーマンスはGoのがいいですが、文字列の操作が入ってくるとPythonの方がやりやすいかもしれません。また空き時間見つけて試してみます。