はじめに
今回はEまでコンテスト中に解けたのでそれを載せようと思います。
では見ていきましょう。
なお、ライブラリの内容は提出結果からご覧ください。
A - Treasure Chest
問題文はこちら
フラグで|の中かどうかを管理しながら調べました。
A.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//|の中かどうか
boolean flag = false;
//*が中にあったかどうか
boolean in = false;
for(int i=0;i<N;i++){
//|を見つけたらflagを反転
if(S.charAt(i)=='|')
flag = !flag;
//*を見つけたら中にあったかをinに代入
if(S.charAt(i)=='*')
in |= flag;
}
//中にあった？
out.println(in?"in":"out");
out.close();
}
}
正規表現で表して検索する方法もありますが(原案者の実装より)、エスケープが必要でなんか嫌だなぁと思ったのでこっちで実装しました。
B - Trick Taking
問題文はこちら
HashMapで各色をkey、最大値を持っている人の番号をvalueにして保持し、$T$が含まれているかどうかで条件分岐しました。
B.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、T、C、Rの受け取り
int N = sc.nextInt();
int T = sc.nextInt();
int[] C = sc.nextInt(N);
int[] R = sc.nextInt(N);
//key:色の番号、value:最大値を持っている人の番号
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<N;i++){
//Rがより大きい方のindexをvalueに
map.merge(C[i],i,(s,t)->{
if(R[s]<R[t])
return t;
return s;
});
}
//Tがあったかどうかで条件分岐(0-indexedなので+1)
if(map.containsKey(T))
out.println(map.get(T)+1);
else
out.println(map.get(C[0])+1);
out.close();
}
}
そこまで難しくはなかったですね。
C - Dango
問題文はこちら
-の位置をArrayListに入れていき、前後の差から長さを調べて最大値を探しました。
C.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//-の位置をlistに入れる
ArrayList<Integer> list = new ArrayList<>();
for(int i=0;i<N;i++){
if(S.charAt(i)=='-')
list.add(i);
}
//-と隣り合うoの長さを前後をみて調べる
int before = -1;
int ans = 0;
for(int i=0;i<list.size();i++){
int max = Math.max(list.get(i)-before-1,(i+1==list.size()?N:list.get(i+1))-list.get(i)-1);
ans = Math.max(ans,max);
before = list.get(i);
}
//1以上のものが見つかればそれを、見つからなければ-1を
out.println(ans>0?ans:-1);
out.close();
}
}
どうだって良いですけど-o-o-って眼鏡っぽいですね。
D - Find by Query
問題文はこちら
細かい説明は公式解説に任せますが、二分探索で求められると思い、それを実装しました。
D.java
final class Main {
private static final boolean autoFlush = true;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Nの受け取り
int N = sc.nextInt();
//上下限設定
int a = 1;
int b = N;
//暫定的な答え
int ans = 1;
//二分探索
while(a-b<1){
int c = (a+b)/2;
out.println("? "+c);
int result = sc.nextInt();
if(result==0)
a = (ans=c)+1;
else
b = c-1;
}
//答えの出力
out.println("! "+ans);
out.close();
}
}
!が抜けてないか数回確認しました(過去に経験があるので…)。
E - Nearest Black Vertex
問題文はこちら
頂点$p_i$から距離$d_i$であるような頂点と$d_i$未満であるような頂点をそれぞれ列挙していき、頂点$p_i$から距離$d_i$であるようないずれかの頂点を黒で塗ることが可能か調べることで判定しました。
E.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、グラフ、Kの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[][] graph = sc.nextGraph(N,M);
int K = sc.nextInt();
//黒に塗るべき頂点の候補で、keyは頂点、valueはp、dのインデックス
HashMap<Integer,ArrayList<Integer>> ok = new HashMap<>();
//白に塗るべき頂点
HashSet<Integer> ng = new HashSet<>();
//全頂点からBFS
for(int $=0;$<K;$++){
int p = sc.nextInt();
int d = sc.nextInt();
int[] dist = new int[N+1];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[p] = 0;
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(p);
while(deq.size()>0){
int now = deq.pollFirst();
for(int next:graph[now]){
if(dist[next]>dist[now]+1){
dist[next] = dist[now]+1;
deq.add(next);
}
}
}
//結果に合わせてok、ngを更新
for(int i=1;i<=N;i++){
if(dist[i]<d){
ng.add(i);
if(ok.containsKey(i))
ok.remove(i);
}
if(dist[i]==d){
if(!ng.contains(i)){
if(ok.containsKey(i)){
ok.get(i).add($);
}
else{
ArrayList<Integer> temp = new ArrayList<>();
temp.add($);
ok.put(i,temp);
}
}
}
}
}
//全インデックスが含まれているか調べる
HashSet<Integer> set = new HashSet<Integer>();
for(ArrayList<Integer> list:ok.values()){
set.addAll(list);
}
//K個全部候補に含まれていた=条件を満たすように塗ることができる
if(set.size()==K){
out.println("Yes");
//答えの構築と出力
int[] ans = new int[N];
if(ok.size()>0){
for(int index:ok.keySet())
ans[index-1] = 1;
}else
ans[0] = 1; //K=0の時用に適当に塗る
out.println(ans,"");
}
//一個でも条件を満たさないならNo
else
out.println("No");
out.close();
}
}
書き直したり消したりを繰り返してたので結構ごちゃごちゃになって時間をかけてしまいました…。
感想
A,B:易しい
C:最長のoを求める問題だと気づけばサクッといける
D:二分探索でいけそうかな～って思えたので良かった
E:ちょっと実装が重くなってしまったかな…
って感じでした。
A問題提出しようとしたときからBad Gatewayが出てしまっていたので非常に慌てました。