はじめに
A～Cは自力AC、Dは解説ACしたものとなります。
昔のコードなので、そのままのも載せますが書き直した方が良さそうな時は書き換えた物も載せます。
では、見ていきましょう。
A - キャンディーとN人の子供イージー
問題文はこちら
単純にfor文でシミュレーションしました。
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//値の受け取り
int N = sc.nextInt();
//答え用変数
int ans = 0;
//順に足していく
for(int i=1;i<=N;i++){
ans += i;
}
//答えの出力
System.out.println(ans);
}
}
公式$\frac{1}{2}N(N+1)$を用いても良いでしょう。
B - バイナリハックイージー
問題文はこちら
こちらもシミュレーションしました。
空のときのBに注意しましょう。
import java.io.*;
//一文字区切りをするメソッドがあるクラス
class subMain{
public static String[] parStr(String someStr){
String[] str = someStr.split("");
return str;
}
}
class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//sの受け取り
String[] s = subMain.parStr(br.readLine());
//今の状態を記録する変数
String ans = "";
//順にシミュレーション
for(int i=0;i<s.length;i++){
if(s[i].equals("B")&&!(ans.equals("")))
ans = ans.substring(0,ans.length()-1);
else if(s[i].equals("0"))
ans += "0";
else if(s[i].equals("1"))
ans += "1";
}
//答えの出力
System.out.println(ans);
}
}
個人的にStringのsubstringはなんとなく消した感が無いのでStringBuilderを使ってみます。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//状態を管理する変数
StringBuilder answer = new StringBuilder();
//一文字ずつ読みとるための一時的な変数
int temp;
//改行まで読み込み続ける
while((temp=br.read())!='\n'){
//それぞれシミュレーション
switch(temp){
case '0':
answer.append('0');
break;
case '1':
answer.append('1');
break;
default:
if(answer.length()>0)
answer.deleteCharAt(answer.length()-1);
}
}
//答えの出力
System.out.println(answer.toString());
}
}
前者でもそこまで時間ギリギリって訳ではないので好みの問題な気がします。
C - いっしょ
問題文はこちら
求める値をXとします。$\sum_{k=1}^{N}(X-a_i)^2$をよーく見てみると分散を求める式に似てるなぁと思ったので、Xは平均値だと思って解きました。
ちょっとした証明みたいなもの
なぜ平均値で良いのでしょうか。実際に式を展開してみましょう。
$ \sum_{k=1}^{N}(X-a_i)^2
= (X-a_1)^2+(X-a_2)^2+･･･+(X-a_N)^2 $
$= NX^2-2(a_1+a_2+･･･+a_N)X+a_1^2+a_2^2+･･･+a_N^2 $
そして平方完成を行なうと、
$ NX^2-2(a_1+a_2+･･･+a_N)X+a_1^2+a_2^2+･･･+a_N^2 $
$ = N(X-\frac{a_1+a_2+･･･+a_N}{N})^2-\frac{(a_1+a_2+･･･+a_N)^2}{N}+a_1^2+a_2^2+･･･+a_N^2 $
上記の式より、この問題は以下の$x$を最小化する問題に帰着できます。
$x = |X-\frac{a_1+a_2+･･･+a_N}{N}| $
そして、$ \frac{a_1+a_2+･･･+a_N}{N} $は全要素の平均値ですので、Xが全要素の平均値の時に$x$は最小値0を取ることがわかります。ただし、全要素の平均が整数ではない場合もあるので、小数点第1位で四捨五入をした値が最終的な答えとなります。
import java.io.*;
//空白区切りで値を受け取るためのクラス
class subMain{
public static int[] parIntWithS(String someInt){
String[] str = someInt.split(" ");
int[] Intel = new int[str.length];
for(int i=0;i<str.length;i++){
Intel[i] = Integer.parseInt(str[i]);
}
return Intel;
}
}
class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//N、aの受け取り
int N = Integer.parseInt(br.readLine());
int[] a = subMain.parIntWithS(br.readLine());
//全要素の和を記録する変数
int sum = 0;
//全部足す
for(int i=0;i<a.length;i++){
sum += a[i];
}
//平均値を求める(小数点以下は四捨五入で丸める)
long average = Math.round((double)sum/a.length);
//平均値との差を記録する変数
int ans = 0;
//それぞれ計算
for(int i=0;i<a.length;i++){
ans += Math.pow(a[i]-average,2);
}
//答えの出力
System.out.println(ans);
}
}
平均値が正解だとわからないと解けないのか？と思うかもしれませんが、シミュレーションで解くこともできます。
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、aの受け取り
int N = sc.nextInt();
int[] a = new int[N];
for(int i=0;i<N;i++){
a[i] = sc.nextInt();
}
//初期値として大きい値を入れる
int answer = Integer.MAX_VALUE;
//-100から100までしかaiは取らないのでその間で全探索
for(int i=-100;i<101;i++){
//シミュレーション
int sum = 0;
for(int j=0;j<N;j++){
sum += (i-a[j])*(i-a[j]);
}
//最小値更新か？
if(answer>sum){
answer = sum;
}
}
//答えの出力
System.out.println(answer);
}
}
まぁ知っといて損は無いですね。
D - アンバランス
問題文はこちら
公式解説通りです。
ある部分文字列がアンバランスであるとき、その文字列のある部分文字列もアンバランスであり、最小のアンバランスな部分文字列は以下の二通りしか存在しません。
・XX(二文字とも同じ)
・XYX(一個挟んで同じ)
したがって、これを先頭から順に探せば高速に解くことができます。
import java.io.*;
//文字を分割するクラス
class subMain{
public static String[] parStr(String someStr){
String[] str = someStr.split("");
return str;
}
}
class Main{
public static void main(String[] args)throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//文字列の受け取り
String[] str = subMain.parStr(br.readLine());
//for文でカバーできない場合を処理
if(str.length==2&&str[0].equals(str[1])){
System.out.println("1 2");
System.exit(0);
}
//for文で全探索
for(int i=0;i<str.length-2;i++){
if(str[i].equals(str[i+1])){
System.out.println((i+1)+" "+(i+2));
System.exit(0);
}
else if(str[i].equals(str[i+2])){
System.out.println((i+1)+" "+(i+3));
System.exit(0);
}
}
//見つけられなかった=アンバランスな部分文字列は存在しない
System.out.println("-1 -1");
}
}
もうちょっと簡潔に書くとこんな感じでしょうか。
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Sの受け取り
char[] S = sc.next().toCharArray();
//隣り合ってる場合
for(int i=1;i<S.length;i++){
if(S[i-1]==S[i]){
System.out.println(i+" "+(i+1));
return;
}
}
//一個挟んで同じ場合
for(int i=2;i<S.length;i++){
if(S[i-2]==S[i]){
System.out.println((i-1)+" "+(i+1));
return;
}
}
//見つけられなかった=アンバランスな部分文字列はそんざいしない
System.out.println("-1 -1");
}
}
範囲外参照に気をつければ比較的簡単な実装ですね。
解法が思いつけば、の話ですが･･･。
感想
A、B:易しい。
C:知ってれば簡単。知らなくても制約を見ればすぐできるかも？
D:難 し い
って感じでした。
4問体制のときのCとDの崖は凄いですね･･･。全然解法が思いつかない･･･。