はじめに
今回はEまでコンテスト中に、Fをコンテスト後に通したので、それを載せようと思います。
では、見ていきましょう。
なお、僕のライブラリは提出結果よりご確認ください。
A - Nine
問題文はこちら
A%3が0以外であり、$A+1=B$であるかどうかを判定すれば良いです。
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 ) {
//A、Bの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
//Aが3の倍数なら合致するBは存在しない
if(A%3==0){
out.println("No");
}
else{
//A<Bより、A+1==B以外に合致するものは存在しない
if(A+1==B)
out.println("Yes");
else
out.println("No");
}
out.close();
}
}
速く解こうとして上下もYes判定してしまってペナルティを頂いてしまいました…。
問題文、ちゃんと読もう。
B - Rotate
問題文はこちら
角の処理が面倒ですが、二重for文で外側かを判定しながら解きました。
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、Aの受け取り
int N = sc.nextInt();
char[][] A = sc.nextCharArray(N);
//答え用配列
char[][] B = new char[N][N];
//順に構築
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
//端っこ？
if(Math.min(i,j)==0||Math.max(i,j)==N-1){
//角だけ気を付けて場合分け
if(j==0){
if(i==N-1)
B[i][j] = A[i][j+1];
else
B[i][j] = A[i+1][j];
}
else if(j==N-1){
if(i==0)
B[i][j] = A[i][j-1];
else
B[i][j] = A[i-1][j];
}
else if(i==0){
if(j==0)
B[i][j] = A[i+1][j]; //よく考えたらこれ要らないじゃん
else
B[i][j] = A[i][j-1];
}
else{
if(j==N-1)
B[i][j] = A[i-1][j]; //よく考えたらこれ要らないじゃん
else
B[i][j] = A[i][j+1];
}
}
//端っこじゃなければそのまま
else
B[i][j] = A[i][j];
}
}
//出力
out.println(B);
out.close();
}
}
最初外側だけ90度回転だと思ってサンプルが合わなくて焦ってしまいました。
なんか今回誤読が多い…。
C - Medicine
問題文はこちら
いもす法の要領で、TreeMapに記録して先頭から順に見ていきました。
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、K、a、bの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
int[][] ab = sc.nextInt(N,2);
//mapに記録
TreeMap<Integer,Long> map = new TreeMap<>();
for(int[] m:ab){
map.merge(1,(long)m[1],Long::sum);
map.merge(m[0]+1,(long)-m[1],Long::sum);
}
//先頭から見ていく
long now = 0;
for(Map.Entry<Integer,Long> e:map.entrySet()){
now += e.getValue();
if(now<=K){ //最初にsum(b)が加算されるので誤判定はしない
out.println(e.getKey());
break;
}
}
out.close();
}
}
Twitterで見かけましたが、普通にソートして引いていけば良い話でしたね…。
D - Add One Edge
問題文はこちら
頂点1と頂点$N_1+N_2$それぞれの一番遠い頂点同士を結ぶのが最適なので、一番遠い頂点の距離を求めて解きました。
D.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 ) {
//N1、N2、M、グラフの受け取り
int N1 = sc.nextInt();
int N2 = sc.nextInt();
int M = sc.nextInt();
int[][] graph = sc.nextGraph(N1+N2,M); //隣接行列(1-indexed)
//1からの最長距離をBFSで調べる
int max1 = 0;
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(1);
boolean[] checked = new boolean[N1+N2+1];
checked[1] = true;
while(deq.size()>0){
//距離を1ずつ進める
ArrayDeque<Integer> nextDeq = new ArrayDeque<>();
for(int now:deq){
for(int next:graph[now]){
if(!checked[next]){
checked[next] = true;
nextDeq.add(next);
}
}
}
deq = nextDeq;
max1++;
}
//N1+N2からも同様に
deq.add(N1+N2);
checked[N1+N2] = true;
int max2 = 0;
while(deq.size()>0){
ArrayDeque<Integer> nextDeq = new ArrayDeque<>();
for(int now:deq){
for(int next:graph[now]){
if(!checked[next]){
checked[next] = true;
nextDeq.add(next);
}
}
}
deq = nextDeq;
max2++;
}
//どちらも最長距離+1になってるので辺を一本追加することを考慮して-1
out.println(max1+max2-1);
out.close();
}
}
サクッと解けて良かったです。
E - Family and Insurance
問題文はこちら
自分が被覆されている保険で一番範囲の大きいもののみを保持する配列を準備し、人1から順に更新しながら補償対象者の数を数えることで解きました。
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、pの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] p = new int[N+1];
for(int i=2;i<=N;i++)
p[i] = sc.nextInt();
//一番範囲が広いのを記録しておく
int[] sum = new int[N+1];
while(M-->0){
int x = sc.nextInt();
int y = sc.nextInt();
sum[x] = Math.max(sum[x],y+1);
}
//人1から順に更新
int count = 0;
for(int i=1;i<=N;i++)
if((sum[i] = Math.max(sum[i],sum[p[i]]-1))>0)
count++; //更新しながら1以上の人を数え上げ
//答えの出力
out.println(count);
out.close();
}
}
Eにしては易しい？
F - Box in Box
問題文はこちら
公式解説ガン見して解きました。
F.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、hwdの受け取り
int N = sc.nextInt();
int[][] box = sc.nextInt(N,3);
//h≧w≧dに変換
for(int[] b:box){
int max = MathFunction.max(b);
int min = MathFunction.min(b);
int mid = (b[0]+b[1]-max-min)+b[2];
b[0] = min;
b[1] = -mid; //後々楽なので負で記録
b[2] = max;
}
//wを座圧
TreeSet<Integer> w = new TreeSet<>();
for(int[] b:box)
w.add(-b[1]);
HashMap<Integer,Integer> indexW = new HashMap<>();
int index = 1;
for(Integer num:w)
indexW.put(num,index++);
//minセグ木
SegmentTree<Integer> segT = new SegmentTree<>(index,Integer.MAX_VALUE,true){
public Integer function(Integer a,Integer b){
return Math.min(a,b);
}
};
//hの昇順(wの降順)にソート
ArrayFunction.sort(box);
//順に見ていき
for(int[] b:box){
int W = indexW.get(-b[1]); //何番目かを取得
//W未満のものでd以下のものがあれば全部上回ってるのでYes
if(segT.query(1,W-1)<b[2]){
System.out.println("Yes");
return;
}
//最小値で更新
segT.update(W,Math.min(segT.get(W),b[2]));
}
//ループを抜けた=全部を上回る組み合わせが無かったのでNo
out.println("No");
out.close();
}
}
確かにセグ木と言われれば確かに…ってなるんですが、気づけなかったですねぇ…悲しい…。
感想
A,B:かなり焦った
C:ソート解法良いな…
D,E:ちょっと易しく感じた
F:$h$、$w$、$d$を昇順、降順に入れ替えても良いとか、$h$に関してソートした方が良さそうってのは見えたんですが、それ以上の進展がありませんでした…
って感じでした。
む～ん…。ペナが効いてちょっとレートが下がりました。落ち着いて丁寧に解かなくちゃ、ですねぇ。