AtCoder Beginner Contest 259 A 問題 から E 問題までの解説(Python3)

こんにちは。こんばんは。Rute(リュート)です。
昨日、AtCoder Beginner Contest 259 に参加しました。
本番の成績は4問正解(A問題・B問題・C問題・E問題)で、D問題が解ければ5問正解でした。 
だいたい80分くらいで4問正解したのですが、一般的な4問正解(A問題・B問題・C問題・D問題)と比べ得点が100点多かったため、水パフォーマンスを取得することが出来ました。

この記事では主に、AtCoder Beginner Contest 259 の A問題 から E問題までの解説を行いたいと思います。
各問題の回答ソースコード例はPython3(3.8.2)です。
 

A問題「Growth Record」

問題

解法

身長がX歳の誕生日からN歳の誕生日までの間変化していないことから、
・X < M であるとき、身長はTcmです。
また、M < X である時、
N歳の誕生日の時の身長に比べてM歳の身長はD * (X - M)cm低いことから
身長は T - (D * (X - M))cm であると計算できます。
よって、これを条件分岐によるプログラムで出力できるようにすれば良いです。
ソースコード例は以下の通りです。

N,M,X,T,D = map(int,input().split())
if X < M:
  print(T)
else:
  print(T - (D * (X - M)))

B問題「Counterclockwise Rotation」

問題

解法

少し、中学生などの方だと解くのに苦戦されたかもしれません。

問題文では、点(a,b)を原点を中心として反時計回りにd度回転させた点を求めて下さい。
ということだったので、加法定理などを用いると、
回転する角度をΘとして
(a,b) をΘ度反時計周りに移動させた座標は(acosΘ-bsinΘ,asinΘ+bcosΘ)
と計算することが出来ます。

これで答えの把握は出来たのですが、ある問題が生じます。
それは、dが「度数法」による角度であるということです。
cosやsinなどの三角関数で扱う角度は「弧度法」なので、
「度数法」の角度を「弧度法」に直す必要があります。
ここでPythonのライブラリの1つであるmath.radians(角度)を使うと
度数法の角度を弧度法の角度に変換することが出来ます。

(*一部、複素数を用いて回答する方法もあったようですが、三角関数を使うだけで十分だと思います。)
ソースコード例は以下の通りです。

import math
a,b,d = map(int,input().split())
d = math.radians(d)
X =  a * math.cos(d) - b * math.sin(d)
Y = a * math.sin(d) + b * math.cos(d)
print(X,Y)

今回の問題で三角関数の問題に興味を持った方は、かなり前のコンテストにはなりますが、ABC168のC問題「C-:(Colon」を解いてみることをオススメします。
C問題ですが、難易度は今回のB問題とあまり変わらない気がします。

C問題「XX to XXX」

問題

解法

この問題は、端的に言うならばTをランレングス圧縮した時にSに出来るかを考える問題です。
ランレングス圧縮についてはここでは深く扱いませんが、簡単に言うならば同じ文字が連続して続いている文字列についてそれを短縮する、というものです。

入力例1を例に考えてみます。

ここでは、その逆の「TをSにランレングス圧縮する」ことをベースに考えます。

まず、Tの1文字目は"a"です。Sの1文字目は"a"なので、圧縮の必要はありません。

Tの2文字目から5文字目までは"bbbb"です。Sの2文字目から3文字目が"bb"なので、
Tの2文字目から5文字目までのうち2文字を圧縮することで
Sの2文字目から3文字目に一致させることが出来ます。

Tの6文字目から8文字目までは"aaa"です。Sの4文字目から5文字目が"aa"なので、
Tの6文字目から8文字目までのうち1文字を圧縮することで
Sの4文字目から5文字目に一致させることが出来ます。

Tの9文字目は"c"で、これはSの6文字目の"c"と一致しているので、
圧縮の必要はありません。

入力例1では、SをTに一致させることが出来るのでYesと出力すれば良いです。

まとめると、Tについての任意の文字のランレングス圧縮を行うことでSに変化させることが出来るかをシミュレーションすれば良いです。
計算量はO(|S| + |T|)となります。

ソースコード例は長いので、URLからご確認下さい。

ソースコード例

D問題「XX to XXX」

問題

解法

難しい問題を解く場合には、まず制約を読んで解法を考える必要があります。
制約では、Nが3000以下であることから
全探索によって、N個の円のうち全ての2つの円の組において円の円周上を行き来できるかどうかを判定することが出来ます。
また、円同士の行き来は、無向グラフと同様のネットワーク構造であると考えることが出来るので、行き来が出来る場合は円を頂点とみなして2つの円の頂点同士で無向グラフを構築すれば良いです。

次に、(sx,sy)と(tx,ty)がどの円の上に存在するかを判定する方法ですが、
これは点を円周上に含む必要条件として、このような式が成り立っているかを全ての円について考えて判断すれば良いです。

式では(sx,sy)がどの円の上に存在するかを判定していますが、
sx,syをtx,tyに置き換えることで(tx,ty)がどの円の上に存在するかを判定することも出来ます。

最後に、(sx,sy)が存在する円から(tx,ty)が存在する円まで移動できるかの判定についてですが、
先ほど述べた通り円を頂点とみなした無向グラフ上を頂点同士で移動して、(sx,sy)が存在する円の頂点から(tx,ty)が存在する円の頂点までを0回以上で移動できるかを判定することと同じです。

したがって、この判定は幅優先探索や深さ優先探索などのグラフ探索アルゴリズムを使うことで解く事が出来ます。

計算量は
まず円同士について移動できるかについての判定の全探索がO(N²)、
続いて(sx,sy),((tx,ty)を含む円の探索がO(N)、
最後に幅優先探索や深さ優先探索による移動できる頂点の探索でO(N)

なので、全体的な計算量はO(N²)となり、この問題の制約で解く事が出来ました。

ソースコード例は長いので、URLからご確認下さい。
(なお、Python3(3.8.2)ではTLE(実行時間制限超過)となったため、PyPy3(7.3.0)で提出しました。)

ソースコード例

E問題「LCM on Whiteboard」

問題

最小公倍数について

最大公約数は「全ての数の素因数において、指数の最小値を全て取る」
最小公倍数は「全ての数の素因数において、指数の最大値を全て取る」
ことで計算が出来ます。

例えば、入力例1では
a_1 = 7²=49, a_2 = 2²×5¹ = 20, a_3 = 5¹ = 5, a_4 = 2¹×7¹ = 14 です。

これを、それぞれの数の素因数を列にして表にするとこのようになります。

よって、この場合のN個の数の最小公倍数が980であることが分かりました。
次に、N個の数についてそれぞれ1にした時に、最小公倍数がどのようになるかを考えていきましょう。

最小公倍数の変化

まず、a_1 = 49を1にした場合を考えます。
2の指数の最大値は2のまま、5の指数の最大値は1のままですが、
7の指数の最大値は1になるので、この場合の最小公倍数は140になります。

以下、a_1,a_2,a_3,a_4のそれぞれを1にした場合の最小公倍数の変化を図にしたものを示します。
 

よって、答えは3になるわけですが、ではこのシミュレーションをどのように行うかを考えていきます。

シミュレーション

各a_i(1≦i≦N)を素因数分解した時の素数をp, 指数をeとおくと 
a_i = p_(i,1)^e_(i,1) * p_(i,m_1)^ p_(i,m_1) ... 
という形となります。

さらに素数p_(i,1),... p(i,m_1)の各j(1≦j≦m_j)について、
もしp_(i,j)のe_(i,j)が
N個の数におけるp(i,j)のe_(i,j)の最大値でかつ
その出現回数が1であった場合のみ、最小公倍数が変化することになります。

よって、
各p_(i,j)のe_(i,j)の最大値の出現回数、並びにp_(i,j)のe_(i,j)の最大値を記憶しておくことにより、N個の数における最小公倍数がどのようになるかをシミュレーションすることが出来ます。

問題の制約に着目すると、p_(i,m_i)の最大値は10⁹(10億)で
10億までに現れる素数の個数は50847534個(引用先)なので、
普通に各素数毎に配列に記憶すると空間計算量の部分で計算量がかかってしまうことが考えられます。

ここで、m_iの合計が10万以下であることから、素数が出現した際に出現した順番を連想配列に持くことで、その値を用いて最大値の出現回数・最大値をそれぞれ10万以下の長さの配列・連想配列で計算することが可能です。

あとは、N個の数のp_(i,j)、e_(i,j)について
先ほどの条件を満たしているかを判断して変化する素数のパターン数を列挙すれば良いです。もちろん、最小公倍数が変化しない場合があることにも注意して下さい。

ソースコード例は長いので、URLからご確認下さい。

ソースコード例

以上、AtCoder Beginner Contest 259 の A問題～E問題までの解説記事でした。
分からない点・訂正すべき等がありましたら、コメントなどで教えて頂けると幸いです。