はじめに
今回はC、Eはコンテスト後のもの、他はコンテスト中のものを載せようと思います。
では、見ていきましょう。
A - ^{-1}
問題文はこちら
$P_i$に重複はないので普通に先頭から見ていけば良いです。
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){
//N、Xの受け取り
int N = System.in.nextInt();
int X = System.in.nextInt();
//indexを入れる変数
int ans = 0;
//先頭から見ていって、Xである箇所のindexをansに格納
for(int i=1;i<=N;i++)
if(System.in.nextInt()==X)
ans = i;
//答えの出力
System.out.println(ans);
System.out.close();
}
}
問題は無いですね。
B - Playing Cards Validation
問題文はこちら
switch文を使いました。
一文字ずつ受け取って判定してHashSetに追加していって、sizeが$N$かどうかで重複してないかを判定しました。
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();
//全ての文字列が条件を満たしているか管理するisTrueと重複を調べるset
boolean isTrue = true;
HashSet<String> set = new HashSet<String>();
//一つずつ受け取り
for(int i=0;i<N;i++){
//受け取った文字を連結する用のStringBuilder
StringBuilder sb = new StringBuilder();
char c = System.in.nextChar();
//一文字目が条件を満たしているか？
switch(c){
case 'H':
case 'D':
case 'C':
case 'S':
break;
default:
isTrue = false;
}
sb.append(c);
c = System.in.nextChar();
//二文字目も条件を満たしているか？
switch(c){
case 'A':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
case 'T':
case 'J':
case 'Q':
case 'K':
break;
default:
isTrue = false;
}
sb.append(c);
//setに加える
set.add(sb.toString());
}
//全部条件を満たしていてかつ重複が無かったらYes、違うならNo
System.out.println(isTrue&&set.size()==N?"Yes":"No");
System.out.close();
}
}
配列作ってfor文で条件を満たしているか見た方が良かったかもしれません。
C - Ladder Takahashi
問題文はこちら
keyを何階か、valueをその階から移動できる階を記録したHashSetにしたHashMapで情報を保持し、BFSで解きました。
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の受け取り
int N = System.in.nextInt();
//各階から行ける箇所を格納するmap
HashMap<Integer,HashSet<Integer>> list = new HashMap<>();
//A、Bの受け取り
while(N-->0){
int A = System.in.nextInt();
int B = System.in.nextInt();
HashSet<Integer> temp = list.remove(A);
if(temp==null)
temp = new HashSet<Integer>();
temp.add(B);
list.put(A,temp);
temp = list.remove(B);
if(temp==null)
temp = new HashSet<Integer>();
temp.add(A);
list.put(B,temp);
}
//行ける階を記録するsetと、行けるかbfsで調べる用のdeque
TreeSet<Integer> floors = new TreeSet<Integer>();
ArrayDeque<Integer> bfs = new ArrayDeque<Integer>();
bfs.add(1);
floors.add(1);
HashSet<Integer> emptySet = new HashSet<>();
//bfs
while(!bfs.isEmpty()){
Integer now = bfs.pollFirst();
for(Integer num:list.getOrDefault(now,emptySet)){
if(!floors.add(num))
continue;
bfs.add(num);
}
}
//floorsの最大値を返す
System.out.println(floors.last());
System.out.close();
}
}
最初の提出ではDFSで解いたんですが、1994msという疑惑のACをとってしまいました(提出結果)。
D - Takahashi's Solitaire
問題文はこちら
$A$はソートしても答えは変わらないのでソート済みであるとします。
条件を満たすようにカードを出すには$A_{i+1}=A_i \mathrm{or} A_i+1$を満たす連続部分列を左から順に出していけば良いです。ということで$A_i$の前後で差の絶対値が$\mathrm{mod}\ M$で$1$のものを全部足して全要素の和から引けば$A_i$を含むように選んだ時の最小値を求めることができ、それを$A$全体で調べれば良いです(重複して調べないように)。
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、M、Aの受け取り(Aはソートする)
int N = System.in.nextInt();
int M = System.in.nextInt();
int[] A = System.in.nextInt(N);
System.sort(A);
//Aの総和を求めておく
long sum = 0;
for(int num:A)sum += num;
//過去に調べた箇所か管理する用の配列
boolean[] isChecked = new boolean[N];
//答え用変数
long answer = sum;
//先頭から調べていく
for(int i=0;i<N;i++){
if(isChecked[i])
continue;
isChecked[i] = true;
//テーブルに置いたカードの総和を計算する用
long ans = A[i];
//A[i]より小さい方向に調べていく
int back = (i-1+N)%N;
int now = A[i];
while(!isChecked[back]&&((A[back]+1)%M==now||A[back]==now)){
isChecked[back] = true;
now = A[back];
ans += A[back];
back = (back-1+N)%N;
}
//A[i]より大きい方向にも
int front = (i+1)%N;
now = A[i];
while(!isChecked[front]&&(A[front]==(now+1)%M||A[front]==now)){
isChecked[front] = true;
now = A[front];
ans += A[front];
front = (front+1)%N;
}
//最小値を更新した？
if(answer>sum-ans)
answer = sum-ans;
}
//答えの出力
System.out.println(answer);
System.out.close();
}
}
そんなには悩まなかったです。助かりました。
E - Crystal Switches
問題文はこちら
01BFSというものを実装しました(今回初めて)。
$1～N$は$0$の辺が通行できるとき、$N+1～2N$は$1$の辺が通行できるときの頂点$1～N$として、
$cost[i]:$頂点$i$にたどり着ける最小操作数
として保持するようにしました。
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、M、Kの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int K = System.in.nextInt();
//各頂点から移動できる頂点を格納するlist
ArrayList<ArrayList<Integer>> route = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<=N*2;i++){
route.add(new ArrayList<Integer>());
}
//各辺を加える(aが0なら1～N、1ならN+1～2Nになるように調整)(別の頂点として保持したいので)
while(M-->0){
int u = System.in.nextInt();
int v = System.in.nextInt();
int a = System.in.nextInt()*N;
route.get(u+a).add(v+a);
route.get(v+a).add(u+a);
}
//スイッチがある=頂点sと頂点s+Nは繋がっているとする
while(K-->0){
int s = System.in.nextInt();
route.get(s).add(s+N);
route.get(s+N).add(s);
}
//bfs用deque
ArrayDeque<Integer> bfs = new ArrayDeque<Integer>();
//最初は1の辺を通れるのでN+1が初期値
bfs.add(N+1);
//移動にかかる最小コストを記録する配列
int[] cost = new int[2*N+1];
int max = (int)1e9;
Arrays.fill(cost,max);
cost[N+1] = 0;
//01bfs
while(!bfs.isEmpty()){
int now = bfs.pollFirst();
for(int next:route.get(now)){
if(next%N==now%N&&cost[now]<cost[next]){
bfs.addFirst(next); //スイッチ切り替え時はdequeの先頭に
cost[next] = cost[now];
}else if(cost[next]>cost[now]+1){
bfs.addLast(next); //辺を通っての移動はdequeの末尾に
cost[next] = cost[now]+1;
}
}
}
//スイッチの状態にかかわらず最小コストの方が答え
int ans = Math.min(cost[N],cost[2*N]);
//到達できない=最小コストが初期値のままなのでそのときは-1を、それ以外はansを出力
System.out.println(ans==max?-1:ans);
System.out.close();
}
}
本番中はスイッチを切り替えるときもaddLast(next)してしまっていたのでafter_contestでTLEが出てました。運が味方してくれて良かったです･･･。
感想
A:易しい
B:場合分けがちょっとめんどくさい
C、D:発想自体はそんなに難しくはなかった
E:テストケースに救われた
って感じでした。
今回のはEとFに崖があったのでEまでをもっと早く解ければパフォーマンスが上がったかもしれません。
まぁ、そんな実力は無いんですが･･･。