はまやんはまやんはまやん

hamayanhamayan's blog

Squared Ends [CSAcademy #70 E]

https://csacademy.com/contest/round-70/task/squared-ends/

N要素の配列Aがある。
これをKグループに分ける。
各グループ[A[l], A[l+1], ..., A[r]]について(A[l] - A[r])^2のコストがかかる時、コストの総和の最小値は?

続きを読む

Distribute Candies [CSAcademy #70 D]

https://csacademy.com/contest/round-70/task/distribute-candies/

N個をK箱に分けるが以下のルールで分ける

  • 隣接する箱の数は異なっている
  • 箱には最低1個は入っている
  • 箱の中に入っている数の最大値と最小値の差が最小化されている

作るのが不可能なら"-1"

続きを読む

Min Distances [CSAcademy #70 C]

https://csacademy.com/contest/round-70/task/min-distances/

以下の条件を満たすN頂点の重み付き無向グラフを構築せよ。

  • M本の「頂点aと頂点bの最短距離がc」という情報をすべて満たす
  • 無向グラフはシンプルで連結である
続きを読む

Right Down Path [CSAcademy #70 B]

https://csacademy.com/contest/round-70/task/right-down-path/

縦N,横Mのバイナリ行列がある。
ここから

  • ある1つのセルを決める
  • そこから最低1セル右に進む
  • そこから更に最低1セル下に進む

のように移動する。
移動できるのは1のマスだけであるとき、作れるパスの最大長は?

続きを読む

Digit Holes [CSAcademy #70 A]

https://csacademy.com/contest/round-70/task/digit-holes/

数0,6,9は穴が1つ、数8は穴が2つあるとする。
[A,B]の数の中で穴の数が最大の数を答えよ。

続きを読む

Subgraphs [SRM730 Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=14817

ある数Kが与えられる。
以下の条件を満たすようにグラフを生成する。

  • 頂点数Nは46個以下
  • 自己辺、多重辺無し
  • x=[0,K*(K-1)/2]について、N個からK個取ってきた頂点集合の中の辺がx本であるような集合が存在する

グラフの隣接グラフと、x=[0,K*(K-1)/2]それぞれについて集合を答えよ

続きを読む

StonesOnATree [SRM730 Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14811

頂点0を根とする木が与えられる。
木の各頂点は最大2個の子を含む。
頂点iには重みW[i]がある。
以下のルールに従って石を置く。
頂点0に石を置くための最大の瞬間重み総和は?

  • 子供(孫は関係ない)に石が置かれてないと、頂点に石は置けない
  • 自由に石を除いて良い
  • 葉は自由に石をおける
  • 石を置くとその頂点の重みが有効になる
続きを読む