はじめに
今回もEまで解けたのでコンテスト中に提出したものを載せます。
では、見ていきましょう。
A - Range Swap
問題文はこちら
for文を5つ書いてそれぞれの区間を出力しました。
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){
//各値の受け取り
int N = System.in.nextInt();
int P = System.in.nextInt();
int Q = System.in.nextInt();
int R = System.in.nextInt();
int S = System.in.nextInt();
int[] A = System.in.nextInt(N);
//1～P-1
for(int i=0;i<P-1;i++)
System.out.print(A[i]+" ");
//R～S
for(int i=R-1;i<S;i++)
System.out.print(A[i]+" ");
//Q+1～R-1
for(int i=Q;i<R-1;i++)
System.out.print(A[i]+" ");
//P～Q
for(int i=P-1;i<Q;i++)
System.out.print(A[i]+" ");
//S+1～N
for(int i=S;i<N;i++)
System.out.print(A[i]+" ");
//最後の改行
System.out.println();
System.out.close();
}
}
1-indexedでA受け取れば-1とか考えなくて済んだかなぁと感じてます。
B - Cat
問題文はこちら
Stringクラスのreplaceメソッドを使って解きました。
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の受け取り
int N = System.in.nextInt();
//Sを受け取ってnaをnyaに置き換える
System.out.println(System.in.next().replace("na","nya"));
System.out.close();
}
}
Aよりも簡単に感じました。
C - Rotate and Palindrome
問題文はこちら
$S$の左端の文字を右端に移動する回数を$i(0 \le i \lt N)$とすると、左端は$i$、右端は$N+i-1 \mathrm{mod} N$になるのでそのように判定するよう実装しました。
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、A、Bの受け取り
int N = System.in.nextInt();
long A = System.in.nextInt();
long B = System.in.nextInt();
//初期解(大きければ良い)
long ans = Long.MAX_VALUE;
//Sの受け取り
String S = System.in.next();
//左端から移動させるのはN-1回までで良い(結局N回やると元の文字列に戻るので)
for(int i=0;i<N;i++){
//文字を書き換えるコストの総数
long temp = 0;
//文字が異なればどちらか一方を書き換えれば良いので+B
for(int j=0;j<N/2;j++)
if(S.charAt((j+i)%N)!=S.charAt((N-j-1+i)%N))
temp += B;
//より小さかったら置き換え
ans = Math.min(ans,temp+A*i);
}
//答えの出力
System.out.println(ans);
System.out.close();
}
}
これもそんなに悩まなかったです。
D - Money in Hand
問題文はこちら
個数制限付き部分和問題と発想が出来てなかったので硬貨を一個一個別の配列に入れてDPをしました。
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、Xの受け取り
int N = System.in.nextInt();
int X = System.in.nextInt();
//硬貨の総数
int sumC = 0;
//硬貨の情報の受け取り
int[][] pair = System.in.nextInt(N,2);
//枚数数え上げ
for(int i=0;i<N;i++)
sumC += pair[i][1];
//各硬貨の価値を全部配列に列挙
int[] coin = new int[sumC];
int index = 0;
for(int i=0;i<N;i++){
for(int j=0;j<pair[i][1];j++){
coin[index++] = pair[i][0];
}
}
//dp[i][j]:i番目の硬貨まででj円が作れるか
boolean[][] dp = new boolean[sumC+1][X+1];
dp[0][0] = true;
//遷移
for(int i=1;i<=sumC;i++){
for(int j=0;j<=X;j++){
//今見ている硬貨を使わない遷移
dp[i][j] |= dp[i-1][j];
//今見ている硬貨を使う遷移
if(j+coin[i-1]<=X)
dp[i][j+coin[i-1]] |= dp[i-1][j];
}
}
//X円、作れた？
System.out.println(dp[sumC][X]?"Yes":"No");
System.out.close();
}
}
なんというか…もっと精進しないとですね…。
E - Souvenir
問題文はこちら
事前に各都市から他の都市への答えを求めておいて、クエリに答えました。
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){
//N、Aの受け取り
int N = System.in.nextInt();
int[] A = System.in.nextInt(N);
//移動できる都市を受け取る
ArrayList<TreeSet<Integer>> canGo = new ArrayList<>();
canGo.add(new TreeSet<>());
for(int i=1;i<=N;i++){
canGo.add(new TreeSet<>());
for(int j=1;j<=N;j++)
if(System.in.nextChar()=='Y')
canGo.get(i).add(j);
}
//移動回数とお土産の価格
int[][] cost = new int[N+1][N+1];
long[][] value = new long[N+1][N+1];
//初期値
for(long[] v:value)
Arrays.fill(v,-1);
//各都市を始点にする
for(int i=1;i<=N;i++){
//今の移動回数で到達している都市
HashSet<Integer> set = new HashSet<>(N);
set.add(i);
value[i][i] = A[i-1];
while(!set.isEmpty()){
//今の都市から移動して到達できる都市
HashSet<Integer> next = new HashSet<>(N);
//今いる都市から行ける都市を調べる
for(int p:set){
for(int nextP:canGo.get(p)){
//違う都市から同一の都市に到達した場合はより価値が高い方で更新
if(next.contains(nextP))
value[i][nextP] = Math.max(value[i][nextP],value[i][p]+A[nextP-1]);
//既に最短で到達してる場合は無視
else if(value[i][nextP]!=-1)
continue;
//未到達なら更新してnextにadd
else{
value[i][nextP] = value[i][p]+A[nextP-1];
next.add(nextP);
cost[i][nextP] = cost[i][p]+1;
}
}
}
//setをnextに置き換え
set = next;
}
}
//Qの受け取り
int Q = System.in.nextInt();
while(Q-->0){
//U、Vの受け取り
int U = System.in.nextInt();
int V = System.in.nextInt();
//到達できているならその答えを、できてないなら-1を出力
if(value[U][V]!=-1)
System.out.println(cost[U][V]+" "+value[U][V]);
else
System.out.println("Impossible");
}
System.out.close();
}
}
これも答えが出るまでかなり時間をかけてしまいました。
基礎力が足りてないですね…。
感想
A:ちょっと大変
B:易しい
C:まぁ易しめ
D:発想が全然出来てなかった…
E:もっと出来てなかった…
という感じでした。
5完はしたけど、遅かったから緑パフォでした。悲しいなぁ。