TopCoder SRM606とCodeforces #227

今日は朝11時のTopCoder SRM606に参加。

easyは、
相手は1~10^9のいずれかの数字を頭に浮かべており、その数を当てるゲームを行う。
こちらが数字を伝えると、頭に浮かべている数字との差の絶対値を教えてくれる。

伝えた数字guesses[i]と教えてくれた数字answer[i]のペアがいくつか与えられるので、
頭に浮かべた数字を当てる問題。

答えがひとつに絞れない時は-1を、嘘を付いている場合は-2を返せ。
愚直に判定していくだけ。リストでやるといい。
候補がなくなったら嘘つき、候補が複数残ったらまだ答えが残っている、
1つしかない場合は答えを返すと言った感じ。


import java.util.ArrayList;

public class EllysNumberGuessing {

public int getNumber(int[] guesses, int[] answers) {
ArrayList list = new ArrayList();
int st = guesses[0]+answers[0];
int en = guesses[0]-answers[0];
if(st <= 1000000000){
list.add(st);
}
if(en >= 1){
list.add(en);
}

for(int i = 1 ; i < guesses.length ; i++){
int st2 = guesses[i]+answers[i];
int en2 = guesses[i]-answers[i];
boolean[] lister = new boolean[list.size()];
for(int j = 0 ; j < list.size(); j++){
if(list.get(j) == st2)lister[j] = true;
if(list.get(j) == en2)lister[j] = true;
}
for(int j = list.size()-1 ; j >= 0 ; j--){
if(!lister[j])list.remove(j);
}
}
if(list.size() == 2){
return -1;
}else if(list.size() == 0){
return -2;
}else{
return list.get(0);
}
}

}


mediumは、N個の大学の生徒が集まっていて、
生徒の名前は2の累乗である整数Mに対し、0~(M-1)のM通りある。

各大学にはcount[i]人の生徒がおり、最初の生徒の名前はfirst[i]である。
各大学で、名前がxの生徒の次の生徒の名前は、(x*mul[i]+add[i]) % M である。

全大学合計で(count[i]の総和)人の生徒で、2人組を作りたい。
所属する大学は同じでも異なっていても良い。
この時、同じ名前の生徒を組にすることはできない。
最大で2人組を何組作れるか。

一番人数から被っちゃう奴を引いただけのペアか、人数/2のペアの最大のどっちかは取れる。
じゃあ被っちゃう時をどうやってカウントするかな…って考えて、かぶりまくる時は周期で求めて、
あんまりかぶらない時はArrayListで実際に求めるとか…

通らなかったんであれですが。
1219->1277

その後はプログラムを動かしつつ、書きつつということで。
夜は親が応援なのか、石狩鮨とやらを買ってきていました。あとはいかめし。
f0019846_1501814.jpg


f0019846_1503311.jpg


23時ぐらいからようやくゲーセンへ。
Vermilion 89.9% miss1
f0019846_1512371.jpg


90.6% AAA
f0019846_1514022.jpg


その後はDiva新曲をプレー。
システマティックラブ EXTREME 104.50% fine12 PERFECT
f0019846_1521762.jpg


そしてLEADING CYBER(A)は7回ほどやってようやくフルコン。
f0019846_1524192.jpg


帰宅後はCodeforces #227に参加。

A問題は、1行目と2行目で時間の引き算をする問題。
2行目の方が遅い時間の場合は一日戻す。
意外に実装が面倒。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
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));
String[] en = br.readLine().split(":");
String[] st = br.readLine().split(":");
int h = Integer.parseInt(en[0])-Integer.parseInt(st[0]);
if(h < 0)h += 24;
int m = Integer.parseInt(en[1])-Integer.parseInt(st[1]);
if(m < 0){
m += 60;
h--;
if(h == -1)h+=24;
}
String s = "";
int zeronum = 2-String.valueOf(h).length();
for(int i = 0 ; i < zeronum ; i++){
s += 0;
}
s += String.valueOf(h)+":";
zeronum = 2-String.valueOf(m).length();
for(int i = 0 ; i < zeronum ; i++){
s += 0;
}
s += String.valueOf(m);
System.out.println(s);
}
}


B問題は、
・コンテストの問題を1からm問目まで用意して、それぞれの問題の難易度はbi
・開催のためには難易度がそれぞれaiのn問が必要
・難易度がa>=bであれば使いまわせるがそうでなければ新たに問題を用意する必要がある。
・最低で何問用意しなければいけないかを出力する。

ソートは不要なので、単純に左から比較していきましょう。


import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
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));
String[] st = br.readLine().split(" ");
int n = Integer.parseInt(st[0]);
int m = Integer.parseInt(st[1]);
st = br.readLine().split(" ");
int[] a = new int[n];
int[] b = new int[m];
for(int i = 0 ; i < n ; i++){
a[i] = Integer.parseInt(st[i]);
}
st = br.readLine().split(" ");
for(int i = 0 ; i < m ; i++){
b[i] = Integer.parseInt(st[i]);
}
int index = 0;
int count = 0;
for(int i = 0 ; i < m ; i++){
if(index == n)break;
if(b[i] >= a[index]){
index++;
}
}
System.out.println(n-index);
}
}


C問題は、
数列Bに対して以下の処理を繰り返すことができるとする。
B[i] >= B[j] かつ i < jとなるインデックスの対を選択し、
B[i]とB[j]をBから削除し、B[i]とB[j]を文字列的に連結して、Bの末尾に加える。
繰り返した結果、Bが単一要素の数列になって、最後の単一要素の数値が与えられたとき、
その数値を上の処理で生成できるようなBの初期状態のうち最大要素数を答えよ。
ただし、Bの各要素は正でなければならず、0が先頭であってはならない。
比較でTLEしてしまった。つらい。

その後は朝5時くらいまで書く作業をしていました。

  by ddrer-yossi | 2014-01-30 23:28 | TopCoder | Comments(0)

<< すべてを悟った。スペースレクイ... マシンをフル稼働 >>

SEM SKIN - DESIGN by SEM EXE