2016-01-20

SRM 679 Div1 Easy 250 FiringEmployees

問題

N人の人達の上司、給料、生産能力が与えられる。
この会社の利益はN人の生産能力-給料の合計値となる。
生産能力が給料よりも低い人がいるので、そのような人をリストラすることで会社の利益を最大化したいが、ある人をリストラするとその人の部下達も全員リストラしなければならない。
適切にリストラを行うことで得られる会社全体の利益の最大値を求めよ。

$N \le 2500$

2016-01-12

Facebook Hacker Cup 2016 Qualification Round 40:Text Editor

問題

https://www.facebook.com/hackercup/problem/1525154397757404/

問題概要

全部でT個のテストケースがある。
各テストケースではN個の単語のうちK個を印刷したい。
今与えられているテキストエディタでは以下の操作を行うことができる。
・一文字打つ
・(右端の)一文字を消す。バックスペースに相当
・印刷する
K単語印刷したら必ず今画面に表示されている文字をすべて消すことも考慮した時、最小何回の操作を行えばよいか

$1 \le T \le 100$
$1 \le K \le N \le 300$
ただし、各テストケースの総文字数は高々 $10^{5}$ である。

2015-11-27

ICPC アジア地区予選2012 F Never Wait for Weights

問題

Never Wait for Weights | Aizu Online Judge

問題概要

N個の重りとM個のクエリがあるので、各クエリについて処理してください。
クエリとしては以下の2つが与えられます。
! A B W := Bの重さ-Aの重さがWであることが分かった
? A B := Bの重さ-Aの重さを出力する。ただし、このクエリを処理する時点でBの重さとAの重さの差がわからなかったら文字列としてUNKNOWNを出力する。

$1 \le N,M \le 10^{5}$

2015-11-19

SRM 673 Div1 Easy BearCavalry

問題概要

兵士と馬の戦闘力がそれぞれwarriors、horsesという配列で与えられる。兵士と馬の数は一致する。
兵士iと馬jを組み合わせた時の戦闘力はwarriors[i]*horses[j]で表される。
兵士と馬を適当に組み合わせた時に、warriors[0](以下、リーダーとする)の戦闘力がどのユニットよりも大きくなるような組み合わせ方は全部で何通りあるかのmod $10^{9}+7$ を求めよ。

$兵士の数 \le 50$ $1 \le 戦闘力 \le 1000$

[サンプル]
warriors = {10,2,10}
horses = {100,150,200}
[答え]
3
組み合わせとしては
(10,200),(2,150),(10,100)
(10,200),(2,100),(10,150)
(10,150),(2,200),(10,100)
が考えられる。
それ以外の組み合わせは例えば(10,150)(2,100)(10,200)を考えると、リーダーの戦闘力は1500,warriors[2]の戦闘力は2000となってしまい題意を満たさないのでNG

2015-11-08

JOI2014 本戦ケーキの切り分け2(Cake 2)

問題

Cake 2 | Aizu Online Judge

問題概要

円形にN個に切られたケーキ(サイズA[i]は全て異なる)について以下のような行動を考える。
1:JOI君とIOIちゃんの二人で交互に進める
2:JOI君が先行で、最初は好きなケーキを選べる
3:IOIちゃんは取ることのできるケーキのうちもっとも大きなケーキを取る
4:JOI君は取ることのできるケーキのうち好きなものを選ぶことができる
5:取ることのできるケーキとは、両隣の少なくともどちらか一方が今までの行動で取られたケーキでなければならない。
JOI君が食べるケーキの合計値の最大値を求めよ
$N \le 2000$ $A \le 1000000000$