<   2012年 01月 ( 31 )   > この月の画像一覧

 

Top Coder SRM531 &決戦前夜

今日は決戦前夜ですが、TopCoderに参加することにしました。

夜は本当は怖い家庭の医学でTCHについてやっていました。
普段歯は噛みあわせていない状態だけど、
くっついている状態が長いとよろしくないんだとか。
デスクワークとかやっていると自然にくっつく時間がながくなる。
無意識のうちにやってしまうので、やらないように意識的に心がけることが大事なんだと。

TopCoderですが、まさかの短期決戦です。
数値の要素の配列が与えられていて、昇順に並べて、1個手前の数を並び替えるだけ。
要素が1個であったり、同じものしかない場合は{}を返す。
しかしこれはnullではない。空配列である。

import java.util.Arrays;

public class UnsortedSequence {

public int[] getUnsorted(int[] s) {
int[] sr = new int[s.length];
for(int i = 0 ; i < s.length ; i++){
sr[i] = s[i];
}
Arrays.sort(sr);
boolean iss = false;

System.out.println();
int tmpsi = sr[s.length-1];
for(int i = s.length-1 ; i >= 0 ; i--){
if(tmpsi != sr[i]){
int swap = sr[i];
sr[i] = tmpsi;
sr[i+1] = swap;
iss = true;
break;
}
}
if(iss){
return sr;
}
int[] nuller = new int[0];
return nuller;
}

}

2問目のmediumは相当難しい問題。
曲のリストが与えられていて、ある制約条件があって、何通りあるか判別する問題。

  by ddrer-yossi | 2012-01-31 23:20 | TopCoder | Comments(0)

Facebook Hacker Cup Round1落ち

やる気を出すために朝からカレーうどん。2玉入っているので大盛バージョンです。

f0019846_22402540.jpg


昨日1問しか解いていませんでしたが、その1問は通りませんでした。ざんねん!
ということでR1落ちです。お疲れ様でした。
そもそも3問全部あっていないと予選は通らないので、無理でしたね。
あとはずっと勉強です。

  by ddrer-yossi | 2012-01-30 22:29 | 日常生活 | Comments(0)

Facebook Hacker Cup Round1

今日は午前3時からFacebook Hacker Cup の Round1がはじまりました。

1問目は組み合わせを求める問題。これぐらいしか手が出せそうなのがなかったのと、
ほとんど時間も無いのでこれだけ提出して終了。
2問目はマージソートの逆。面倒そうなのでマージソートの勉強だけして終わり。
3問目はDPを使って解くらしい。愚直な実装だと3^nのオーダとなり、死滅していく。

ということで結果的にこれに時間を結構割いてしまったのが悔やまれました。
通ればいいとは思いますが、見た目上、
3完しないと通過しないラインのようなので無理だと思います。

夜9時でこの気温なのでかなり寒かったです。
f0019846_22385522.jpg


f0019846_2239782.jpg

ついでに山積みになったフィギュアも。

  by ddrer-yossi | 2012-01-29 22:35 | 日常生活 | Comments(0)

パーティクル崩し

f0019846_1347427.png


f0019846_1358399.png


こんなのが流行っていました。きれいですねー。
パーティクル崩し EASY
パーティクル崩し 通常
ブロック崩しの派生系です。最初さえちゃんとやれば後は操作不要です。

後はひたすら勉強に打ち込んでいました。片方向遅延とかネットワーク関係。

  by ddrer-yossi | 2012-01-28 23:47 | 日常生活 | Comments(0)

日々精進

今日は確率に関する復習をしていました。
r*(nCr) =n*(n-1Cr-1) とかですね。

後はε-N論法など。
どんな誤差εにおいても、適切なあるNを選べば |aN - α| < ε となるようなNが存在する。

f0019846_16235969.jpg

パンにプリンが入っている斬新なおやつをいただきました。

  by ddrer-yossi | 2012-01-27 23:08 | 日常生活 | Comments(0)

ハザード、行列の勉強

今日はパイプライン処理におけるハザードについての勉強と、
待ち行列(リトルの公式など)をやりました。

構造ハザード 制御ハザード データハザード の対処法などなど。

L = λWとかρ/1-ρとか。
導くのに三項間漸化式の復習も兼ねました。

f0019846_16383988.png


後はこんなもの更新してました。

  by ddrer-yossi | 2012-01-26 23:24 | 日常生活 | Comments(0)

Facebook Hacker Cup Qualification Round 通過

Facebook Hacker CupのQualification Roundの結果がようやく出ていました。
3問中2問解いて、2完です。
提出時は700位でしたが、間違った答えや適当な答えがいくつもあったせいか、400位台でした。

終わったので内容について簡単に。
・Billboards
正方形フォントの文字を長方形のボードに貼り付ける。フォントの最大サイズを求める問題。でかい値から調べていけばok

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

public class Test {

public void dom() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/billboards.txt"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int cases = input.nextInt();
int[] W = new int[cases];
int[] H = new int[cases];
String[] str = new String[cases];

for(int i = 0 ; i < cases ; i++){
W[i] = input.nextInt();
H[i] = input.nextInt();
str[i] = input.nextLine();
}
for(int i = 1 ; i <= cases ; i++){
pw.println("Case #"+i+": "+font(W[i-1],H[i-1],str[i-1]));
}

input.close();
pw.flush();
pw.close();
}

public static int font(int W,int H,String str){
str = str.substring(1,str.length());
String[] strsp = str.split(" ");
int[] spacewith = new int[strsp.length];
int sqr = 0;
for(int i = 0 ; i < strsp.length ; i++){
sqr = (strsp[i].length());
spacewith[i] = sqr;
}

int max = Math.max(W,H);
for(int i = max ; i > 0 ; i--){
int rW = W;
int rH = H;
boolean ok = true;
for(int j = 0 ; j < strsp.length ; j++){
if(rH < i){
ok = false;
break;
}else if(rW >= i*spacewith[j]){
rW -= i*(spacewith[j]+1);
}else{
rW = W;
rH -= i;
j--;
}
}
if(ok == true)return i;

}
return 0;
}

public static void main(String[] args) throws Exception{
(new Test()).dom();
}


}


・Auction
ある計算式にしたがって物の重さと値段があり、バーゲン物とゴミの数を求める。難問。

・Alphabet Soup
HACKERCUPに使われているアルファベットが文字列中に何回でているかを調べる問題。Cが2回使われていることに気をつけるだけで、後はカウントしてソートして最初の値を出すだけ。一番簡単。

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

public class Test {

public void dom() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/alphabet_soup.txt"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int cases = input.nextInt();
input.nextLine();
String[] str = new String[cases];

for(int i = 0 ; i < cases ; i++){
str[i] = input.nextLine();
}
for(int i = 1 ; i <= cases ; i++){
pw.println("Case #"+i+": "+Hacker(str[i-1]));
}

input.close();
pw.flush();
pw.close();
}

public static int Hacker(String str){
int[] letters = new int[8];
for(int i = 0 ; i < str.length() ; i++){
if(str.charAt(i) == 'A'){
letters[0]++;
}else if(str.charAt(i) == 'C'){
letters[1]++;
}else if(str.charAt(i) == 'E'){
letters[2]++;
}else if(str.charAt(i) == 'H'){
letters[3]++;
}else if(str.charAt(i) == 'K'){
letters[4]++;
}else if(str.charAt(i) == 'P'){
letters[5]++;
}else if(str.charAt(i) == 'R'){
letters[6]++;
}else if(str.charAt(i) == 'U'){
letters[7]++;
}
}
letters[1] /= 2;
Arrays.sort(letters);
return letters[0];

}


public static void main(String[] args) throws Exception{
(new Test()).dom();
}


}


夕方は、スコアの更新を行うために外出しました。
帰宅後は引き続き勉強です。夜食もいきました。

f0019846_16345785.jpg

  by ddrer-yossi | 2012-01-25 23:28 | 日常生活 | Comments(0)

雪でしたが外に出ました

今日は朝出てきたところ、若干の雪が積もっていました。
f0019846_16462522.jpg


しかし、告げなければいけない用事ができたので、某所へ向かうことに。
昼過ぎになれば雪の影響はほとんどありませんでした。
後は軽く試験も受けていました。これはとても適当でした。

夜はゲーセンへ。diva10クレ(コンテスト含む)をやりました。
f0019846_16471288.jpg


f0019846_1648191.jpg


f0019846_16482879.jpg


f0019846_16483549.jpg


f0019846_16484328.jpg


sound voltexというKONAMIの新作が置いてありましたが、
200円設定なのでやりませんでした。100円になることが見えているので・・・。

  by ddrer-yossi | 2012-01-24 23:44 | 日常生活 | Comments(0)

アルゴリズムの勉強

今日はunion-findを中心に、最小全域木(プリム法)などの勉強をしました。
夜は雪が降り始めていました。

後は、Face bookがやっているプログラミングコンテストに参加してみたのですが、
TLEで通らず時間切れに。条件がなかなかシビアです。

  by ddrer-yossi | 2012-01-23 23:51 | 日常生活 | Comments(0)

Codeforces #104とかリフレクプラスとか

今日は16時にcodeforcesがありましたので参加しました。

A問題
4と7だけ含むチケットをラッキーとする。
前半の半分の数値と後半の半分の数値の合計が一致する条件を付け加えて、
そのチケットがラッキーかどうかを判別しろという問題。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
input.nextLine();
String s = input.nextLine();
System.out.println(lucky(n,s));
}

public static String lucky(int n,String s){
for(int i = 0 ; i < s.length(); i++){
if(!(s.charAt(i) == '4' || s.charAt(i) == '7'))return "NO";
}
String front = s.substring(0,n/2+1);
String last = s.substring(n/2,s.length());
int fsum = 0;
int lsum = 0;
for(int i = 0 ; i < n/2 ; i++){
fsum += Character.digit(front.charAt(i),10);
lsum += Character.digit(last.charAt(i),10);
}
if(fsum == lsum)return "YES";
return "NO";
}
}

B問題
ある数aとラッキーナンバーbが与えられている。
マスクという法則があり、3403790などの数字から4と7だけとってきたものである。(例は47)
a以上の数値でマスクしてbというラッキーナンバーになる最小の値を求めるプログラムを作る。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int b = input.nextInt();
System.out.println(lucky(a,b));
}

public static int lucky(int a,int b){
a+=1;
while(true){
StringBuilder sb = new StringBuilder();
String s = String.valueOf(a);
for(int i = 0 ; i < s.length() ; i++){
if(s.charAt(i) =='4' || s.charAt(i) == '7'){
sb.append(s.charAt(i));
}
}
if(sb.length() != 0 && Integer.parseInt(sb.toString()) == b)return a;
a++;
}
}
}

C問題
ラッキーナンバーaとbが与えられている。
aに操作を加えbにする。
aにできる操作は、4を7にしたり7を4にしたり、aのある桁とある桁の数をチェンジするといったことである。
これらの操作を加えてbにするときの最少の回数を求める。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
String a = input.nextLine();
String b = input.nextLine();
System.out.println(lucky(a,b));
}

public static int lucky(String a,String b){
int a4sum = 0;
int a7sum = 0;
int b4sum = 0;
int b7sum = 0;
int f47 = 0;
int f74 = 0;
for(int i = 0 ; i < a.length() ; i++){
if(a.charAt(i) == '4'){
a4sum++;
}else{
a7sum++;
}
if(b.charAt(i) == '4'){
b4sum++;
}else{
b7sum++;
}
if(a.charAt(i) == '4' && b.charAt(i) == '7'){
f47++;
}
if(a.charAt(i) == '7' && b.charAt(i) == '4'){
f74++;
}
}
int gosa = Math.abs(a4sum-b4sum);
return Math.min(f47, f74)+gosa;
}
}

D問題(時間内は失敗し、その後提出)

4の数、7の数、47の数、74の数が与えられている。
これらを満たす最少のラッキーナンバーを求めよ。存在しない場合は-1を返せ。

条件分岐の問題です。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int b = input.nextInt();
int c = input.nextInt();
int d = input.nextInt();
System.out.println(lucky(a,b,c,d));
}

public static String lucky(int a,int b,int c,int d){
if(c == d){
if(Math.min(a, b) >= (c+1)){//ok
StringBuilder s = new StringBuilder();
int r47 = c-1;
int pkt4 = a-2-r47;
int pkt7 = b-2-r47+1;
for(int i = 0 ; i < pkt4 ; i++){
s.append(4);
}
for(int i = 0 ; i < r47 ; i++){
s.append(47);
}
s.append(47);
for(int i = 0 ; i < pkt7 ; i++){
s.append(7);
}
s.append(4);
return s.toString();

}else if(Math.min(a, b) == c){
if(a == b)return "-1";
StringBuilder s = new StringBuilder();
if(a == c){
s.append(7);
for(int i = 0 ; i < c ; i++){
s.append(47);
}
int res7 = b-c-1;
for(int i = 0 ; i < res7 ; i++){
s.append(7);
}
return s.toString();
}else if(b == c){
int res4 = a-c-1;
for(int i = 0 ; i < res4 ; i++){
s.append(4);
}
for(int i = 0 ; i < c ; i++){
s.append(47);
}
s.append(4);
return s.toString();
}
return "-1";
}else{
return "-1";
}
}

if((a+b) <= (c+d) || Math.abs(c-d) >= 2 || Math.min(a, b) < Math.max(c, d)){
return "-1";
}else{
if(c > d){
int pkt4 = a-c;
int pkt7 = b-c;
StringBuilder s = new StringBuilder();
for(int i = 0 ; i < pkt4 ; i++){
s.append(4);
}
for(int i = 0 ; i < c ; i++){
s.append(47);
}
for(int i = 0 ; i < pkt7 ; i++){
s.append(7);
}
return s.toString();
}else{
int pkt4 = a-d;
int pkt7 = b-d;
StringBuilder s = new StringBuilder();
for(int i = 0 ; i < d ; i++){
if(i != d-1){
s.append(74);
if(i == 0){
for(int j = 0 ; j < pkt4 ; j++){
s.append(4);
}
}
}else{
s.append(7);
for(int j = 0 ; j < pkt7 ; j++){
s.append(7);
}
s.append(4);
}
}
return s.toString();
}
}
}
}

3問解けたので、レーティングは上昇しました。

後はリフレクを少々。
f0019846_1771643.png

  by ddrer-yossi | 2012-01-22 16:57 | codeforces | Comments(0)

SEM SKIN - DESIGN by SEM EXE