カテゴリ:codeforces( 95 )

 

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)

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)

同期飲み 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)

Code-Strike予選とか

今日も仕事。報連相とかその辺のワーク。結構重かった。
お昼は光麺。ぬるかった。

f0019846_10493589.jpg


夜はゲーセン。
MARIA(I believe...)(H)フルコン
f0019846_10501886.jpg


太陽の子 87.5% miss1
f0019846_10505022.jpg


Codeforcesは、

A問題は、5文字以上、大文字、小文字、数字を含むパスワードであれば
Correctを返し、そうでなければToo weakを返す問題。やるだけ。


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 str = br.readLine();
boolean[] isok = new boolean[3];
if(str.length() < 5){
System.out.println("Too weak");
}else{
for(int i = 0 ; i < str.length(); i++){
char c = str.charAt(i);
if(48 <= c && c <= 57){
isok[0] = true;
}else if(65 <= c && c <= 90){
isok[1] = true;
}else if(97 <= c && c <= 122){
isok[2] = true;
}
}
boolean correct = true;
for(int i = 0 ; i < isok.length ; i++){
if(!isok[i]){
correct = false;
break;
}
}
if(correct){
System.out.println("Correct");
}else{
System.out.println("Too weak");
}
}

}


B問題は、
N個のプロセッサがM個の処理を時間順に行って、
プロセッサpは時刻qにメモリX[p][q]をロックする。

同じメモリを2つ以上のプロセッサがロックしようとすると、
各プロセッサはデッドロックで以降の動作をやめる。
また、以後そのメモリを触ったプロセッサも同様にそれ以降の動作をやめる。
各プロセッサはいつまで動き続けることができるか。

やるだけのはずが通らず。

C問題も簡単だったそうですが、見ずに寝ました。

  by ddrer-yossi | 2014-04-14 23:46 | codeforces | Comments(0)

Codeforces #239 div2

今日は全国的に大雨。

16時からCodeforces #239 div2に参加。

A問題は、Vasyaは買い物をするのにn箇所から1つ選んでレジに並ぶ。
i番目のレジには既にki人が並んでいて、
j番目の人はmi,jの商品を持って並んでいる。
レジ打ちは1商品5秒かかって、すべて終わったら支払いで15秒かかる。
自分の番になるまでの最短秒数を求めよ。

全部のレジに関してシミュレートすればよい。

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());
int[] num = new int[n];
String[] s = br.readLine().split(" ");
for(int i = 0 ; i < n ; i++){
num[i] = Integer.parseInt(s[i]);
}
int mintime = Integer.MAX_VALUE;
for(int i = 0 ; i < n ; i++){
int tmptime = 0;
String[] st = br.readLine().split(" ");
for(int j = 0 ; j < num[i] ; j++){
tmptime += Integer.parseInt(st[j])*5;
}
tmptime += num[i]*15;
mintime = Math.min(tmptime,mintime);
}
System.out.println(mintime);
}
}


B問題は、与えられたアルファベットの紙(1平方)を使って、
下のようなアルファベットのかざりになるようにしろという問題。
切っていいし、使わないものがあってもよい。

つまり、多すぎる部分は1平方でいいし、少なすぎる部分は切って全部使う。
存在しないものがある場合は問答無用で-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();
String e = br.readLine();
int[] num = new int[26];
int[] nume = new int[26];
for(int i = 0 ; i < s.length() ; i++){
num[s.charAt(i)-97]++;
}
for(int i = 0 ; i < e.length() ; i++){
nume[e.charAt(i)-97]++;
}
int count = 0;
for(int i = 0 ; i < num.length ; i++){
if(num[i] >= nume[i]){
count += nume[i];
}else if(num[i] == 0){
count = Integer.MAX_VALUE;
break;
}else{
count += num[i];
}
}
if(count == Integer.MAX_VALUE){
System.out.println(-1);
}else{
System.out.println(count);
}
}
}


C問題はずっとプレテストが通らず、諦めました。
内容は、
2つの整数a,bが与えられるときm
以下の条件を満たす2次元座標中の格子点3つがあれば答えよ。

3点は直角三角形を成し、直角を挟む2辺の長さはa,bである。
各辺はX軸およびY軸に平行でない。

夜は久しぶりに親と話す時間を設けました。
f0019846_16375721.jpg


その後は少しゲーセン。
REVOLUTIONARY ADDICT 95.2% フルコン
f0019846_16385984.jpg


弐寺DP八段67%でした。
f0019846_16393088.jpg


その後は家寺。

moon_child(A)ノマゲ
f0019846_1640023.jpg

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

6年間お疲れ様でした Codeforces #237 div2

今日は晴れの舞台。
ここまで死ぬ気でやってきたなーという感じあります。
やりきれなかったところもありますが、新たな旅立ち・・・ですね。

それが終わった後は、秋葉原のゲーセンで若干弐寺する。

渚の小悪魔押し。
f0019846_22205028.jpg


MAD ATTACK DPA 易
f0019846_22211619.jpg


その後は皆で打ち上げ。お疲れ様でしたーということで。
f0019846_22213893.jpg


f0019846_2221469.jpg


f0019846_22215612.jpg


f0019846_2222615.jpg


f0019846_22271211.jpg


f0019846_22272365.jpg


f0019846_22273472.jpg


その後は幸楽苑でラーメンを食べに行く。
つけ麺で更にお腹を満たしていくスタイル。
f0019846_2228599.jpg


帰宅後はCodeforces #237 div2に参加。

A問題は、n*nの二次元平面上にxの文字ができているかどうか判定する問題。
ノイズが1個でもあればダメなので、2種類の文字だけ使われているか、
×上はきちんとあるか判定する。
i == j || i == st-j-1 でいける。


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

import javax.print.attribute.standard.Sides;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int st = Integer.parseInt(br.readLine());
String[] s = new String[st];
for(int i = 0 ; i < st ; i++){
s[i] = br.readLine();
}
boolean isok = true;
char c = s[0].charAt(0);
char c2 = s[0].charAt(1);
if(c == c2){
isok = false;
}else{
for(int i = 0 ; i < s.length ; i++){
for(int j = 0 ; j < s[i].length() ; j++){
if(i == j || i == st-j-1){
if(c != s[i].charAt(j)){
isok = false;
break;
}
}else{
if(c2 != s[i].charAt(j)){
isok = false;
break;
}
}
}
if(!isok)break;
}
}
if(!isok){
System.out.println("NO");
}else{
System.out.println("YES");
}
}

}


B問題は、
Valeraは左下座標(0,0)から始まる大きさa*aの正方形の会場を反時計回りにn*d+0.5の距離を走る
マラソンに参加し、d毎に水分補給をするために飲み物を用意しておく必要がある。
その場所の座標を出力せよ。
・反時計回りなので0,0 -> a,0 -> a,a -> 0,a で0,0戻って1周になることに注意する。


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

import javax.print.attribute.standard.Sides;

public class Main2 {
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] st = br.readLine().split(" ");
double a = Double.parseDouble(st[0]);
double d = Double.parseDouble(st[1]);
int n = Integer.parseInt(br.readLine());

int count = 0;
int ctbk = 0;
double kyori = d;
while(count != n){
if(kyori > a){
int plus = (int)(kyori/a);
ctbk += plus;
ctbk %= 4;
kyori -= (int)(kyori/a)*a;
}else{
if(ctbk == 0){
System.out.println(kyori+" "+0);
}else if(ctbk == 1){
System.out.println(a+" "+kyori);
}else if(ctbk == 2){
System.out.println((a-kyori)+" "+a);
}else{
System.out.println(0+" "+(a-kyori));
}
kyori += d;
count++;
}
}
}

}


シミュレートして出力する。
ドリンクを置く位置は、全シミュレートで良いが、割り切れるところまでは先に計算して、
どこの周回にいるかを判定する必要がある。

C問題はグラフの復元系問題。最近流行っている…?
考える気力もなかったので解きませんでした。

明日から完全にフリーです。さあどう過ごそうか。

  by ddrer-yossi | 2014-03-19 23:15 | codeforces | Comments(0)

SEM SKIN - DESIGN by SEM EXE