AOJ2249 Road Construction

問題

Road Construction | Aizu Online Judge

N頂点、M辺の連結グラフが与えられる。各辺には距離と建設コストが与えられる。0番目が首都であり、各ノードから首都までの距離を与えられたグラフと同じにするものとして、一から連結グラフを生成するための最小コストを求めよ。

  • 1\le N\le 10000,\ 0\le M\le 20000
  • 1\le d_i,\ c_i \le 1000
続きを読む

AOJ2104 Country Road

問題

Country Road | Aizu Online Judge

限界集落には一直線上の道があり、電気の通らない家々が立ち並ぶ。

N個の家が数直線状に並び、K個の発電機が与えられる。全ての家に発電機から出る電気を行き渡らせたい。 発電機から出る電気は家同士を電線で結ぶことで、共有することが出来る。しかし電線を引くには長さに比例するだけのコストがかかる。引くべき電線の長さの最小値を求めよ。

  • 0 \lt n \le 100000
  • 0 \lt k \le 100000
  • 0 \le x_1 \lt x_2 \lt ... \lt x_n \le 1000000
続きを読む

AOJ2741 Invisible

問題

インビジブル | Aizu Online Judge

2人でカードゲームをする。各々デッキを持つ。カードには数字がかかれている。-1は妨害カードで、それ以外は正の得点となるカードである。2人は交互にプレイする。プレイヤーは、カードを場のスタック上に置くか、パスするかの選択肢を取れる。パスした場合、相手の置いた妨害カードの上の自分の全てのカードの和を得点として得ることが出来る。スタックに何も置かれていない状態から、2人がパスした場合にゲーム終了となる。2人とも出せるカードがなくなった場合もゲーム終了である。プレイヤーは、自分の得点から相手のプレイヤーの得点を引いた値を最大化しようとする。互いに最適な行動を取った場合、プレイヤー1の得点からプレイヤー2の得点を引いた値を求めよ。

  • 1\le n,\ m\le 50
続きを読む

AGC 006: B Median Pyramid Easy

問題

B: Median Pyramid Easy - AtCoder Grand Contest 006 | AtCoder

i段目に2 * i - 1個のブロックがあり、ピラミッド型に積まれている。 ブロックには数字がかかれていて、あるブロックの数字はその左下と真下と右下のブロックに書かれた数字の中央値である。 ブロックの段数と、最上段のブロックに書かれた値が入力として与えられる。このとき、最下段が1〜Nの順列となるような場合は存在するか。存在するならば、1行目に"Yes"と出力し、2行目以降は条件を満たす順列を1つ出力せよ。そのような順列がひとつも存在しない場合は"No"と一行に出力せよ。

  • 2\le N\le 10^5
  • 1\le x\le 2\times N−1
続きを読む