はじめに
これはコンテスト中に解いた解法なので少々煩雑だとは思いますが、ご理解いただけると嬉しいです。
では、コードを解説していきます。
A - Last Two Digits
問題文はこちら
下二桁を出力すれば良いんですが、int型で受け取っちゃうと01が1になっちゃったり、わざわざ長さを整えるためにString.formatみたいなの使ったりするのはめんどくさいのでString型のまま受け取ってやりましょう。
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの取得
String str = read();
//substringで下二桁を切り出して出力
println(str.substring(str.length()-2,str.length()));
flush();
}
/*テンプレ一覧
・String read() ：一行取得(String型)
・void println(String) ：改行あり出力
・void flush() ：出力のflush
*/
public static String read()throws IOException{return br.readLine();}
public static void println(Object T){pw.println(T);}
public static void flush(){pw.flush();}
}
大体80ms以内に終わりますね。
B - Practical Computing
問題文はこちら
問題文では何言ってるか正直わからなかったんですが、出力例を見て「パスカルの三角形」じゃん！って思ったのでそれを出力するコードを書きました。一つ前の配列だけ保持しておいて、端っこ以外は右上、左上を加算するようにしました。
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの取得
int N = readInt();
//最初だけ出力
int[] before = {1};
printAllln(before,"");
//2行目以降はfor文で回す
for(int i=2;i<=N;i++){
//出力用配列
int[] nums = new int[i];
//左端は1
nums[0] = 1;
//中の方は前の配列を参照して構成
for(int j=1;j<before.length;j++){
nums[j] = before[j-1]+before[j];
}
//右端は1
nums[nums.length-1] = 1;
//出力
printAllln(nums," ");
//必要あるかわからないけど念のためnull代入してから今の配列を格納
before = null;
before = nums;
}
//最後にフラッシュ
flush();
}
/*テンプレ一覧
・int readInt() ：int型取得(行まるごと)
・void println(int) ：改行あり出力
・void printAllln(配列,String) ：全て出力(Stringは区切り文字、最後に改行)
・void flush() ：出力のflush
*/
public static int readInt()throws IOException{return Integer.parseInt(br.readLine());}
public static void println(Object T){pw.println(T);}
public static void printAllln(int[] T,String str){for(int i=0;i<T.length-1;i++){pw.print(T[i]);pw.print(str);};println(T[T.length-1]);}
public static void flush(){pw.flush();}
}
割とパスカルの三角形の上手いコードがありそうな気もしますが、加算のみで処理した方が速いと思ったのでこの実装です。
C - K Swap
問題文はこちら
普通に全部入れ替えて･･･なんてやっていたらN=200000、K=1の時に地獄と化します。ここでキーとなるのがi番目(0≦i<N-K)とi+K番目のみ入れ替えられるという点です。i番目の数字と入れ替えることができるのi+tK番目(tは自然数)(i+tK<N)の数字のみです。ですので、i番目の数字をi modK番目のリストに入れてそれぞれのリストをソート、また順番に元の配列に戻していったときに昇順になっているかを見れば判定ができます。
import java.io.*;
import java.util.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//NとMの取得(行まるごと取得して空白区切り)
String[] temp = reads();
int N = Integer.parseInt(temp[0]);
int K = Integer.parseInt(temp[1]);
//K=1なら全部入れ替えられるのでYes
if(K==1){
System.out.println("Yes");
exit();
}
//K個分のリストの準備
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<K;i++){
list.add(new ArrayList<Integer>());
}
//数列の取得(行まるごと+空白区切り)
String[] nums = reads();
for(int i=0;i<N;i++){
//i%K番目のリストに数字を加える
list.get(i%K).add(Integer.parseInt(nums[i]));
}
//全リストソート
for(int i=0;i<K;i++){
Collections.sort(list.get(i));
}
//初期値設定(0でもMIN_VALUEでも、初項以下なら何でも可)
int temp1 = -1;
//順に取り出していく
for(int i=0;i<N;i++){
//i番目の数字はi%K番目のリストのi/K番目(小数部分切り捨て)
int temp2 = list.get(i%K).get(i/K);
//一つ前より小さい？
if(temp1>temp2){
//小さかったらNo
println("No");
exit();
}
//直前の数字として格納
temp1 = temp2;
}
//全部大丈夫だったらYes
println("Yes");
exit();
}
/*テンプレ一覧
・String[] reads() ：一行分を空白区切りで取得(String型配列)
・void println(何か) ：改行あり出力
・void exit() ：戻り値0を返してプログラムを終了(flushアリ)
*/
public static String[] reads()throws IOException{return br.readLine().split(" ");}
public static void println(Object T){pw.println(T);}
public static void exit(){pw.flush();System.exit(0);}
}
今更だけど、printlnじゃなくて全部System.out.println()+System.exit(0)でも良い気がします。わざわざ出力とflushを分ける必要が無いですし･･･。
コンテスト中の感想
A：比較的簡単。助かる。
B：数学的面が大きい気がする。
C：コンテスト中になかなか思いつかなくてかなり時間食った。要復習。
って感じでした。
Dも解きたかったんですが、知識が足らず･･･。Eも何を言っているのか全くわからなくてそっと問題文を閉じてしまいました。
改めて復習した時に解けたら追記します。
以下追記
D - Together Square
問題文はこちら
単純に全探索するとTLEをいただいてしまうので、iを固定して可能な限り模索する量を減らします。iの因数のうち、最大の平方数(例えば、80なら16)でiを割った値をkとすれば、k*jを平方数にできるようなjのみを模索すれば良いですね。ということで、$j=k\times m^2(m^2≦N/k)$であることから条件を満たすmの数を数えれば良いです。
import java.io.*;
class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter pw = new PrintWriter(System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
int N = readInt();
//答え用変数
long ans = 0;
//素因数内の最小の平方数を格納するための配列
int[] pows = new int[N+1];
//1～Nまで調べる
for(int i=1;i<=N;i++){
for(int j=1;j*j<=i;j++){
//j^2を因数に持つか？
if((i%(j*j))==0){
//持っているなら更新
pows[i] = j*j;
}
}
}
//iは固定する
for(int i=1;i<=N;i++){
//平方数である因数を除去
int temp = i/pows[i];
for(int j=1;j*j*temp<=N;j++){
//j^2 × tempが取り得る値(すなわちN以下)なら+1する
ans++;
}
}
//答えの出力
println(ans);
flush();
}
/*テンプレ一覧
・int readInt() ：int型取得(行まるごと)
・void println(何か) ：改行あり出力(引数無しも可)
・void flush() ：出力のflush
*/
public static int readInt()throws IOException{return Integer.parseInt(br.readLine());}
public static void println(Object T){pw.println(T);}
public static void flush(){pw.flush();}
}
コード自体は簡単なんですが、コンテスト中に解法はなかなか思いつかないですね…。