はじめに
今回はコンテスト中にA～Eが解けたので、それをそのまま説明しようかと思います。
では、見ていきましょう。
A - Rightmost
問題文はこちら
StringのlastIndexOfを使いました。
A.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Sの受け取り
String S = System.in.next();
//aのindexを調べる
int ans = S.lastIndexOf("a");
//見つからなかったら-1なので別処理
System.out.println(ans>=0?ans+1:ans);
System.out.close();
}
}
提出後に気付きましたが、Sは" "+Sにしておけばans+1をしなくて済みますね。
B - Adjacency List
問題文はこちら
TreeMap(keyはInteger、valueはTreeSet)で結ばれている都市を記録しました。
B.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Mの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
//都市iの情報を、i-1をkeyとして保持
TreeMap<Integer,TreeSet<Integer>> list = new TreeMap<>();
for(int i=0;i<N;i++)list.put(i,new TreeSet<Integer>());
while(M-->0){
int A = System.in.nextInt();
int B = System.in.nextInt();
list.get(A-1).add(B);
list.get(B-1).add(A);
}
//都市1から順に出力
for(Integer key:list.keySet()){
System.out.print(list.get(key).size());
for(Integer num:list.get(key)){
System.out.print(' ');
System.out.print(num);
}
System.out.println();
}
System.out.close();
}
}
今思えばTreeMapじゃなくてArrayListで良かったんですが、何故か本番は思いつきませんでした。
C - Previous Permutation
問題文はこちら
証明は公式解説に任せますが、$P[i]>P[i+1]$となっている一番後ろの場所を探して$P[i]$以降をArrayListに移し、$P[i]$未満で最大のものをP[i]に、それより後ろはArrayListを降順で並べ替えたもので置き換えれば求めるべき数列になります。
C.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Pの受け取り
int N = System.in.nextInt();
int[] P = System.in.nextInt(N);
//一番後ろのP[i-1]>P[i]の場所を記録する変数
int index = -1;
for(int i=1;i<N;i++)
if(P[i-1]>P[i])
index = i-1;
//P[index]以降のものを記録するList
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=index;i<N;i++)
list.add(-P[i]); //降順で並べるために負数に変換
//ソート
Collections.sort(list);
//P[index]未満で最大のものを探す
int ind = System.overSearch(list,-P[index]);
//P[index]を更新
P[index] = -list.get(ind);
list.remove(ind);
//P[index+1]以降も更新
int j = 0;
for(int i=index+1;i<N;i++)
P[i] = -list.get(j++);
//空白区切りで出力
System.out.println(P," ");
System.out.close();
}
}
提出時はかなり不安がありましたが、合っていたようで安心しました。
D - Divide by 2 or 3
問題文はこちら
$a_1$を$a$、$a_i(2 \le i \le N)$を$A$とします。
$a$と$A$を揃えるには、最大公約数$g$に変換するのが一番操作回数が少なくて済みます。ということで、先頭から順に$g$を求めて$\frac{a}{g}$を$1$にする操作回数、$\frac{A}{g}$を$1$にする操作回数を数え上げていけば良いです。
D.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、a_1を受け取り
int N = System.in.nextInt();
int a = System.in.nextInt();
//操作回数を記録する変数
int ans = 0;
for(int i=1;i<N;i++){
//a_iの受け取り
int A = System.in.nextInt();
//最大公約数を求める
int g = (int)System.gcd(a,A);
//初項をgに揃える回数を数える(a_iより後ろのものも揃えるのでiずつ加算する)
int subA = a/g;
while(subA%2==0){
subA /= 2;
ans += i;
}
while(subA%3==0){
subA /= 3;
ans += i;
}
//2か3で割り切れなかったら終了
if(subA!=1){
System.out.println(-1);
System.exit(0);
}
//初項更新
a = g;
//a_iも揃える回数を数える
subA = A/g;
while(subA%2==0){
subA /= 2;
ans++;
}
while(subA%3==0){
subA /= 3;
ans++;
}
//2か3で割り切れなかったら終了
if(subA!=1){
System.out.println(-1);
System.exit(0);
}
}
//答えの出力
System.out.println(ans);
System.out.close();
}
}
個人的にはそこまで難しく感じなかったですね。
E - Round Trip
問題文はこちら
UnionFindで解きました。
.のマスを見つけたらその上下左右の.のマスと連結していき、Sの周りのマスを記録しておきます。
そして後からSと連結してみて判定しました。
E.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//H、Wの受け取り
int H = System.in.nextInt();
int W = System.in.nextInt();
//UnionFind((i,j)はi*W+jとして扱う)
UnionFind uf = new UnionFind(H*W);
//グリッドの受け取り
char[][] map = System.in.nextCharArray(H);
//Sの座標を記録する変数
int startPoint = -1;
//S周りで`.`のマスを記録するList
ArrayList<Integer> list = new ArrayList<Integer>();
//`.`同士の連結とSの場所の特定、S周りの情報を調べる
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(map[i][j]=='.'){
if(i<H-1&&map[i+1][j]=='.')
uf.unite(i*W+j,(i+1)*W+j);
if(j<W-1&&map[i][j+1]=='.')
uf.unite(i*W+j,i*W+j+1);
if(i>0&&map[i-1][j]=='.')
uf.unite(i*W+j,(i-1)*W+j);
if(j>0&&map[i][j-1]=='.')
uf.unite(i*W+j,i*W+j-1);
}
if(map[i][j]=='S'){
startPoint = i*W+j;
if(i<H-1&&map[i+1][j]=='.')
list.add((i+1)*W+j);
if(j<W-1&&map[i][j+1]=='.')
list.add(i*W+j+1);
if(i>0&&map[i-1][j]=='.')
list.add((i-1)*W+j);
if(j>0&&map[i][j-1]=='.')
list.add(i*W+j-1);
}
}
}
//同じ集合に属しているとfalseが返ってくるようになっているのでfind |= uniteで調べられる
boolean find = false;
for(int num:list)
find |= !uf.unite(startPoint,num);
//答えの出力
System.out.println(find?"Yes":"No");
System.out.close();
}
}
これも比較的早く思いつきました。よかった･･･。
感想
A,B:易しい
C:早く思いつけて良かった
D:Dにしては簡単･･･？
E:初めてUFを使った
って感じでした。
今回は簡単めだった気がするので速解きが求められるコンテストでしたね。