ナランハジャグリングまつり(2日目) Codeforces #118

今日も並んはジャグリングまつりに参加。
朝はクラブのワークショップに。
うん、やっぱり3つになるとほとんどできない。

ボールの輪に入っていると、
7ボールのエンデュランスどうですかと声かけられたので、
久しぶりに参戦。できないのわかっていたけど。
結局まともに続かず終了。
ジャグリングセールに関しても、お金はほとんど使わないと決めていたのと、
勝利できなかったのとで何も買わず。

10秒コンテストですが、うーん、まあ微妙なジャッジでした。
致し方ないのかもしれませんが・・・ね。
私だけでなく、知り合いも納得してなかったです。

夕方までにかけてはディアボロなども触ってみました。
後はシャッフルに関しての極め方について、詳しい方に教えてもらいました。

夜は友人と池袋のゲーセンへ。
さすがGW中、どこも混んでいて、プレーできる状況にありませんでした。
諦めてラーメン二郎へ。
これも、早めに行ったからよかったものの、後10分遅ければ高校生の団体のあとになり、
混み混みになっていました。

さっそく食べる。が、思ったより箸が進まず、結局スープは飲まずに行きました。
歳かなあ・・・。

ナランハジャグリングまつり(2日目) Codeforces #118_f0019846_3273778.jpg


その後はmayoさんが代表のぁ~んの6周年記念記念イベントのニコ生を見ました。
テルさんとPocariさんの対談って、やっぱりいろいろな意味ですごい。
特にPocariさんがラスベガス中継とかありえん!と。
TypeRacerについて結構テルさんが熱く語ってました。
あれって今そんなに流行ってるのかーと最認識させられました。
後、キーボード紹介で金持ちーとか言われましたが、まったくの誤解です。
確かにリアフォ3台、HHKB Pro無刻印はありますが・・・。

タイパー(過去形)だもの、キーボードに7万かけてなにがわるいっ!

そして夜はcodeforcesへ。

A問題 文字列が2つ与えられていて、
1つめから1回だけ入れ替えを行なって2つ目にできるかどうかという話。入れ替え回数が無制限でも、Pretestは通ってしまったので、それでhackされた。
直したソースを。

import java.util.Scanner;

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
String s = input.nextLine();
String t = input.nextLine();
System.out.println(maximum(s,t));
}

public static String maximum(String s,String t){
int[] ss = new int[26];
int[] ts = new int[26];
for(int i = 0 ; i < s.length() ; i++){
ss[s.charAt(i)-97]++;
}
for(int i = 0 ; i < t.length() ; i++){
ts[t.charAt(i)-97]++;
}
boolean isng = false;
for(int i = 0 ; i < ss.length ; i++){
if(ss[i] == ts[i]){
continue;
}else{
isng = true;
break;
}
}
int differ = 0;
if(s.length() != t.length()){
isng = true;
}else{
for(int i = 0 ; i < s.length(); i++){
if(s.charAt(i) != t.charAt(i))differ++;
}
}
if(isng || differ > 2){
return "NO";
}else{
return "YES";
}
}
}


B問題。前半戦がt1、後半戦がt2与えられていて、
前半戦と後半戦の間に、値がk%になってしまう。
最大値となるように戦略を考え、値の大きい順に、人数番号も含めて提出せよ。


import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int t1 = input.nextInt();
int t2 = input.nextInt();
int k = input.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for(int i = 0 ; i < n ; i++){
a[i] = input.nextInt();
b[i] = input.nextInt();
}
maximum(n,t1,t2,k,a,b);
}

public static void maximum(int n,int t1,int t2,int k,int[] a,int[] b){
double[] swapped = new double[n];
for(int i = 0 ; i < n ; i++){
swapped[i] = Math.max((double)b[i]*t1*((double)(100-k)/100)+a[i]*t2,(double)a[i]*t1*((double)(100-k)/100)+b[i]*t2);
}
while(true){
double max = -1;
int index = -1;
boolean flag = true;
for(int i = 0 ; i < swapped.length ; i++){
if(max < swapped[i]){
index = i;
flag = false;
max = swapped[i];
}
}
if(flag)break;
BigDecimal bd = new BigDecimal(max);
BigDecimal bd4 = bd.setScale(2, BigDecimal.ROUND_HALF_UP);
System.out.println((index+1)+" "+bd4);
swapped[index] = -1;
}
}
}


戦略は両方共計算してみて大きい方を取る。それだけ。後は誤差に気をつける。
インデックスを記憶してソート。

C問題
上三角形の中に下三角形を、下三角形の中に上三角形をn回入れるという動作を行う。上三角形となるような数を求めよ。
これは法則を探して漸化式を使って式を簡略化できる。
譬えばa[n]をn回目における上三角形の数、b[n]をn回目における下三角形の数とすると

a[n+1] = 3*a[n]+b[n]
b[n+1] = a[n]+3*b[n]
両方を足すと a[n+1]+b[n+1] = 4*(a[n]+b[n])となる。
a[n]+b[n] = 4^n
両方を引くと a[n+1]-b[n+1] = 2*(a[n]-b[n])となる。
a[n]-b[n] = 2^n
これらを足すと 2*a[n] = 4^n+2^n = 2^n(2^n+1)
a[n] = 2^n(2^n+1)/2 が答えとなる。

つまり、n=1 で答えが2*3/2 = 3 、 n=2 で答えが4*(4+1)/2 = 10 となり、辻褄が合う。

後ほどmod(1000000007)をしたら通った。死にたい。

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

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
String s = input.nextLine();
maximum(s);
}

public static void maximum(String s){
BigInteger a = new BigInteger(s);
BigInteger b = new BigInteger("2");
BigInteger mode = new BigInteger("1000000007");
BigInteger d = new BigInteger("1");
//BigInteger c = b.modPow(a,mode);
BigInteger cs = b.modPow(a,mode);
//System.out.println((c.multiply(c.add(d))).divide(b));
if(cs.multiply(cs.add(d)).compareTo(d) <= 0){
System.out.println(cs.multiply(cs.add(d)).mod(mode));
}else{
System.out.println(cs.multiply(cs.add(d)).divide(b).mod(mode));
}

//1000000007
}

}


結局Bしか合っていないのでレートはガタ落ちです。泣きそう。

  by ddrer-yossi | 2012-05-04 23:23 | codeforces

<< TODやったりプログラミングしたり ナランハジャグリングまつり(1... >>

SEM SKIN - DESIGN by SEM EXE