Home / Python /

AtCoder Beginner Contest 177をPythonで解く

投稿日：　

Atcoder Python

B!
Daniel AgreloによるPixabay(https://pixabay.com/)からの画像

こんにちは, Shinoryoです.

今回はAtCoder Beginner Contest 177を, Pythonで解いてみた結果を書き連ねていこうと思います.

AtCoder Beginner Contest 177 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A - Don't be late

たどり着けるかどうかを計算します. 一応整数の範囲でやれるように

\begin{align} D &\leq T \times S \end{align}

の条件式を用いています.

B - Substring

文字列$T$を文字列$S$に重ねる全パターンを調査して, その最小値をとります. 文字列の長さはlen()で分かります.

C - Sum of product of pairs

問題文にあることを律儀に実行する(すなわち, $1 \leq i < j \leq N$を満たす$i$, $j$に対して,

\begin{align} \sum_{i,j} A_i A_j \end{align}

を計算しようとする)と, 計算量が膨大になり, TLEになります. 参考までにそのコードを示しておきます.

解決策はいくつか考えられますが, 累積和によるものを示しておきます. $1 \leq i \leq N$($i = N$のときは対応する$j$が存在しないので, 実質的には$N-1$)の各$i$に対して, $A_i$に掛け算するのは$A_{i+1}$, $A_{i+2}$, ……, $A_N$です. ゆえに, あらかじめ$A_{i+1}$, $A_{i+2}$, ……, $A_N$の和を求めておけば, 計算量を減らすことができます.

実際には, $A_1$, $A_2$, ……, $A_N$の和を求めておいて, $i=1$に対する計算が終わった後にその累積和から$A_1$を減らして$i=2$に対する計算に利用する, というようにします.

あるいは,

\begin{align} \sum_{i < j} A_i A_j &= \frac{\left( \sum_i A_i \right)^2 - \sum_i A_i^2}{2} \end{align}

であるため, これを計算する方法もあります.

D - Friends

友達関係を辿って辿り着ける人は友達であるということから, $N$人の人は最終的には友達同士で結成されたいくつかの「友達集合」に分けられます. もちろん, 友達が存在しないために$1$人の「友達集合」に含まれる可能性もあります.

ここで, もし同じ「友達集合」に所属する人同士を同じグループに配置してしまうと, その人達は友達同士になってしまうため, 条件を満たすことが出来ません. よって, 最も人数の多い「友達集合」の人数を$K$とすると, 必要なグループ数は最低でも$K$になります. 他の各「友達集合」についても, $1$人ずつ順番にグループを割り振っていけばよいので, 求める数は$K$になります.

$K$を求める方法として, ここでは幅優先探索(breadth first search; BFS)と呼ばれる方法を用います.

幅優先探索はグラフ理論等で用いられるアルゴリズムです. ある根ノードで始まり隣接した全てのノードを探索し, そのそれぞれに対して同様のことを繰り返すことによって探索対象ノードを網羅します.

下の図は, 鹿児島県から出発して, 陸続きの都道府県を探索する幅優先探索を表しています. 鹿児島県に隣接していて陸続きなのは, 熊本県と宮崎県です. その熊本県と宮崎県に対しても同様のことを繰り返していきます*1.

幅優先探索を九州で説明している図

いくつか注意点を述べておきます.

  • 友達が誰かを調べるべき人を格納したリスト(上の例でいうと, この後熊本県と宮崎県に関してどの都道府県に隣接しているかを調べるので, 「熊本県」と「宮崎県」を格納するリストが欲しい)に関しては, collectionsモジュールのdeque型を使用します*2.
  • これまでの探索でどの友達集合に所属しているかが判明している人に関しては, 新たに幅優先探索を行っても既知の友達集合を調べることになってしまいます. そのままではでは時間計算量が大きくなってしまうので, リストvisitedを用いてどの友達集合に所属しているかが判明している人のリストを管理します.

E以降

E以降は私の能力不足故に省略いたします.

参考にしたサイト等

脚注

*1 : 宮崎県から大分県に点線で矢印が引いてあるのは, 探索に関する熊本県と宮崎県の順番次第では, 大分県へは熊本県からではなく宮崎県から矢印が引かれる可能性があることを示しています.

*2 : deque型には, 先頭・末尾の要素を追加・削除するappend(), appendleft(), pop(), popleft()にかかる時間計算量が大きく減少するというメリットがあります. 一方で, deque型の中央部分へのアクセスには時間計算量が大きくなってしまうというデメリットがあるので, 要素の追加・削除以外も何らかの操作を行う場合には, deque型を使わない方が良いかもしれません.

Search

About Me

自分の写真
理系大学生でした. Bloggerを利用して発信を行っています.

Labels

Blog Archives