タグ:codeforces ( 114 ) タグの人気記事

 

のんびりだったけどのんびりじゃない。

今日はお昼時までのんびり。
テレビを見て夕方はCodeforces #327に参加。
いつのまにかレーティング引き上げにより、強制的にDiv2に落とされていました。
しかし、A問題に手間取る。

問題としては、ハリーが速度P、対戦者が速度Qで魔法をキャストする。
距離がLあるとき、一回ぶつかったらお互いに跳ね返って来るが、
もう一度それを跳ね返す。2回めにぶつかった時のハリーからの魔法の距離を求めよ。

ぶっちゃけ当たり前なんだけど1回目と2回目にぶつかったときの距離は一緒なんだよね…。
仮にPが
**** で
Qが
△だとしたら

****△となるけど跳ね返る時も同じ距離、戻ってくる時も同じ距離だからちょっと計算するだけ。
ここが遅かったので保留してB、Cを見ました。

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

public class Main7 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int L = Integer.parseInt(br.readLine());
int p = Integer.parseInt(br.readLine());
int q = Integer.parseInt(br.readLine());
double ft = (double)L / (p+q);
System.out.println(ft * p);

}
}


B問題は、文字の長さと変換回数と文字と変換用文字が与えられていて、
xをyに変換するという動作を変換回数分だけやったとき、
最後の文字列がどうなるかという問題。
愚直にやるのは絶対に間に合わない。さて、どうしたものかということで
考えるのもしんどくなったのでCへ。

そしてCは読めなかったので寝ました。

その後夕食を食べてゲーセンへ。結局ジムにはいけませんでした。

Ignited Night SPECIALでmiss1まで出す。これはフルコンいけそう。
f0019846_2272555.jpg


REVはIroha MASTERをフルコン ULT 100%
f0019846_2275011.jpg


その他Hopes Bright MASTERは99% ULT
f0019846_2281553.jpg


The Four Seasons -SPRING- (Remix Ver.)は意味不明で99% ULTどまり。
f0019846_2284250.jpg


帰路につきすぐ寝ました。

  by ddrer-yossi | 2015-10-25 23:22 | reflec beat | Comments(0)

Google Code JamとかCodeforces #298(div2)とか

一夜明けてGoogle Code Jamの結果が出ていました。

結果は A-Small,large B-Small,large C-Small D-Smallで57点の2150位。

A問題は、x人立ち上がったら立ち上がるような観客が何人かいるとき、
全員立ち上がるようにするには何人引き立て役が必要かという問題。
人数が少ない方から拾っていって、足りなければ順次補って加算していく方式で問題なし。

import java.io.*;

public class A {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2015/io/A-large.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2015/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] shys = input.readLine().split(" ");
int maxshy = Integer.parseInt(shys[0]);
int addfriend = 0;
int stand = 0;
for(int j = 0 ; j <= maxshy ; j++){
if(stand < j){
addfriend += j - stand;
stand += j - stand + Character.digit(shys[1].charAt(j), 10);
}else{
stand += Character.digit(shys[1].charAt(j), 10);
}
}
pw.println("Case #"+(i+1)+": "+addfriend);
}
pw.flush();
input.close();
pw.close();
}
}


B問題は、最初のパンケーキが乗っている状態があって、
皿ごとに一人人がついていて、全員一斉に1枚食べる or 分配するので全員待つという動作をする。
人間は無限人いるとき、皿の上にあるパンケーキが、
すべてなくなるまでの最小時間を求めよという問題。

分け方に関してあれこれ考えると見事にはまっていく問題であり、
後は人数が無限人いることにも気づかないとハマる問題であった。

実は皿に乗るパンケーキは多くても1000という条件があるので、
これをもとに分配していけばいいことになる。

ちなみに最初に分配作業をしきって、後は食べるのを見ているだけというのが正答である。
食べてる途中に分配作業をしても、より良い状態になることはない。
人数は無限人いるので、たとえばパンケーキをN枚以下にするというふうにしたとき、
一人目がM枚(M >= N)あるとき、これをN N ...あまりといった分割にして、
新しい人の皿に載せていくようにする。
その動作回数をN枚より多い皿に対してのみ記録していき、
あとはN回足せば良い(Nより小さければ一番皿に載ってる人の分だけかかる)だけである。

正答率45%の難問でした。

import java.util.*;
import java.io.*;

public class B {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2015/io/B-large.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2015/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
int D = Integer.parseInt(input.readLine());
String[] st = input.readLine().split(" ");
int[] a = new int[D];
for(int j = 0 ; j < D ; j++){
a[j] = Integer.parseInt(st[j]);
}
Arrays.sort(a);
int min = Integer.MAX_VALUE;
for(int j = a[D - 1] ; j >= 1 ; j--){
int tmp = 0;
for(int k = 0 ; k < D ; k++){
if(a[k] > j){
if(a[k] % j != 0){
tmp += a[k] / j;
}else{
tmp += a[k] / j - 1;
}
}
}
tmp += j;
min = Math.min(min, tmp);
}
pw.println("Case #"+(i+1)+": "+min);
}
pw.flush();
input.close();
pw.close();
}
}


C問題は、djkの単位元変換問題。
愚直な実装で作れるかどうか判定していたら間に合わなかったので、
後ろからの計算などを実装することでオーダを省いた。

import java.io.*;

public class CSmall {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2015/io/input.txt"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2015/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] str = input.readLine().split(" ");
int L = Integer.parseInt(str[0]);
long X = Long.parseLong(str[1]);
boolean isok = false;
String st = input.readLine();
StringBuilder sb = new StringBuilder();
for(int j = 0 ; j < X ; j++){
sb.append(st);
}
Status first = new Status();
Status second = new Status();
Status third = new Status();
boolean readl = false;
for(int j = 0 ; j < L * X - 2 ; j++){
first = str(first, new Status(sb.charAt(j), false));
//System.out.println(first.c+","+first.minus+","+"phase1:"+j);
if(first.c != 'i' || first.minus)continue;
for(int k = j + 1 ; k < L * X - 1 ; k++){
second = str(second, new Status(sb.charAt(k), false));
//System.out.println(second.c+","+second.minus+","+"phase2:"+k);
if(readl){
third = str(new Status(sb.charAt(k), true), third);
}
if(second.c != 'j'|| second.minus)continue;
if(!readl){
for(int l = k + 1 ; l < L * X ; l++){
third = str(third, new Status(sb.charAt(l), false));
}
readl = true;
}
if(third.c == 'k' && !third.minus){
//System.out.println(j+","+k+","+sb.length());
isok = true;
break;
}
}
readl = false;
second = new Status();
third = new Status();
if(isok)break;
}
if(isok){
pw.println("Case #"+(i+1)+": YES");
}else{
pw.println("Case #"+(i+1)+": NO");
}
pw.flush();
}
input.close();
pw.close();
}

public static Status str(Status st,Status st2){
if(st.c == 'a')return new Status(st2.c,st.minus);
if(st2.minus){
if(st.minus){
st.minus = false;
}else{
st.minus = true;
}
}
if(st.c == '1'){
if(st2.c == 'i'){
st.c = 'i';
}else if(st2.c == 'j'){
st.c = 'j';
}else if(st2.c == 'k'){
st.c = 'k';
}else if(st2.c == '1'){
st.c = '1';
}
}else if(st.c == 'i'){
if(st2.c == 'i'){
st.c = '1';
if(st.minus){
st.minus = false;
}else{
st.minus = true;
}
}else if(st2.c == 'j'){
st.c = 'k';
}else if(st2.c == 'k'){
st.c = 'j';
if(st.minus){
st.minus = false;
}else{
st.minus = true;
}
}else if(st2.c == '1'){
st.c = 'i';
}
}else if(st.c == 'j'){
if(st2.c == 'i'){
st.c = 'k';
if(st.minus){
st.minus = false;
}else{
st.minus = true;
}
}else if(st2.c == 'j'){
st.c = '1';
if(st.minus){
st.minus = false;
}else{
st.minus = true;
}
}else if(st2.c == 'k'){
st.c = 'i';
}else if(st2.c == '1'){
st.c = 'j';
}
}else if(st.c == 'k'){
if(st2.c == 'i'){
st.c = 'j';
}else if(st2.c == 'j'){
st.c = 'i';
if(st.minus){
st.minus = false;
}else{
st.minus = true;
}
}else if(st2.c == 'k'){
st.c = '1';
if(st.minus){
st.minus = false;
}else{
st.minus = true;
}
}else if(st2.c == '1'){
st.c = 'k';
}
}
return new Status(st.c,st.minus);
}
}

class Status{
boolean minus = false;
char c = 'a';
Status(char c,boolean minus){
this.c = c;
this.minus = minus;
}
Status(){
minus = false;
c = 'a';
}
}


でも本当の正解は、
ijkをいち早く作り上げてしまった上で、残りの計算結果が1になるかどうかで良いということ。
そこに気付かなかったー><
それは後日時間があればやります。

D問題は、テトリスの縦横枠があって、最初の人が5つなら5つつながっているブロックのどれかなんでもいいのを選んで、もう一人が残りを好きなピース(5つなら5つと決まっているが)で、
穴を開けずにはめられるかどうか判定せよという問題。
7つ以上だと
***
*x*
**x
という穴あき確定ピースを作れてしまうので絶対に不可能で良い。
後は6ピース以下の時の判定である。
Smallは一発で通したが、Largeは落としてしまった。

import java.util.*;
import java.io.*;

public class DSmall {
static PrintWriter pw;
public static void main(String args[]) throws Exception{
BufferedReader input = new BufferedReader(new FileReader("../GoogleCodeJam2015/io/D-large-practice.in"));
pw = new PrintWriter(new FileWriter("../GoogleCodeJam2015/io/output.txt"));
int T = Integer.parseInt(input.readLine());
for(int i = 0 ; i < T ; i++){
String[] st = input.readLine().split(" ");
int X = Integer.parseInt(st[0]);
int[] a = {Integer.parseInt(st[1]),Integer.parseInt(st[2])};
Arrays.sort(a);
if(X == 1){
pw.println("Case #"+(i+1)+": GABRIEL");
}else if(X == 2){
if((a[0] * a[1]) % 2 == 0){
pw.println("Case #"+(i+1)+": GABRIEL");
}else{
pw.println("Case #"+(i+1)+": RICHARD");
}
}else if(X >= 7){
pw.println("Case #"+(i+1)+": RICHARD");
}else if(X >= 3){
if(X == 5 && a[0] == 3 && a[1] == 5){
System.out.println(i);
pw.println("Case #"+(i+1)+": RICHARD");
}else if(a[0] >= (X / 2 + 1) && (a[0] % X == 0 || a[1] % X == 0)){
pw.println("Case #"+(i+1)+": GABRIEL");
}else{
pw.println("Case #"+(i+1)+": RICHARD");
}
}
}
pw.flush();
input.close();
pw.close();
}
}


後で聞くと、3*5で5ミノの場合、M字ピースがコーナーケースで入らないとのこと。
***
*xx
xx*
x**
***

このケースを入れて提出してみたものの、正答にならないので諦めました。
取り敢えず予選は通過です。


クロスビーツはNEXT FRONTIER -TRUE RISE-をようやく初クリア。
40回ぐらいやったんじゃないかな。
f0019846_16341159.jpg


残った肉で豪勢に焼肉とかしていました。
f0019846_16345362.png


帰宅後はCodeforces #298にちょっとだけ参戦。
A問題は、n人生徒がいるとき、隣り合う番号にならないようにできる
人数とその配置を出力せよという問題。
n=4のとき、2 4 1 3という配置ができることに気づかず、何度もミスをする。


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

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
if(n == 2){
System.out.println("1");
System.out.println("1");
}else if(n == 3){
System.out.println("2");
System.out.println("1 3");
}else if(n == 4){
System.out.println("4");
System.out.println("2 4 1 3");
}else{
System.out.println(n);
StringBuilder sb = new StringBuilder();
for(int i = 1 ; i <= n ; i += 2){
sb.append(i+" ");
}
for(int i = 2 ; i <= n ; i += 2){
sb.append(i+" ");
}
System.out.println(sb.substring(0,sb.length() - 1));
}
}
}


B問題から先は読まずに寝ました。仕事もあるしね…。

  by ddrer-yossi | 2015-04-12 23:30 | codeforces | Comments(0)

TopCoder SRM654 と Codeforces#297

今日は仕事の合間にTopCoderに参戦。
easyは、連続した文字が何箇所に現れるかを求める問題。
愚直に文字の長さだけ全アルファベットを調べる方式でやりました。時間がかかった。


View SquareScoresDiv2 Problem Statement
public class SquareScoresDiv2 {

public int getscore(String s) {
int count = 0;
for(int i = 0 ; i < 26 ; i++){
String subs = "";
for(int j = 0 ; j < s.length(); j++){
subs += (char)(97 + i);
for(int k = 0 ; k <= s.length() - subs.length(); k++){
if(s.substring(k, k+subs.length()).equals(subs))count++;
}
}
}
return count;
}

}


次はmedium。必ずどこかしらを経由して通れる部屋があることが保障されていて、
その部屋に荷物を詰める。詰めた場合その先の部屋に行けないといった条件のとき、
荷物を置く組み合わせは何通りあるかという問題。
これは難しそうだ・・・と思うと、N = 9という条件に着目する。
あ・・・これ総当りでいけるなと思ったが、実装がだるかったです。
まずすべての順列を作るのがだるい。
結局自分の過去に作ったライブラリを持ってきてやることに。

その後も総当りで調べるコードを書くのが面倒でしたね。時間がかかりすぎました。


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class OneEntrance {
static int sum = 0;
static int sp;
static ArrayList[] list;
public int count(int[] a, int[] b, int s) {
sp = s;
list = new ArrayList[a.length + 1];
for(int i = 0 ; i < list.length ; i++){
list[i] = new ArrayList();
}
String rooms = "";
for(int i = 0 ; i <= a.length ; i++){
if(i != a.length){
list[a[i]].add(b[i]);
list[b[i]].add(a[i]);
}
rooms += i;
}
num(rooms,0,"");
return sum;
}

public static void num(String s,int index,String sub){
for(int i = sub.length() ; i >= 0 ; i--){
StringBuilder sb = new StringBuilder(sub);
if(sub.length() == s.length()){
//System.out.println(list[0].get(0));
boolean isok = true;
boolean[] isclosed = new boolean[s.length()];
for(int j = 0 ; j < sub.length(); j++){

int count = 0;
boolean[] isused = new boolean[s.length()];
isclosed[Character.digit(sub.charAt(j), 10)] = true;

Queue q = new LinkedList();
q.add(sp);

while(!q.isEmpty()){
int num = (Integer)q.poll();
count++;
isused[num] = true;
for(int k = 0 ; k < list[num].size(); k++){
int nextnum = (Integer)list[num].get(k);
if(!isclosed[nextnum] && !isused[nextnum]){
q.add(nextnum);
}
}
}
if(count != s.length() - j){
isok = false;
break;
}
}
if(isok)sum++;
break;
}
sb.insert(i,s.charAt(index)).toString();
num(s,index+1,sb.toString());
}
}
}


3問目は、ある数式が与えられていて、
毎回ある箇所を変更したときに、
カッコを最大2回使ってできる最大値を毎回出力せよという問題。
何か工夫しないとできなさそう。DPっぽい。でも時間も気力もありませんでした。

その後は仕事を順当にこなし、17時には終了。
その後は死んだように寝て、気づいたら21時でした。なんだそりゃ…。

飯を食って早々にジムへ行くも、筋トレ2セットちょっとで時間に。
ゲーセンは2クレ。進捗0。

帰宅後はCodeforcesに参加する。
A問題は、部屋に落ちている鍵と、次に向かうドアの鍵型が与えられていて、
最後の部屋に行くのに、いくつ別の鍵が必要かという問題。
問題文が長いし、鍵を買うとか書いてあるけど、こういう問題でしかなかった。
愚直に鍵を26の配列で管理しつつ、なければカウントしていく方式で良い。

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 n = Integer.parseInt(br.readLine());
String s = br.readLine();
int[] keys = new int[26];
int count = 0;
for(int i = 0 ; i < n - 1 ; i++){
keys[s.charAt(2 * i) - 97]++;
if(keys[s.charAt(2 * i + 1) - 65] == 0){
count++;
}else{
keys[s.charAt(2 * i + 1) - 65]--;
}
}
System.out.println(count);
}
}


B問題は、文字列が与えられていて、対称になる部分を毎回リバースしたとき、
最後にどんな文字列になるか求める問題。
最初、対称になるとは気づかずに愚直にやって、予想通りのTLE。
対称性から、2回リバース対称になると戻るというところに気づかないといけない。
そして更にその判定を全箇所でやっていたら死ぬので、
いもす法を使ってやる。
たとえば6文字で2番目が指定されると、2から5までの文字を反転する必要がある。
2から5までを1ずつインクリメントするのではなく、2に1をインクリメントして、6に-1をインクリメントする。
最後にそれを合計すれば同じ結果になるということ。

普通にやると処理にO(n^2)、ある値を求めるのにO(1)で済むのに対し、
いもす法は、処理がO(2*n)、ある値を求めるのにO(n)程度で済む。
つまりオーダを落とせるので有効だといえよう。


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 s = br.readLine();
int n = Integer.parseInt(br.readLine());
String[] ch_int = br.readLine().split(" ");
int[] number = new int[s.length() + 1];
for(int i = 0 ; i < n ; i++){
int num = Integer.parseInt(ch_int[i]) - 1;
number[num]++;//ここと
number[s.length() - num]--;//ここがいもす法
}
StringBuilder sb = new StringBuilder();
int sum = 0;
for(int i = 0 ; i < number.length - 1 ; i++){
sum += number[i];
if(sum % 2 == 0){
sb.append(s.charAt(i));
}else{
sb.append(s.charAt(s.length() - i - 1));
}
}
System.out.println(sb.toString());
}
}



C問題は、1だけ長さを縮められる棒がいくつかあって、それらを使って
できるだけ大きな長方形を作れるだけ作った面積を求める問題。
もちろん折り曲げてはいけないし、1辺に使える棒は1本。

まあ、ソートして、大きい順から1本目を基準にして、
2本目が1本目と同じか1小さいだけで済むかどうか判定するだけです。
ダメなら2本目を基準にして・・・というのが2本できた時点で長方形を作っていくだけです。
99886622のペアがあったら、9*8 + 6*2が最大になりますからね。

複数作れることに気付かず、2WAです。


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

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] ch_int = br.readLine().split(" ");
int[] length = new int[n];
for(int i = 0 ; i < n ; i++){
length[i] = Integer.parseInt(ch_int[i]);
}
Arrays.sort(length);
int stnum = -1;
long sum = 0;
ArrayList size = new ArrayList();
for(int i = n - 1 ; i >= 0 ; i--){
if(stnum == length[i]){
size.add(stnum);
stnum = -1;
}else if(stnum == length[i] + 1){
size.add(length[i]);
stnum = -1;
}else{
stnum = length[i];
}
if(size.size() == 2){
sum += (long)size.get(0) * (long)size.get(1);
size.clear();
}
}
System.out.println(sum);
}
}


D問題は、二次元平面上に壁と空きスペースが与えられている時、
すべての区画が長方形の間取になるときに、取り除く必要のある壁の枚数が最も少なくなる
場合の、二次元平面を出力せよという問題。見るからに難しい。

E問題は、箱に数字がラベリングされていて、!シールが何枚かあるので、
これを箱に貼って、いくつかの箱を選んだ和が
丁度Sになるような選び方が何通りあるかという問題。

1 1 1で1枚持っているときは、
貼らずにどれかの箱を選ぶのが3通りで、
選ぶ箱に貼って選ぶのが1!となるのでこれも3通りあるということ。
どこかに貼って、それを選ばないという組み合わせはNGのようであり、
あくまで選んでるものの組み合わせを考慮すればいいとか。

見るからにSの条件はlong程度の値なので、18!程度ぐらいまでしか組み合わせはなさそう。
でも箱は25個あるし総当りはきついなー、時間的に眠いなーということで寝ました。
どうせUnrated。

寝る前にFrgmntsのMasterをシェアであったのでやりました。難しいねこれ。
f0019846_21581059.jpg

  by ddrer-yossi | 2015-03-26 23:39 | TopCoder | Comments(0)

Codeforces Round #288 (Div. 2)に参加

今日も仕事。お昼は三種まぐろ丼。
f0019846_2173072.jpg


仕事後は、飯食ってジムへ。
有酸素運動 + 60minのつもりでしたが、
引き続きしんどさがあり、30minを2セットとなりました。いずれも10.1km/h。

ゲーセンは、TOXIC VIBRATION(H)をフルコン。
f0019846_2182954.jpg


偶然にも少年A(H)をフルコン。低速地帯も等速で通った。
f0019846_2185940.jpg


リフレクはGimme a Big Beat (Hommarju Remix)で95.8% AAA+
f0019846_2193866.jpg


帰宅後はCodeforcesに参戦。

A問題は、N*Mの2次元平面上に、
座標を黒く塗りつぶしていく。
2*2の正方形ができてしまったら負けで、負けの瞬間のターン数を導く問題。
ただし勝ちであれば-1を返す。

最初は、塗りつぶす毎に判定すればいいかなと思いましたが、
1000*1000*100000は割に合わないし間に合わない。
どうしようどうしようと一番考えていた気がします。
結局塗りつぶした近場4箇所だけ判定すれば良いのです。
塗りつぶし箇所がoなら
xx
xo

xx
ox

xo
xx

ox
xxです。

で、角っこの条件を複雑に書いてしまって、見事にSystemTestで落ちる。
よく考えたら囲いを作る(N+2,M+2)にすることで、
複雑な条件書きを回避できることがすぐに思いついた。
つまりフィールドが
ooo
ooo
ooo
oooであれば

xxxxx
xooox
xooox
xooox
xooox
xxxxx となる。 3*4→5*6である。


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[] s = br.readLine().split(" ");
int N = Integer.parseInt(s[0]);
int M = Integer.parseInt(s[1]);
int K = Integer.parseInt(s[2]);
int[] x = new int[K];
int[] y = new int[K];
for(int i = 0 ; i < K ; i++){
s = br.readLine().split(" ");
y[i] = Integer.parseInt(s[0]);
x[i] = Integer.parseInt(s[1]);
}
boolean[][] ban = new boolean[N + 2][M + 2];
int count = 0;
boolean lose = false;
for(int i = 0 ; i < K ; i++){
count++;
ban[y[i]][x[i]] = true;
if(chosa(x[i],y[i],ban)){
lose = true;
break;
}
}
if(lose){
System.out.println(count);
}else{
System.out.println("0");
}
}

public static boolean chosa(int x,int y,boolean[][] ban){
if(ban[y][x - 1] && ban[y - 1][x - 1] && ban[y - 1][x])return true;
if(ban[y - 1][x] && ban[y - 1][x + 1] && ban[y][x + 1])return true;
if(ban[y][x - 1] && ban[y + 1][x - 1] && ban[y + 1][x])return true;
if(ban[y + 1][x] && ban[y + 1][x + 1] && ban[y][x + 1])return true;
return false;
}
}


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 s = br.readLine();
boolean ok = false;
int kouhoindex = -1;
for(int i = 0 ; i < s.length() -1 ; i++){
int num = Character.digit(s.charAt(i), 10);
if(num % 2 == 0)
if(num < Character.digit(s.charAt(s.length() - 1), 10)){
ok = true;
System.out.println(s.substring(0,i)+s.charAt(s.length() - 1)+s.substring(i + 1,s.length() - 1)+s.charAt(i));
break;
}else{
kouhoindex = i;
}
}

if(!ok){
if(kouhoindex != -1){
System.out.println(s.substring(0,kouhoindex)+s.charAt(s.length() - 1)+s.substring(kouhoindex + 1,s.length() - 1)+s.charAt(kouhoindex));
}else{
System.out.println("-1");
}
}
}
}


C問題は、ゴーストがmだけ現れて、t秒だけ光るろうそくがある。
ろうそくは1秒ごとにおける。1秒後に光り、t秒後に消滅する。
1ゴーストあたりr本のろうそくが光っている必要があるとき、必要なろうそくの本数を求めよ。

制約が300秒なので、全探索で余裕で行けると思ったので、
キューを使って書きました。配列を使って書くこともできそうですが、バグってうまくいかず。
t < rのときは、どうあがいても先にろうそくが消えてしまい、r本に到達しないのでNG。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(" ");
int m = Integer.parseInt(s[0]);
int t = Integer.parseInt(s[1]);
int r = Integer.parseInt(s[2]);
s = br.readLine().split(" ");
int[] w = new int[m];
for(int i = 0 ; i < m ; i++){
w[i] = Integer.parseInt(s[i]);
}
int num = 0;
if(t < r){
System.out.println(-1);
}else{
Queue q = new LinkedList();
for(int i = 0 ; i < w.length ; i++){
int counter = 0;
int qsize = q.size();
for(int j = 0 ; j < qsize ; j++){
int a = q.poll();
if(a >= w[i]){
q.add(a);
counter++;
}
}
for(int j = w[i] - (r - counter - 1) - 1 ; j <= w[i] - 1 ; j++){
q.add(j + t);
num++;
}
}
System.out.println(num);
}
}
}


とまあ、残念な感じでした。

  by ddrer-yossi | 2015-01-27 23:16 | codeforces | Comments(0)

焼肉を焼く時、肉もまた財布を焼いているのだ Codeforces #261

今日はお昼はそばを食べる。
夕方ごろに移動し、一旦ゲーセン。

その後は都内某所へ。無印でジム用のタオルを買いつつ、
焼肉屋で集合した。

f0019846_301683.jpg


f0019846_302547.jpg


f0019846_30357.jpg


f0019846_304182.jpg


f0019846_305032.jpg


f0019846_305977.jpg


その後は日本でも有数のものすごいPCを自宅に保持している某所へ向かい、
アルゼンチンビールで乾杯。
物に対するこだわりっぷりにものすごく惹かれました。わかる。

帰宅後はCodeforcesに参戦。
A問題は、頂点が2つ与えられているから、残りの2点を使って正方形が作れるなら
残り2点の座標を出力し、ダメなら-1を出力せよという問題。
なんか凝りすぎて結局SysTestで落ちています。

B問題は、花の美しさが与えられるので、2本ピックアップして、
差異が最も大きくなるその値を出力し、その組み合わせが何通りあるか求めよという問題。

よく考えれば間を取る必要がないので、ソートして、
最小値と最大値が一致するものがいくつあるか計算して、掛け算をする。


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

public class Main2 {

public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
int[] a = new int[n];
for(int i = 0 ; i < a.length ; i++){
a[i] = Integer.parseInt(s[i]);
}
Arrays.sort(a);
int minx = a[0];
int maxx = a[n-1];

if(minx == maxx){
System.out.println("0 "+(long)n*(n-1)/2);
}else{
int index = 0;
int mincount = 0;
while(index != n){
if(a[index] == minx){
mincount++;
index++;
}else{
break;
}
}

index = n-1;
int maxcount = 0;
while(index != 0){
if(a[index] == maxx){
maxcount++;
index--;
}else{
break;
}
}
System.out.println((maxx-minx)+" "+(long)mincount*maxcount);
}
}

}

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

進捗なし。帰宅後即codeforces #258(div2)

今日も開発。反省点が活かされていたのでチーム全体の進みも悪くないものでした。

お昼だけがっつり食っていました。
f0019846_195092.jpg


夜はいつもどおりジムに行き、お腹のシェイプアップを行う。
有酸素運動して、音ゲーは1クレずつやって帰宅。

そしてCodeforcesの準備。

A問題は単純に交わる点がなくなったら負けということで、
1本取り除くと、確実に縦も横も1減るので、最大値だけ見ると良い。
線が少ない方を2で割った余りが0ならば後手のMalvika、1ならば先手のAkshatの勝利。


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 a = Integer.parseInt(st[0]);
int b = Integer.parseInt(st[1]);
if(Math.min(a, b) % 2 == 0){
System.out.println("Malvika");
}else{
System.out.println("Akshat");
}

}
}


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));
int n = Integer.parseInt(br.readLine());
String[] st = br.readLine().split(" ");
int[] a = new int[n];
boolean isok = true;
for(int i = 0 ; i < n ; ++i){
a[i] = Integer.parseInt(st[i]);
}
int bnum = 0;
int nownum = 0;
boolean ishen = false;
int hennum = 0;
boolean henned = false;
isok = true;
int sta = 0;
int en = 0;
for(int i = 0 ; i < n ; i++){
if(!ishen && nownum < a[i]){
nownum = a[i];
}else if(!henned && !ishen){
ishen = true;
if(i != 1)bnum = a[i-2];
hennum = a[i];
henned = true;
sta = i-1;
en = i;
}else if(ishen){
en = i;
if(a[i] < hennum){
hennum = a[i];
}else{
if(nownum < a[i]){
nownum = a[i];
ishen = false;
en = i-1;
}else{
isok = false;
break;
}
}
}else{
isok = false;
break;
}
}
if(ishen && sta != 0 && bnum > a[n-1]){
System.out.println("no");
}else if(isok){
System.out.println("yes");
System.out.println((sta+1)+" "+(en+1));
}else{
System.out.println("no");
}

}
}

  by ddrer-yossi | 2014-07-24 23:37 | codeforces | Comments(0)

タイピング大会とCodeforces #253

今日は朝から社員大会のため直帰。
お昼はフォーラムの近場でラーメンを食べる。
f0019846_6284155.jpg


その後はTopCoderを犠牲にして、パーティーに参加。
そしてタイピング大会は出場し、優勝しておきました。
昔とった杵柄ですな(えっ
景品お菓子だったし、リアルに要らない奴や…。金くれ金!

最後まで参加していましたが、結局抽選は当たらず。
どうでもいい同期があたっていたのでクソゲーかと思った。

帰宅前にゲーセン少々。

Flip Flap SPECIAL 97.1%
f0019846_6303364.jpg


その後はCodeforcesに参加。元気だね私…。

A問題は、単純に使われている文字の種類を数え上げるだけ。
小文字しか使われないのでその辺だけ考えれば良い。

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

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
boolean[] set = new boolean[26];
for(int i = 0 ; i < s.length(); i++){
if(s.charAt(i) >= 97 && s.charAt(i) <= 122){
set[s.charAt(i) - 97] = true;
}
}
int count = 0;
for(int i = 0 ; i < set.length ; i++){
if(set[i])count++;
}
System.out.println(count);
}


}


B問題は、2nの部分文字列が、2回繰り返しになるようにする追加アルファベット数を求める問題。


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

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int k = Integer.parseInt(br.readLine());
for(int i = 0 ; i < k ; i++){
s += "*";
}
int maxc = 0;
for(int i = 0 ; i < s.length() ; i++){
for(int j = i ; j < (s.length()-i)/2 + i ; j++){
int pre = j - i + 1;
boolean isok = true;
for(int l = i ; l < j ; l++){
if(s.charAt(l) == s.charAt(l+pre) || s.charAt(l+pre) == '*' || s.charAt(pre) == '*'){

}else{
isok = false;
break;
}
}
if(isok){
maxc = Math.max(maxc, pre);
}
}
}
System.out.println(maxc*2);
}


}

始点と終点をキメて総当りでOK。200程度なのでO(n^3)は(200^3)で間に合う。

C問題は、色のヒントもしくは数字のヒントをもらって、すべてのカードを一意に識別できる
最短を求める問題。今考えたけど実は総当りでいけるんじゃないかと。
それだけじゃダメですが。

D問題は、質問に答えてくれる確率が人によって与えられているので、
Andreyは聞くか聞かないか選べる。
その時に答えを返してくれる最大の確率を求めよという問題。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
double[] nums = new double[n];
for(int i = 0 ; i < n ; i++){
nums[i] = Double.parseDouble(s[i]);
}
Arrays.sort(nums);
if(nums[n-1] >= 0.5){
System.out.println(nums[n-1]);
}else{
int index = 0;
while(index < n){
if(nums[index] < 0.5){
index++;
}else{
break;
}
}
double sumper = 0;
for(int k = 0 ; k < index ; k++){
for(int l = k ; l < index ; l++){
double sumper2 = 0;
for(int i = k ; i <= l ; i++){
double tmpsum = 1;
for(int j = k ; j <= l ; j++){
if(j == i){
tmpsum *= nums[j];
}else{
tmpsum *= (1-nums[j]);
}
}
sumper2 += tmpsum;
sumper = Math.max(sumper, sumper2);
}
}
}
System.out.println(sumper);
}
}


}


nが100程度なのでO(n^4)は1000万程度でいける。
ちなみにどれかの確率が0.5以上なら、掛けあわせで0.5より大きくなることはない
(0.5*0.5+0.5*0.5が最大)のでその値を出力する(テストケース1)
ソートして0.5より大きくなる最初のインデックスを見つける。
後はある範囲からある範囲に対して聞いて、ある範囲まで聞いてくれなくて、どこかで聞いてくれる
という計算をしたときの、最大となる確率を求めていく。

1589 -> 1725(34th、部屋内1位)でついに念願のDiv1に。これからやらなくなりそうですね…。
明日はサッカーがあるので早めに寝ます(2時半過ぎ。

  by ddrer-yossi | 2014-06-19 23:27 | codeforces | Comments(0)

石巻二日目、コドフォ参加

ダブル人狼から一夜明けて、朝食は控えめに。
f0019846_11154974.jpg


その後は視察に行きました。
f0019846_11163674.jpg


f0019846_11165666.jpg


f0019846_11174938.jpg


f0019846_1118911.jpg


この辺り(漫画館付近)は震災の凄惨さがよくわかります。

ありがとうハウス
f0019846_11185340.jpg


f0019846_1119556.jpg


大川小学校
f0019846_11213978.jpg


お昼はうまいもんやで海鮮丼を頂きました。
f0019846_11223382.jpg


f0019846_11225045.jpg


震災から3年、復興の頑張りもあって、取り戻してきている感じがありましたが、
まだ一部の箇所ではその生々しい状態が残されていました。

f0019846_1124298.jpg


帰ります。仙台駅で牛タンたべる時間がとれなかったので、弁当で。
f0019846_1125784.jpg


夜は仲間内とPUBで飲みました。一杯だけ。
f0019846_11253895.jpg


おみやげとか。
f0019846_11262124.jpg


飲んだ後でもCodeforcesに気合で参加しました。

A問題は、初期状態ではXのジャンプが可能で、飴が0と1の二種類ある。
それぞれに高さと量が与えられていて、プレイヤーはジャンプで届く高さの飴が食べられる。
食べた量だけジャンプ力が増す。
飴は二種類あり、交互に食べる必要がある。最大何個食べられるか。

これは両方で試し、量が多く取れるものから取っていけば良い。

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[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int x = Integer.parseInt(s[1]);
int[] t = new int[n];
int[] h = new int[n];
int[] m = new int[n];
boolean[] used = new boolean[n];
for(int i = 0 ; i < n ; i++){
s = br.readLine().split(" ");
t[i] = Integer.parseInt(s[0]);
h[i] = Integer.parseInt(s[1]);
m[i] = Integer.parseInt(s[2]);
}
int t_candy = 0;
int type = 0;
int stlength = x;
while(true){
int maxcouho = 0;
int maxindex = -1;
for(int j = 0 ; j < n ; j++){
if(!used[j]){
if(t[j] == type && stlength >= h[j]){
if(maxcouho < m[j]){
maxcouho = m[j];
maxindex = j;
}
}
}
}
if(maxindex == -1)break;
used[maxindex] = true;
stlength += maxcouho;
t_candy++;
if(type == 0){
type = 1;
}else{
type = 0;
}
}

used = new boolean[n];
int m_candy = 0;
type = 1;
stlength = x;

while(true){
int maxcouho = 0;
int maxindex = -1;
for(int j = 0 ; j < n ; j++){
if(!used[j]){
if(t[j] == type && stlength >= h[j]){
if(maxcouho < m[j]){
maxcouho = m[j];
maxindex = j;
}
}
}
}
if(maxindex == -1)break;
used[maxindex] = true;
stlength += maxcouho;
m_candy++;
if(type == 0){
type = 1;
}else{
type = 0;
}
}
System.out.println(Math.max(t_candy, m_candy));
}
}



B問題は、最上段のセルから下に向かって移動するとき、
方向が定まっている蜘蛛といくつ遭遇するかという問題。
もちろんシミュレーションする余裕はないし、
蜘蛛ごとに調べることも制約条件上できない。
気づけば簡単だが、プレイヤーがある位置にいるときに、
その前の位置に蜘蛛がいるかどうかを判定すれば良い。
つまり

P
*
**L

のようなとき、Pが2マス下に行った時、遭遇する蜘蛛は右2つにLがあるか、
下2つにUがあるかの2通りである。一度遭遇した蜘蛛は再度遭遇することはない。
こうするとマス目*条件分岐(Dは絶対遭遇しないのでLRUだけ考える3つ)より、
2000*2000*3 = 12000000で通せる。


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[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
int k = Integer.parseInt(s[2]);
String[] str = new String[n];
for(int i = 0 ; i < n ; i++){
str[i] = br.readLine();
}
int[] counted = new int[m];
for(int i = 0 ; i < m ; i++){
int count = 0;
for(int j = 1 ; j < n ; j++){

if(i-j >= 0 && str[j].charAt(i-j) == 'R'){
count++;
}

if(i+j < m && str[j].charAt(i+j) == 'L'){
count++;
}

if(j+j < n && str[j+j].charAt(i) == 'U'){
count++;
}
}
counted[i] = count;
}
for(int i = 0 ; i < counted.length ; i++){
if(i != counted.length-1){
System.out.print(counted[i]+" ");
}else{
System.out.println(counted[i]);
}
}
}

}


ここまでやって気力がなくなってしまい、やめた。

  by ddrer-yossi | 2014-06-13 23:13 | 旅行 | Comments(0)

同期飲み Codeforces #249(div2)

今日も開発、ひと通りやれるところまで終わり、
明日はコードレビューというところまで。

お昼はフカヒレチャーハンとやらを大量に食べる。
f0019846_24546.jpg


夜は同期とカラオケからの鳥貴族。
酒のつまみがIPv6とか。

夜はゲーセンに知り合いが多かったですが、Codeforces #249に参加のため、離脱。

A問題は、nグループとm人乗れるバスがあり、
グループの順序は変えられない。
グループの一部が乗れないということがないように、番号の若い順番から載せるとき、
バスは何台必要かという問題。
単純に加算オーバーのときは、カウントをリセットしてインクリメントするだけ。


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[] s = br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
s = br.readLine().split(" ");
int[] a = new int[n];
for(int i = 0 ; i < n ; i++){
a[i] = Integer.parseInt(s[i]);
}
int num = 1;
int bus = m;
for(int i = 0 ; i < n ; i++){
if(a[i] > bus){
i--;
bus = m;
num++;
}else{
bus -= a[i];
}
}
System.out.println(num);
}
}


B問題は、与えられた数で、隣り合う数字をk回スワップ可能なので、
最大値がいくつになるか求めるという問題。
一番左の数と、交換できる候補を探す(候補は一番左より大きく、かつ同値であれば、より距離的に近いものを候補とする)
交換後はインデックスを1つずらす。
同じことを繰り返す、で最大値が求まる。


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[] s = br.readLine().split(" ");
StringBuilder num = new StringBuilder(s[0]);
int k = Integer.parseInt(s[1]);
int index = 0;
boolean moved = true;
while(index != num.length()){
moved = false;
int kouhoindex = index;
int kouhonum = num.charAt(index) - 48;
//System.out.println(kouhonum);
for(int i = index+1 ; i < num.length(); i++){
if(kouhonum < num.charAt(i) - 48){
if(i - index <= k){
kouhonum = num.charAt(i) - 48;
kouhoindex = i;
moved = true;
}
}
}
//System.out.println(index+","+moved+","+kouhonum);
if(moved){
num = new StringBuilder(num.substring(0, index) + String.valueOf(kouhonum) + num.substring(index,kouhoindex) + num.substring(kouhoindex+1,num.length()));
k -= kouhoindex - index;
//System.out.println(num);
}
index++;
}
System.out.println(num);
}
}


C問題は、見た目通り折れ線を出力する問題。
書き方は色々ありますが、コーナーケースには注意しましょう(最小値や最大値の取り方


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 n = Integer.parseInt(br.readLine());
String[] s = br.readLine().split(" ");
int[] a = new int[n];
for(int i = 0 ; i < n ; i++){
a[i] = Integer.parseInt(s[i]);
}
int[] kekka = new int[n+1];
int[] kekkayoko = new int[n+1];
kekka[0] = 0;
kekkayoko[0] = 0;
int sum = 0;
int max = Integer.MIN_VALUE;
int min = 0;
int tate = 0;
for(int i = 0 ; i < n ; i++){
if(i % 2 != 1){
sum += a[i];
}else{
sum -= a[i];
}
kekka[i+1] = sum;
tate += a[i];
kekkayoko[i+1] = tate;
max = Math.max(kekka[i+1], max);
min = Math.min(kekka[i+1], min);
}
int[][] kousi = new int[max-min+1][tate+1];
int start = 0;
int startyoko = 0;
for(int i = 0 ; i < a.length ; i++){
if(start < kekka[i+1]){
for(int j = startyoko ; j < kekkayoko[i+1] ; j++){
//System.out.println((max-start-(j-startyoko))+","+j+","+max+","+start+","+startyoko);
kousi[max-start-(j-startyoko)][j] = 1;
}
startyoko = kekkayoko[i+1];
start = kekka[i+1];
}else{
for(int j = startyoko ; j < kekkayoko[i+1] ; j++){
//System.out.println((max-start+j-startyoko)+","+j+","+max+","+start+","+startyoko);
kousi[max-start+j-startyoko+1][j] = 2;
}
startyoko = kekkayoko[i+1];
start = kekka[i+1];
}
}

for(int i = 1 ; i < max-min+1 ; i++){
StringBuilder sb = new StringBuilder();
for(int j = 0 ; j < tate ; j++){
if(kousi[i][j] == 0){
sb.append(" ");
}else if(kousi[i][j] == 1){
sb.append("/");
}else if(kousi[i][j] == 2){
sb.append("\\");
}
}
System.out.println(sb);
}
}
}

  by ddrer-yossi | 2014-05-30 23:03 | codeforces | Comments(0)

Codeforces #247(div2)

今日は仕事ではシステム設計を主に担当(短め。
かなりの苦戦を強いられていた。

お昼はバリカタ醤油ラーメン。
f0019846_185569.jpg


夜はゲーセンに少し

We are Disっ娘よっつ打ち命(A) フルコン
f0019846_194356.jpg


リフレクはexamination leave 97.8%
f0019846_1101346.jpg


True Blue 88.5% 微更新
f0019846_1104219.jpg


DIVAはコンテストをプレー。

炉心融解EXTREME 105.06% fine5
f0019846_1111430.jpg


SYMPHONIC DIVE HARD 106.06% fine 1
f0019846_1121954.jpg


ミラクルペイント HARD 102.85% fine13
f0019846_113341.jpg


そいやっさぁ! HARD 105.65% fine10
f0019846_1132713.jpg


ワールズエンド・ダンスホール NORMAL 105.76% fine3
f0019846_1135540.jpg


*ハロー、プラネット。 NORMAL 105.00% fine11
f0019846_1142547.jpg


帰宅後はコドフォ前にパラレルスペックを99%更新。
f0019846_1152370.png


コドフォはA問題は1,2,3,4の数字にそれぞれ配点があり、数字が与えられるときの、
合計点を求めるという問題。
左からなめていって合計を求めるだけ。


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[] s = br.readLine().split(" ");
String st = br.readLine();
int[] a = new int[4];
for(int i = 0 ; i < 4 ; i++){
a[i] = Integer.parseInt(s[i]);
}
int sum = 0;
for(int i = 0 ; i < st.length(); i++){
sum += a[Character.digit(st.charAt(i), 10)-1];
}
System.out.println(sum);
}

}


B問題は、5人の人が居て、隣り合った人同士はしゃべることで幸福を得る。
並び順を変えることができるとき、その合計値を最大化したものを求めよという問題。
愚直に全部試しましょう。全部で5!通りです。


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));
int[][] grad = new int[5][5];
for(int i = 0 ; i < 5 ; i++){
String[] s = br.readLine().split(" ");
for(int j = 0 ; j < 5 ; j++){
grad[i][j] = Integer.parseInt(s[j]);
}
}
int sum = 0;
for(int i = 0 ; i < 5 ; i++){
for(int j = 0 ; j < 5 ; j++){
for(int k = 0 ; k < 5 ; k++){
for(int l = 0 ; l < 5 ; l++){
for(int m = 0 ; m < 5 ; m++){
if(i == j || i == k || i == l || i == m || j == k || j == l || j == m || k == l || k == m || l == m )continue;
int tmp = grad[i][j] + grad[j][i] + grad[k][l] + grad[l][k] + grad[j][k] + grad[k][j] + grad[l][m] + grad[m][l] + grad[l][m] + grad[m][l] + grad[k][l] + grad[l][k];
sum = Math.max(tmp, sum);
}
}
}
}
}
System.out.println(sum);
}

}


C問題は途中で眠くなって離脱しました。起きてから問題文を理解するという感じ。
すべてのノードはk個の子ノードを持ち、K個の枝にそれぞれ1,2,...kの重みがついている。
ルートを始点として末端まで通る重みが丁度nで、少なくとも1つはd以上の重みを通る
組み合わせを求めよという問題。

  by ddrer-yossi | 2014-05-21 23:07 | codeforces | Comments(0)

SEM SKIN - DESIGN by SEM EXE