AtCoder Beginner Contest 116

AtCoder Beginner Contest 116を解きました

 A - Right Triangle

 

atcoder.jp

問題

直角三角形ABC(\angle ABC = 90^\circ)の長さ|AB|,|BC|,|CA|が与えられる。この直角三角形の面積を求めろ。

解き方

\frac{|AB| \times |BC|}{2}を出力する。

B - Collatz Problem

 

atcoder.jp

問題

初項0 \leq s \leq 100が与えられる。

nが偶数ならf(n)=n/2、奇数ならf(n)=3n+1となる関数がある。

i=1ならa_i = s  i<1ならa_i = f(a_{i-1})となる。

a_m = a_n (m > n)となるmの最小値を求めよ。

aのすべての要素とm1000000以下になることが保証される。

解き方

1 \leq N \leq 1000000の範囲をフラグで管理する。f[a_i=0]ならf[a_i=1]にする。f[a_i=1]ならiを出力して終了する。

C - Grand Garden

atcoder.jp

問題

数列h = {h_1,h_2,...}が与えられる。数列の最初の状態はすべて0。以下の操作を繰り返して数列hと同じ値にしたい。

区間[tex;l,r]を指定してその区間の値を全て1増やす。

操作の最小数を求める。

解き方

再帰で解ける。

dfs(l,r,x)::区間l,rで数列の現在の値が全てxのとき、目標までに必要な操作の回数。

int dfs(int l,int r,int x){
if(l>r){
return 0;
}
int p=0,a=10000;
for(int i=l;i<=r;i++){
if(a>h[i]){
a=h[i];
p=i;
}
}
return a-x+dfs(l,p-1,a)+dfs(p+1,r,a);
}

区間の最小値までは安全に足すことができる。

そのあと、区間を最小値の右側と左側に分割して再帰をする。

D - Various Sushi

atcoder.jp

問題

N個の寿司があり、それぞれの寿司にネタt_iとおいしさd_iが与えられる。寿司をK個選んで以下の式を最大化する。

・満足ポイント=おいしさ基礎ポイント+種類ボーナスポイント

・おいしさ基礎ポイント=選んだK個の寿司のおいしさの総和

・種類ボーナスポイント=選んだ寿司の種類の2乗

考え方

X種類の寿司を食べたときの最適解をO(1)で解く。

解き方

貪欲法を使う。

とりあえず、寿司をおいしさ、種類でペアを作る。(pair<d,t>)これをソートする。

美味しい順に寿司をK個取り出す。このとき、以下の操作を行う。

・寿司のおいしさの総和を求める

・同じネタで自分よりもおいしい寿司がない場合、種類を1増やす

・同じネタで自分よりもおいしい寿司がある場合、スタックまたは小さい順に取り出すpriority_queueにおいしさの値を入れる

寿司のおいしさの総和と種類の2乗の和が暫定的な答え。

 

また、美味しい順のK個に含まれていない寿司のうち、同じネタで自分よりもおいしい寿司がない寿司をキューまたは大きい順に取り出すpriority_queueに入れる。

 

これらの操作の後、 キューかスタックが空になるまで以下の操作を繰り返す。

・総和からスタックの1番上の値を引いてキューの1番上の値を足す

・種類を1増やす

・操作後の満足ポイントが答えよりも大きいなら答えを更新

 

最終的に求まった答えを出力。

 

感想

D問題の実装が難しかった。