はじめに
これはコンテスト中に解いた解法なので少々煩雑だとは思いますが、ご理解いただけると嬉しいです。
では、コードを解説していきます。
A - ASCII code
問題文はこちら
普通にint型をchar型に変型して出力してやればいいです。
A.java
import java.util.*;
class Main{
static Scanner sc = new Scanner(System.in);
public static void main(String[] args){
//値の取得
int N = readI();
//Nをchar型に変型して出力
System.out.println((char)N);
}
//以下使用したテンプレ
public static int readI(){return sc.nextInt();}
}
最初言語をPythonとして提出しちゃって二回もREを取ってしまいました。
B - Takahashi's Failure
問題文はこちら
Aの値を順に見ていって、最大値に対してBにあるかをfor文で回していけば十分時間内に終わります。
B.java
import java.util.*;
class Main{
static Scanner sc = new Scanner(System.in);
public static void main(String[] args){
//値の取得
int N = readI();
int K = readI();
int[] A = readIs(N);
int[] B = readIs(K);
//食べるかもしれないかをboolean型で管理
boolean can = false;
//最大値管理用変数
int max = 0;
//全探索
for(int i=0;i<N;i++){
//0～iにおいてA[i]は最大値か？
if(A[i]>max){
//iはBに入ってる？
for(int j=0;j<K;j++){
//入ってるならtrueに
if(i+1==B[j]){
can = true;
break;
}
//とりあえずelseならfalseに
else can = false;
}
//max値更新
max = A[i];
}
//max値と同値でまだcan=false？
if(A[i]==max&&!can){
//iはBに入ってる？
for(int j=0;j<K;j++){
//入ってるならtrueに
if(i+1==B[j]){
can = true;
break;
}
}
}
}
//canに応じた解答を出力
retE(can);
}
//以下使用したテンプレ
public static void retE(boolean hantei){
if(hantei)System.out.println("Yes");else System.out.println("No");System.exit(0);}
public static int readI(){return sc.nextInt();}
public static int[] readIs(int num){
int[] ans = new int[num];for(int i=0;i<num;i++) ans[i] = sc.nextInt();return ans;}
}
A[i]>maxの時の処理ですが、else can = falseを忘れてしまうとmax値が更新される時もずっとtrueのままで処理されてしまうので注意してください(実体験)。
C - Slot Strategy
問題文はこちら
Nが小さいので0～9まで、実際に試してみて何秒かかるか調べてしまいましょう。
C.java
import java.util.*;
class Main{
static Scanner sc = new Scanner(System.in);
public static void main(String[] args){
//値の取得
int N = readI();
//スロットの準備
int[][] slots = new int[N][10];
for(int i=0;i<N;i++){
String[] temp = sc.next().split("");
for(int j=0;j<10;j++){
slots[i][j] = Integer.parseInt(temp[j]);
}
}
//出力したい最小値用変数
int min = Integer.MAX_VALUE;
//0～9までを全探索
for(int i=0;i<10;i++){
//時間管理用変数
int temp = 0;
//スロット全部を見るためにforループ(0秒から順にスロットの数字を見ていく)
for(int j=0;j<10;j++){
//数字が被っている回数を管理するための変数
int chohuku = 0;
//j秒の時のスロットを順に見ていく
for(int k=0;k<N;k++){
//調べている数字(i)と同じ？
if(slots[k][j]==i){
//重複を加味した時間と、今かかると想定している時間の大きい方を代入
temp = Math.max(chohuku*10 + j,temp);
chohuku++;
}
}
}
//最小値更新か？
if(min>temp)
min = temp;
}
//出力
retE(min);
}
//以下使用したテンプレ
public static void retE(int ret){System.out.println(ret);System.exit(0);}
public static int readI(){return sc.nextInt();}
}
同じ時間に他のスロットと数字が被ると+10秒されることに注意しましょう。
コンテスト中の感想
A：久しぶりに優しい問題が来て嬉しかった(ただし、提出ミスでペナルティを2回も受けたのでちょっと悲しかった)
B、C：実装はちょっとだけめんどくさかったけど特に悩まず解けた。
D：全く解法が思いつかなかった･･･。
って感じでした。
その内できたらD問題も解いて載せようと思います。
追記(D - Distinct Trio)
kyopro_friendsさんの解説を見ながら解いたのでほぼそのままの実装です。
Aはソート済みとします。Ajを決めれば、Aiとして選べる種類mとAkとして選べる種類nからmn種の組合せが存在します。
よって、1から順にいくつ存在するかを記録した配列を準備してやれば十分高速で処理できます。
D.java
class Main{
public static void main(String[] args){
java.util.Scanner sc = new java.util.Scanner(System.in);
//Nの取得
int N = sc.nextInt();
//Aを格納
int[] A = new int[N];
for(int i=0;i<N;i++)A[i] = sc.nextInt();
//1～iまでの要素の数を記録する
long[] sum = new long[(int)2e5+1];
for(int i=0;i<N;i++)sum[A[i]]++;
for(int i=1;i<sum.length;i++)sum[i] += sum[i-1];
//組合せを数え上げる
long count = 0;
for(int i=0;i<N;i++) count += sum[A[i]-1]*(N-sum[A[i]]);
System.out.println(count);
}
}
いやぁ、天才的な解き方ですね…。自分には思いつかないわ…(しかもコンテストの限られた時間だと難しい…)。