問題 N個()の頂点を持ち、dist[i][j]()のコストの一方向の辺を持つグラフが与えられる。それぞれの頂点からそれぞれの頂点への最短路を考えた時、T()より多い回数を通る辺のコストの総和を求めよ。 解法 d[i][j]は最短路のコストを表す。ある辺が最短路に含…

問題 N*Nの平面()に、AppleとPearが置かれている。空白のマスも存在する。ひとつのフルーツを取り出しそれを空のマスへ移動するという操作をK回()することができる。Appleで満たされる長方形の最大面積を求めよ。 解法 ある長方形をAppleで満たせるかを全探…

問題 サイズN()の数列が与えられる。任意の要素に数字を足していくことで同じ値の要素を増やしていく。同じ値の要素数をiとし、その要素数を作るのに必要な最小な値をとする。の全要素でのXORの値を求めよ。 解法 愚直に全探索を行うととなる。はある要素に…

問題 長さN()の文字列が与えられる。文字列の順番を入れ替えて新しい文字列を作成する。新しく作成した文字列の集合(最初の文字列も含む)からランダムに値を取り出す。その文字列が回文になっている確立を求めよ。 解法 文字列の集合の要素数は順列を用いる…

問題 AliceとBobがいる。Aliceはa個のb面あるサイコロを転がし、Bobはc個のd面あるサイコロを転がす。サイコロの目の合計が高い方が勝ちとする。Aliceが勝利する時のサイコロの目の期待値を求めよ。 解法 はじめに、スコアに対する確率分布を求める。 Alice…

問題 長さN()の文字列が与えられる。その中で違う文字同士のペアを取り出す。取り出すペアが無くなった時点で終了となり、この時に残っている文字をwinning letterと呼ぶ。winning letterの文字列を辞書順にして求めよ。 解法 サイズが小さいので一文字ずつw…

問題 割れる数を求める関数dを用いてとなる関数hを定義する。h(x)の値n()からxを求めよ。 解法 nの値が大きいので、xを全探索して答えを見つけることはできない。d(n)の値は十分小さいので、この値について全探索を行う。 を計算し、となることを確認する。 …

問題 横幅がW、縦幅がHの四角形の穴があり、それを埋めるための四角形の板がN個()与えれる。穴を埋めるの最小な板の数を求めよ。 ただし、以下の条件を満たさなければならない。 板の四隅は穴の外側(板の横幅か縦幅のどちらかが穴の横幅か縦幅より真に大きい…

問題 ノード数がN()の木(tree)が与えられる。各辺(edge)は双方向(bidirectional)であり、長さlength()が定義されている。互いに同じ距離となるノードの集合の最大要素数を答えよ。 解法 まずノードの数が1つである場合は1となり、2の場合は必ず2となる。 木…