最初の節目。一段落した。 Codeforces #226(div2)

今日は仕事。お昼は三種のチーズ牛丼。
最初の節目。一段落した。 Codeforces #226(div2)_f0019846_20191782.jpg


夜は急いで2時間かけて某所へ。
急遽、書き上がった原稿を提出する。ようやく。

夜ですがCodeforces #226もあるので、足早に2クレのみ。

デッドボヲルdeホームラン 93.5% フルコン
最初の節目。一段落した。 Codeforces #226(div2)_f0019846_2021456.jpg


A問題は、くまは蜂蜜を貯めておきたい。
その日の
友人から1日だけnキロのラズベリーのレートで1kgの蜂蜜を借りて、
それをどこかの日のレートでラズベリーに変換し、次の日で1kg分のレートで返す。
その時のラズベリーのキロ数を最大値を求めよという問題。
得たラズベリーから、借りた費用と次の日に返したラズベリー分を引く。

問題文はわかりづらいが、例がわかりやすいのでこちらから解くとよい。
全部調べるだけ。O(n)でできる。


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));
String[] s = br.readLine().split(" ");
int N = Integer.parseInt(s[0]);
int c = Integer.parseInt(s[1]);
int[] array = new int[N];
String[] st = br.readLine().split(" ");
for(int i = 0 ; i < N ;i++){
array[i] = Integer.parseInt(st[i]);
}
int max = 0;
for(int i = 0 ; i < N-1 ; i++){
max = Math.max(max,array[i]-array[i+1]-c);
}
System.out.println(max);
}
}


B問題は、"bear"が含まれる部分文字列が何通りできるか数えるだけ。
全通り試してしまうと怪しいので、どこかで含まれている時点で、残りも含まれているという考えで良い。
つまり、始点だけ動かして、最初にbearが来る位置を特定して、加算していくとよい。

aaabearcdeとかであれば、
まず(始点,終点)は(0,3)となる。
文字数は10なので、10-(3+3+0)の4通りがまず出る。
これを始点をずらして繰り返していく。


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));
String s = br.readLine();
int count = 0;
for(int i = 0 ; i < s.length() ; i++){
int ct = s.substring(i,s.length()).indexOf("bear");
if(ct != -1){
count += s.length()-(ct+3+i);
}
}
System.out.println(count);
}
}


C問題は、エラトステネスの篩を使う。本番中には解けませんでしたが。

N個の自然数X[i]が与えられ、M個のクエリが与えられる。
各クエリはL[i],R[i]の2整数で表現される。
各クエリの解は、L[i]~R[i]の区間に含まれる各素数について、
X[i]を割り切る数の総和のとき、
それぞれのクエリについて答えよ。

意外に面倒。

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));
int[] primer = new int[10000001];
boolean[] isnotprime = new boolean[10000001];
int[] intimidate = new int[10000001];
isnotprime[1] = true;
primer[1] = 1;
for(int i = 2 ; i <= 10000000 ; i++){
if(!isnotprime[i]){
int num = i;
primer[i] = i;
while(num + i <= 10000000){
num += i;
if(!isnotprime[num]){
primer[num] = i;
}
isnotprime[num] = true;
}
}
}
int n = Integer.parseInt(br.readLine());
int[] a = new int[n];
String[] s = br.readLine().split(" ");
for(int i = 0 ; i < a.length ; i++){
a[i] = Integer.parseInt(s[i]);
int num = a[i];
int same_number = -1;
while(num != 1){
int primes = primer[num];
//System.out.println(primes+","+num);
if(same_number != primes){
same_number = primes;
intimidate[primes]++;
}
num /= primes;
}
}

int i_sum = 0;
int[] sum = new int[10000001];
for(int i = 0 ; i < sum.length ; i++){
i_sum += intimidate[i];
sum[i] = i_sum;
}


int m = Integer.parseInt(br.readLine());
int[] st = new int[m];
int[] en = new int[m];
for(int i = 0 ; i < st.length ; i++){
int count = 0;
s = br.readLine().split(" ");
st[i] = Integer.parseInt(s[0]);
en[i] = Integer.parseInt(s[1]);
if(st[i] > 10000000){

}else{
if(en[i] > 10000000){
en[i] = 10000000;
}
count += sum[en[i]]-sum[st[i]-1];
}
System.out.println(count);
}
}
}

  by ddrer-yossi | 2014-01-24 23:59 | codeforces

<< 反動でのんびり 地獄の追い込み >>

SEM SKIN - DESIGN by SEM EXE