きままにものづくり

日々の気付いたことなんかを書いてます。

SRM

SRM619Div1Easy

SRM

問題 二人のプレイヤーがいて、サイズN()の数列が与えられる。交互に配列に対して操作を行い、操作ができなくなったプレイヤーが負けとなる。操作は以下となる。 2以上の値を持つ要素を選ぶ この要素を空ではない2つの要素に分割 最初に選んだ要素を含まない…

SRM620Div1Easy

SRM

問題 (a, b)と(c, d)の2組の数字のペアが与えられる。任意のペア(x, y)を考える。可能な操作は(x+y, y)または(x, x+y)である。(a, b)と(c, d)が作れる(x, y)のペアを求め、その中でx+yが最大となるペアを求めよ。作れない場合は-1を返す。 解法 (a, b)または…

SRM622Div1Easy

SRM

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

SRM623Div1Easy

SRM

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

SRM625Div1Easy

SRM

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

SRM629Div1Easy

SRM

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

SRM630Div1Easy

SRM

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

SRM580Div1

SRM

結果: 0 pt Easyでつまづいてしまい全然解けなかった。 習得したアルゴリズムに当てはめようとして、失敗した感じ。 アルゴリズムを身につけるのはとても大切だけど、中途半端な理解だと柔軟に思考できなくなってしまう。 EelAndRabbit セグメントツリー、bi…