AtCoder Beginner Contest 276について
2022年11月06日
昨日にAtCoder Beginner Contest 276を受けたのでその感想を書いていきたい。
https://atcoder.jp/contests/abc276
AtCoderについては前回のエントリに投稿してから三週連続で参加をしている。
初回がA,Bの２問を解き、5,238位。
二回目がA,B,Dの３問を解き、2,983位。
今回についてはA,B,Cの３問を解いて4,513位という結果だった。
順位的には下がってしまったが、前回でD問題を解けたのは、ほぼほぼラッキーパンチみたいな感じだった。
今回は自分なりの解法でC問題を解けたという手ごたえがある。そのため、前に進んだ、という気持ちがある。
C問題に圧倒的な時間を使ってしまい、D問題に取り掛かる前にタイムオーバー。
自分の立ち位置と今後の目標
なんとなく三回受けてみて、過去問等も行いながら、今の自分の実力が把握できてきた。
それはC問題とD問題が鬼門になっている、というレベルだ。
このあたりをきっちり時間通りに解け切れるようになるのを当面の目標としたい。
振り返り
振り返りを兼ねて、今回のC問題とD問題のおさらい。
C - Previous Permutation
https://atcoder.jp/contests/abc276/tasks/abc276_c
順列とソートに関する問題。
一見してitertoolsを使ってやるだけなのでは、という典型的な罠にはまる。
つまり、こういうコードを書いていた。
import itertools
n = int(input())
a_list = [int(v) for v in input().split()]
# 全順列を作成する
perm = list(itertools.permutations(a_list))
# 並び替える
perm.sort()
# indexを取得
a_list = tuple(a_list)
a_index = perm.index(a_list)
ans = perm[a_index - 1]
print(' '.join(list(map(str, ans))))
答えとしては正しいものが出力される。
しかし全順列を作成すると、ソートするのに時間がかかりすぎて、TLEを起こしてしまう。
考え方をかえて、リストを後ろから繰り返すことで、高速に処理をできることに気づいた。
問題は与えられた順列の一つ若い順列を返すというものだ。
9 8 6 5 10 3 1 2 4 7こういう順列があたえられたときに、後ろから順番に見ていく。
4 72個目になった際にこういう並びになる。これを並び変えても、元の4 7より若くなることはない。
2 4 7
1 2 4 7ここまで進めても同様だ。いくら並び替えても若くならない。
3 1 2 4 7ここまでくると並び替えることで若い数字が作れる。
つまり前の数字よりでかい数字が来ることが条件だ。
ここから一つ若い順列は以下の手順で作れる。
まず一番左の3と一番近い2を入れ替える。
2 1 3 4 72を切り離す。
1 3 4 7切り離した数列を降順で並び替える。
7 4 3 12とくっつける。
2 7 4 3 1あとはまだ走査していない数列と合体して出力すれば完了となる。
最終的に以下のようなコードになった。
n = int(input())
a_list = [int(v) for v in input().split()]
# 一番後ろの数字を保存
min_val = a_list[-1]
for i in range(2, n + 1):
# 後ろから見ていき、小さい数字を更新していく
# 小さい数字が入り続ける限り、それ以上若い順番はない
if min_val > a_list[-i]:
min_val = a_list[-i]
# でかい数字が来たら入れ替え可能
else:
# 一時リストを取得
tmp = a_list[-i:]
# 先頭の数字を切り離す
num = tmp.pop(0)
# 先頭の数字より小さくて一番近い数字を探す
near = 0
for j in range(1, num):
near = num - j
if near in tmp:
break
# 一番近い数字と先頭の数字を入れ替える
a_index = tmp.index(near)
tmp[a_index] = num
# 降順でソートしたものが次に若い順列
tmp.sort(reverse=True)
# 答えを生成
tmp = [near] + tmp
ans = a_list[:n - i] + tmp
print(' '.join(map(str, ans)))
break
D - Divide by 2 or 3
https://atcoder.jp/contests/abc276/tasks/abc276_d
時間中には解けなかったが、チャレンジをしたところ自力で解くことができた。
初回は以下のようなコードとなった。
def prime_factorize(n: int) -> list:
"""素因数分解リストを返す"""
if n == 1:
return []
ret = []
while n % 2 == 0:
ret.append(2)
n //= 2
f = 3
while f * f <= n:
if n % f == 0:
ret.append(f)
n //= f
else:
f += 2
if n != 1:
ret.append(n)
return ret
def check_can(prime_list):
return len(prime_list) == prime_list.count(2) + prime_list.count(3)
def job():
n = int(input())
numbers = [int(v) for v in input().split()]
primes = []
for num in numbers:
primes.append(prime_factorize(num))
inter = set(primes[0])
for p in primes[1:]:
inter = inter.intersection(set(p))
goal = []
for num in inter:
min_cnt = 10 ** 15
for p in primes:
min_cnt = min(min_cnt, p.count(num))
tmp = [num] * min_cnt
goal += tmp
for num in goal:
for p in primes:
p.remove(num)
ans = 0
for p in primes:
if check_can(p):
ans += len(p)
else:
print(-1)
exit()
print(ans)
job()
これはけっこうまわりくどいやり方であるが、ぎりぎりACとなる。
いちおう処理を追ってみよう。
まず与えられた数字を素因数分解したリストに変換する。
例えば、20 60 120が与えられたとすると、以下のようなリストができる。
primes = []
for num in numbers:
primes.append(prime_factorize(num))
>>>
[[2, 2, 5], [2, 2, 3, 5], [2, 2, 2, 3, 5]]
次にこのリストの共通する要素をsetで取得する。
inter = set(primes[0])
for p in primes[1:]:
inter = inter.intersection(set(p))
>>>
{2, 5}
次に素因数分解のリストを繰り返し目指すべき数字を確認する。
goal = []
for num in inter:
min_cnt = 10 ** 15
for p in primes:
min_cnt = min(min_cnt, p.count(num))
tmp = [num] * min_cnt
goal += tmp
>>>
[2, 2, 5]
つまり20が目指す数字ということになる。
その次は素因数分解リストからゴールの数字を除去していく。
for num in goal:
for p in primes:
p.remove(num)
残った素因数分解リストは以下のような形になる。
[[], [3], [2, 3]]問題では２か３で割ることができるので、２か３以外の数字がここで入っていたら、その数字は作ることができない。
配列の数を数えて、3と出力すれば正解だ。
別の解法
他の人のコードで、まず最大公約数で割ってから試行するという方法を取っているのを見つけた。
この方が高速で、分かりやすい。
import math
def job():
n = int(input())
numbers = [int(v) for v in input().split()]
a_gcd = numbers[0]
# 与えられた数字の最大公約を算出する イコール、ゴール
for num in numbers:
a_gcd = math.gcd(a_gcd, num)
ans = 0
for num in numbers:
# 最大公約数で割る
num = num // a_gcd
# 2で割れるだけ割る
while num % 2 == 0:
num = num // 2
ans += 1
# 3で割れるだけ割る
while num % 3 == 0:
num = num // 3
ans += 1
# 商が１になってなかったら同じ数字が作れない
if num != 1:
print(-1)
exit()
print(ans)
job()
そういえば、自分のやりかたも回りくどいやり方で最大公約数を計算していたのだなぁと、気づかされる。こういうのがパッと出て来る人がすごいと思う。ではでは。
Share