DP八段取得! Codeforces #236

今日は休みを生かしてお昼ごろに起きました(違
クロスビーツはLotusと逆転裁判で記録を若干更新。

自分の中でDP流行りなのでラスストの練習。
f0019846_1392431.jpg


その後はリベンジのためゲーセンへ。
そして漸く…。
f0019846_1406100.jpg


f0019846_1402551.jpg

やりました!DP八段です!震えが止まらない。

その後はユミル(A)難
f0019846_1405759.jpg


f0019846_141956.jpg

いやーいいっすね^ー^

気分がいいので、リフレクへ。
HYENA 84.0% 更新
f0019846_1414076.jpg


夜は急遽誘われて夕飯を食べに行った。
牛すじ煮込み丼らしいです。
f0019846_1421020.jpg


その後はDIVA。新曲とコンテストをこなす。
SING & SMILE EXTREME 102.13% fine56
f0019846_1424075.jpg


おなじみの愛言葉 EXTREME 105.70% fine6 更新ではない
f0019846_143785.jpg


Ievan Polkka EXTREME 103.51% fine6 これも更新ではない
f0019846_1434615.jpg


ワールズエンド・ダンスホール HARD 103.45% fine15 これは更新
f0019846_1441154.jpg


愛言葉 HARD 105.93% fine2
f0019846_1443637.jpg


ワールズエンド・ダンスホール NORMAL 105.82% fine2
f0019846_145898.jpg


そして愛言葉 NORMAL 105.71% fine0(ALL COOL)を取る。
f0019846_1454264.jpg


ジュゲムシーケンサー NORMAL 104.92% fine7
f0019846_1461465.jpg


弐寺に戻ってみる。
Ganymede(H)を等速で漸く難。
f0019846_1464424.jpg


jubeatもやってました。

METROPOLIS初見93.5k
f0019846_1471718.jpg


Shine On Me 99.2k
f0019846_1474088.jpg


とまあ、ゲーセン三昧でした。
帰宅後はCodeforces #236(div2)に参戦。

A問題は、a個のナッツとたくさんの箱を持っている。
箱はx個の仕切りを置くと、スペースがx+1個になる。
箱のスペースをkより多くするのも嫌だが、ナッツをv個より多く入れるのも嫌である。
b個の仕切りを持っているが、なるべく箱を使う数を少なくしたい。
その時の箱の数は?

結論、詰められるだけ詰める。仕切りも使えるだけ使う。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] st = br.readLine().split(" ");
int k = Integer.parseInt(st[0]);
int a = Integer.parseInt(st[1]);
int b = Integer.parseInt(st[2]);
int v = Integer.parseInt(st[3]);
int num = (int)Math.ceil((double)a/v);
int box = 1;
int count = 0;
while(num != 0){
if(b > 0 && count < k){
if(count != 0)b--;
count++;
}else{
box++;
count = 1;
}
num--;
}
System.out.println(box);

}
}


B問題は、木の配列があって、以下の動作が行える。
・ある木を任意の長さに伸ばす
・ある木を任意の長さに短くする
等差kで単調増加する等差数列に木を整えろという問題。

どこを始点にするかによっても結果が変わるので、全部やってみましょう。
やった上で、一番作業が少なくなるものを出力しましょう。
複数答えがある場合は、どれでも結構です。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] st = br.readLine().split(" ");
int n = Integer.parseInt(st[0]);
int k = Integer.parseInt(st[1]);
int[] a = new int[n];
st = br.readLine().split(" ");
for(int i = 0 ; i < n ; i++){
a[i] = Integer.parseInt(st[i]);
}
ArrayList great = new ArrayList();
int minturn = Integer.MAX_VALUE;
for(int i = 0 ; i < n ; i++){
ArrayList tmpgreat = new ArrayList();
int start = a[i];
int turn = 0;
boolean isok = true;
for(int j = 0 ; j < n ; j++){
if(i == j)continue;
if(start-(i-j)*k <= 0){
isok = false;
break;
}
if(start-(i-j)*k != a[j]){
turn++;
if(a[j] - (start-(i-j)*k) > 0){
tmpgreat.add("- "+(j+1)+" "+(a[j] - (start-(i-j)*k)));
}else{
tmpgreat.add("+ "+(j+1)+" "+((start-(i-j)*k) - a[j]));
}
}
}
if(!isok)continue;
if(turn < minturn){
minturn = turn;
great = tmpgreat;
}
}
System.out.println(minturn);
for(int i = 0 ; i < great.size(); i++){
System.out.println(great.get(i));
}
}
}


C問題は、
数N,Pが与えられる。
N点と(2N+P)辺からなるグラフを作りたい。
この時、N点中任意のK点を選ぶと、それらの間の辺が2K+P以下になるようにしたい。
そのようなグラフを答えよ。

で、でたーグラフ…と思いましたが、条件を見ると、
結局手当次第順番に張っていけばいいことに気づきます。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for(int i = 0 ; i < t ; i++){
String[] st = br.readLine().split(" ");
int n = Integer.parseInt(st[0]);
int p = Integer.parseInt(st[1]);
int number = 2*n+p;
int count = 0;
for(int j = 1 ; j < n ; j++){
for(int k = j+1 ; k <= n ; k++){
if(count == number)break;
System.out.println(j+" "+k);
count++;
}
if(count == number)break;
}
}
}
}


D問題は、
数列A(1-N)がある。また悪い素数の一覧B[i]がある。
悪い素数の一覧B[i]に含まれない素数はよい素数である。

F(x)=(xを素因数分解したときのよい素数の数)-(xを素因数分解したときの悪い素数の数) と定義する。

ここで、1≦R≦NとなるRに対し、
g=gcd(A[1]~A[R])を求め、A[1]~A[R]をgで割る、
という処理を任意回数行えるとする。
その時の最終的なF(A[i])の総和を最大化せよ。

色々考えていましたが、結局TLEで終わりました。

  by ddrer-yossi | 2014-03-16 23:02 | codeforces | Comments(0)

<< 新潟旅行? 一日目~様々な日本... DP練。八段大敗北 >>

SEM SKIN - DESIGN by SEM EXE