はじめに
今回もA～Dはコンテスト中、Eはコンテスト後に解いたものを載せようと思います。
では、見ていきましょう。
A - A Recursive Function
問題文はこちら
定義通り再帰しても良いですが、これは1～Nの総乗なのでfor文で回してやれば良いです。
A.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//Nの受け取り
int N = System.in.nextInt();
//初期解
int answer = 1;
//f(0)=1、f(1)=1なので2から
for(int i=2;i<=N;i++)
answer *= i;
//答えの出力
System.out.println(answer);
System.out.close();
}
}
特に問題はないですね。
B - Broken Rounding
問題文はこちら
ちょっとめんどくさいことをしてしまいました。
右から$i$桁目の数字を、Xを$10^i$で割ったあまりを$10^{i-1}$で割って参照して、$5$以上ならその桁と足して$10$になるような値を$X$に足し、$4$以下ならその桁が$0$になるような値を$X$から引きました。
B.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//X、Kの受け取り
long X = System.in.nextLong();
int K = System.in.nextInt();
//1の位から順に四捨五入
for(int i=1;i<=K;i++){
long temp = (X%System.pow(10,i))/System.pow(10,i-1);
if(temp>4)
X += (10-temp)*System.pow(10,i-1);
else
X -= temp*System.pow(10,i-1);
}
//Xの出力
System.out.println(X);
System.out.close();
}
}
右から$K$桁目までは絶対0になることに着目すれば以下のように実装することもできます。
B改.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//X、Kの受け取り
long X = System.in.nextLong();
int K = System.in.nextInt();
//各桁の値に合わせて処理
for(int i=0;i<K;i++){
long temp = X%10;
X /= 10;
//5以上なら繰り上がり
if(temp>4)
X++;
}
//先に今のXを出力(K桁目より上)
System.out.print(X);
//Xが0より大きいならK個分0を出力
if(X>0)
for(int i=0;i<K;i++)
System.out.print(0);
//改行
System.out.println();
System.out.close();
}
}
こっちの方が個人的には好きです。
C - (K+1)-th Largest Number
問題文はこちら
「種類」を知らなくてはいけないので、$A$は別に記録しておいてHashSet(TreeSet)で重複を除きました。
後は自分のライブラリ的に二分探索がしやすいArrayListに入れ直して順に二分探索して求めました。
C.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//N、Aの受け取り
int N = System.in.nextInt();
int[] A = System.in.nextInt(N);
//HashSetにaddして重複を無くす
HashSet<Integer> set = new HashSet<Integer>();
for(int num:A)set.add(num);
//ライブラリ的に助かるのでArrayListに移してソート
ArrayList<Integer> list = new ArrayList<Integer>();
list.addAll(set);
Collections.sort(list);
//種類を記録
int sum = list.size();
//答えを配列に記録する用
int[] answer = new int[N];
for(int num:A){
//二分探索(numより大きい要素のindex)
int index = System.overSearch(list,num);
answer[sum-index]++;
}
//改行区切りで出力
System.out.println(answer,'\n');
System.out.close();
}
}
今思えばTreeSetに入れてTailSet(A_i).size()でも良かったのかなぁと思いましたが、TLEでした（提出結果)。
先頭探すのに時間かかるのかな･･･知らなかった･･･。
D - LRUD Instructions
問題文はこちら
グリッドのサイズが最大$10^9 \times 10^9$になるので当然配列じゃ保持できません。
ということで、壁の情報のみ保持するようにします。ただ、普通に保持していては後々壁に接触するか調べるときに大変なので、$r$をkeyとしたHashMap(valueはTreeSet)と$c$をkeyとしたHashMap(こっちもvalueはTreeSet)を使って記録します。後はそれぞれの進む向きに合わせてTreeSetのceiling、floorを使って壁を探せば良いです。
D.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//H、W、rs、cs、Nの受け取り
int H = System.in.nextInt();
int W = System.in.nextInt();
int rs = System.in.nextInt();
int cs = System.in.nextInt();
int N = System.in.nextInt();
//行、列ごとに記録する用
HashMap<Integer,TreeSet<Integer>> listR = new HashMap<Integer,TreeSet<Integer>>();
HashMap<Integer,TreeSet<Integer>> listC = new HashMap<Integer,TreeSet<Integer>>();
//それぞれ記録
for(int i=0;i<N;i++){
int r = System.in.nextInt();
int c = System.in.nextInt();
if(listR.containsKey(r))
listR.get(r).add(c);
else{
TreeSet<Integer> temp = new TreeSet<Integer>();
temp.add(c);
listR.put(r,temp);
}
if(listC.containsKey(c))
listC.get(c).add(r);
else{
TreeSet<Integer> temp = new TreeSet<Integer>();
temp.add(r);
listC.put(c,temp);
}
}
//Qの受け取り
int Q = System.in.nextInt();
while(Q-->0){
//dに合わせて壁を探し、行けるとこまで移動を繰り返す
char d = System.in.nextChar();
int l = System.in.nextInt();
if(d=='U'){
TreeSet<Integer> blocks = listC.get(cs);
if(blocks==null){
rs = Math.max(1,rs-l);
}else{
Integer num = blocks.floor(rs);
if(num==null)
num = 0;
rs = Math.max(rs-l,num+1);
}
}else if(d=='D'){
TreeSet<Integer> blocks = listC.get(cs);
if(blocks==null){
rs = Math.min(H,rs+l);
}else{
Integer num = blocks.ceiling(rs);
if(num==null)
num = H+1;
rs = Math.min(rs+l,num-1);
}
}else if(d=='L'){
TreeSet<Integer> blocks = listR.get(rs);
if(blocks==null){
cs = Math.max(1,cs-l);
}else{
Integer num = blocks.floor(cs);
if(num==null)
num = 0;
cs = Math.max(cs-l,num+1);
}
}else if(d=='R'){
TreeSet<Integer> blocks = listR.get(rs);
if(blocks==null){
cs = Math.min(W,cs+l);
}else{
Integer num = blocks.ceiling(cs);
if(num==null)
num = W+1;
cs = Math.min(cs+l,num-1);
}
}
//出力
System.out.print(rs);
System.out.print(' ');
System.out.println(cs);
}
System.out.close();
}
}
実装が重いですね･･･。最初躊躇してしまいました･･･。
E - Notebook
問題文はこちら
末尾しか出力しないので、ある箇所の要素とその前の要素を保持したものを作れれば良さそうです。ということで自分自身の値とその前のオブジェクトを保持した、追加と削除が行えるクラスを作ります(BigIntegerみたいに追加ごとに新しいオブジェクトを生成するようにしましょう)。
Data.java
class Data{
//自身の値
int num;
//自分の前のData
Data before;
//コンストラクタ
public Data(int num,Data before){
this.num = num;
this.before = before;
}
//追加(新しいオブジェクトを生成する)
public Data add(int num){
return new Data(num,this);
}
//削除(直前のDataを返す)
public Data delete(){
return before;
}
}
あとはそれぞれの処理を順に行なっていけば良いです。
E.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//Qの受け取り
int Q = System.in.nextInt();
//空の数列用
Data empty = new Data(-1,null);
//初期化
Data A = empty;
//各ページに記録する用のHashMap
HashMap<Integer,Data> book = new HashMap<Integer,Data>();
while(Q-->0){
//queryに合わせて処理
String str = System.in.next();
if(str.equals("ADD")){
int num = System.in.nextInt();
A = A.add(num);
}else if(str.equals("DELETE")){
if(A!=empty)
A = A.delete();
}else if(str.equals("SAVE")){
int page = System.in.nextInt();
book.put(page,A);
}else{
int page = System.in.nextInt();
A = book.getOrDefault(page,empty);
}
//末尾を出力(空白区切り)
System.out.print(A.num);
System.out.print(' ');
}
//最後の改行
System.out.println();
System.out.close();
}
}
公式解説とcirno3153さんの補足も一緒に読むとわかりやすいかと思います。
感想
A:易しい
B:ちょっとめんどくさい
C:そんなに難しくは感じなかった
D:実装が重すぎる･･･
E:全然思いつかなかった･･･
って感じでした。
4完でもパフォーマンスは1200を超えていたので、Dが難関だったようです。とはいえ、5完したかったな･･･(高望み)。