問題概要 マス目上に木となっている地図が与えられる。最大の距離となる2点の距離を求めよ。 解法 木の2点間最長距離を求めるには、任意の頂点から探索を行ない一番遠かった点から再度探索を行なう。 これをBFSで実装した。 実装(C++) #include <cstdio> #include <queue> #</queue></cstdio>…

問題概要 0 解法 nCk=n!/k!/(n-k)!なので、整数m!に含まれる素因数2の個数を求めることが出来れば簡単に判定出来る。 これは、mをどんどん2で割っていくことで求めることが出来る。 実装(C) #include <stdio.h> int calc_2(int a){ int res=0; a>>=1; while(a>0){ res</stdio.h>…

問題概要 長さが1〜Nの木がそれぞれあり、それを使って柵を作りたい。 ただし、柵はジグザグな形になるようにするようにしたい。 C番目の作り方を求めよ。 解法 dp[進行方向の残りの木の本数][全体の残りの木の本数]とすることで、O(N^2)でパターン数を求め…

問題概要 廊下を通って荷物を運ぶことを考える。それぞれの荷物運びに関しては独立に廊下を共有しないものに関しては同時に運ぶことが出来る。 何回運べば、全ての荷物を運び終えることが出来るか。 解法 ある廊下の前を通る最大の数を求める 実装(C) int ma…