競プロ典型90問 ★2問題コード解説[2]

はじめに

最近はかなり冷え込みが厳しくなってきましたね。最近は椅子に座るときも足に毛布を巻いています。椅子に座りながらこたつのような温かさと安心感があってとてもよいですね。

今回は競プロ典型90問の★2問題を2問解説していきたいと思います。 競プロ典型90問については、以下のリンクからご覧ください。

atcoder.jp

022 - Cubic Cake（★2）

022 - Cubic Cake（★2）

ケーキに切れ込みを入れてすべてのピースを立方体にするためには、何回切ればよいか、という問題です。
この問題を解くカギは、
各辺に対して等分する必要がある
ということです。
ケーキに切れ込みを入れるときは、スパッとすべて切断する必要がある（一部だけ切れ込みを入れることはできない）ので、切断後の1辺の長さは、全ての辺の約数である必要があります。
また、操作を行う最小回数を求める必要があるので、できるだけ大きく切る必要があります。
それらの条件を満たすのは最大公約数なので、a, b, cの最大公約数が切断する1辺の長さとなります。切断回数は切断後のピースの数 - 1で求めることが出来ます。
Pythonだと、mathライブラリをインポートしてmath.gcd(a, b)で簡単に最大公約数を求めることが出来ます。

import math
a, b, c = map(int, input().split(" ")) 
 
#1辺の長さ
length = math.gcd(math.gcd(a, b), c)
 
output = (a//length-1)+(b//length-1)+(c//length-1)
print(output)

024 - Select +／- One（★2）

024 - Select +／- One（★2）

2つの数列が与えられ、K回の +1か -1でそれらを一致させられるかを判定する問題です。この問題を解くカギは、
+1 と -1を1回ずつの2回の操作を行えば、今の状態をキープできる
ということです。
つまり、添え字が同じ数列の数値の差を合計して、それとKとの差が2の倍数であれば、K回の操作で数列を一致させることが出来るということです。

n, k= map(int, input().split(" "))
a_list = list(map(int, input().split(" ")))
b_list = list(map(int, input().split(" ")))
 
sum_diff = 0
for i in range(n):
     sum_diff += abs(a_list[i] - b_list[i])
 
if (k - sum_diff) % 2 == 0 and (k - sum_diff) >= 0:
    print("Yes")
else:
    print("No")

おわりに

今回は典型90問の★2問題の2問を解説していきました。予定では前回の続きのABC280のD問題を解説しようとしたのですが…アルゴリズムを理解したつもりになってもACにならずで…。まだ少し時間がかかりそうです。
次回のABCまでには何とか理解して記事を書きたいですね。