はじめに
今回はコンテスト中にEまで、コンテスト後にF、Gを解いたのでそれを載せようと思います。
では、見ていきましょう。
A - Alternately
問題文はこちら
先頭がFかどうかをbooleanで保持し、反転しながら前後が異なるかを判定しました。
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();
//直前に見た文字はFだったかを管理する変数
boolean flag = S.charAt(0)=='F';
//交互になっているか管理する変数
boolean ans = true;
for(int i=1;i<N;i++){
//「直前と違う文字か」との論理積を取って、flagを反転
ans &= flag^(S.charAt(i)=='F');
flag = !flag;
}
//交互になってた？
out.println(ans?"Yes":"No");
out.close();
}
}
Twitterで見かけましたが、MMかFFが含まれているかどうかで判定する方法もあるそうです。
その方が個人的に好きですね。
B - Chessboard
問題文はこちら
二重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 ) {
//S(変数名はmap)の受け取り
char[][] map = sc.nextCharArray(8);
//*を探して、見つかったら場所を出力
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(map[i][j]=='*'){
System.out.print((char)(j+'a'));
System.out.println(8-i);
return;
}
}
}
out.close();
}
}
番号が下からなのにちょっと戸惑ってしまいました。
C - Gap Existence
問題文はこちら
尺取り法のように実装しました。
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、X、Aの受け取り
int N = sc.nextInt();
int X = sc.nextInt();
int[] A = sc.nextInt(N);
//Aはソートしても構わないのでソートする
ArrayFunction.sort(A);
//jに対応するindex
int index = 0;
//A_iを決めて、jを尺取り法の要領で探す
for(int i=0;i<N;i++){
while(index<N&&A[index]-A[i]<X)
index++;
//見つかったらYesを出力して終了
if(index<N&&A[index]-A[i]==X){
System.out.println("Yes");
return;
}
}
//forを抜けた=見つからなかったので、Noを出力
out.println("No");
out.close();
}
}
最初$i$≠$j$だと思ってたのでこのような実装をしましたが、HashSetを用いた実装の方が楽でしたね。
C改.java
import java.util.Scanner;
import java.util.HashSet;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Xの受け取り
int N = sc.nextInt();
int X = sc.nextInt();
HashSet<Integer> set = new HashSet<>();
//Aをsetに入れていく
while(N-->0)
set.add(sc.nextInt());
//各要素に対して、A_jに対応する値が存在するか調べてboolean型変数と論理和を取る
boolean canMake = false;
for(int A:set)
canMake |= set.contains(A-X);
//適切な組み合わせが見つかった？
System.out.println(canMake?"Yes":"No");
}
}
多分コード書く前に気付いたらこっちで書いていたと思います。
D - M<=ab
問題文はこちら
$a \le b$と仮定すると$1 \le a \le \lceil\sqrt{M}\rceil$の範囲しか考えなくて良いのでその範囲で全探索しました。
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 ) {
//N、Mの受け取り
long N = sc.nextLong();
long M = sc.nextLong();
//aとして考えられる最大値を求める
long a = (long)Math.sqrt(M);
if(a*a<M)
a++;
//初期値の時点でaがNより大きい場合は解が存在しないので-1、それ以外は暫定的にa*bを代入
long b = a;
long ans = 0<a&&a<=N?a*b:-1;
//aが適正値の範囲で探索
while(1<a&&a<=N){
a--;
//bを求め、bがNを超えていたら終了
b = M/a;
if(a*b<M)
b++;
if(N<b)
break;
//a、bともに適正な値ならansとa*bで、より小さい方を代入
ans = Math.min(ans,a*b);
}
//答えの出力
out.println(ans);
out.close();
}
}
ちょっと悩みましたが、比較的早めに気づけて良かったです。
E - Transition Game
問題文はこちら
トポロジカルソートを利用して解きました。
各値を頂点として、$i$から$A_i$へ伸びる有向辺を貼り、入次数が0になるような頂点とその頂点から伸びる辺を削除し、最終的に残った頂点の合計が答えに対応します。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//グラフの構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
for(int i=0;i<N;i++)
list.get(i+1).add(A[i]);
//トポロジカルソート(入次数が0になった頂点を削除していく(削除した個数はanswerに))
int[] count = new int[N+1];
for(ArrayList<Integer> path:list){
for(int point:path){
count[point]++;
}
}
int answer = 0;
ArrayDeque<Integer> deq = new ArrayDeque<>();
for(int i=1;i<=N;i++){
if(count[i]==0){
deq.add(i);
answer++;
}
}
while(deq.size()>0){
int nowP = deq.pollFirst();
for(int nextP:list.get(nowP)){
if(--count[nextP]==0){
deq.add(nextP);
answer++;
}
}
}
//削除されなかった=上手くSiを選べばiに出来るので、Nからanswerを引いた値が答え
out.println(N-answer);
out.close();
}
}
ライブラリからコピって整形した感じなのでちょっと変に見えるかも…。
F - Simultaneous Swap
問題文はこちら
公式解説の通りです。
公式解説では$A$と$B$が異なると判定したらNoを出力して即座に終了していますが、僕のコードでは$A$に重複する値があるかどうかまで見終わってから判定しています。
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、A、Bの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(N);
//BIT
BIT bitA = new BIT(N+1);
BIT bitB = new BIT(N+1);
//反転数を数える
long sum = 0;
for(int i=0;i<N;i++){
sum += bitA.sum(N+1)-bitA.sum(A[i]);
bitA.add(A[i],1);
sum += bitB.sum(N+1)-bitB.sum(B[i]);
bitB.add(B[i],1);
}
//比較するためにソート
ArrayFunction.sort(A);
ArrayFunction.sort(B);
boolean isSame = true;
boolean hasSameValue = false;
//同一の多重集合かの判定と、重複する要素を持っているかの判定
for(int i=0;i<N;i++){
isSame &= A[i]==B[i];
if(i!=0)
hasSameValue |= A[i-1]==A[i];
}
//解を持つ条件か判定
if(isSame&&(hasSameValue||sum%2==0))
out.println("Yes");
else
out.println("No");
out.close();
}
}
G - Polygon and Points
問題文はこちら
これも公式解説の通りです。
平面走査？ってやつでやってみました。
G.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、多角形の頂点の受け取り
int N = sc.nextInt();
int[][] point = sc.nextInt(N,2);
//xが最小、最大のものを探しておく
int minIndex = -1;
int minX = Integer.MAX_VALUE;
int maxIndex = -1;
int maxX = Integer.MIN_VALUE;
for(int i=0;i<N;i++){
if(point[i][0]<minX){
minIndex = i;
minX = point[i][0];
}
if(point[i][0]>maxX){
maxIndex = i;
maxX = point[i][0];
}
}
//Qと各点の受け取り
int Q = sc.nextInt();
int[][] query = new int[Q][3];
for(int i=0;i<Q;i++){
query[i][0] = sc.nextInt();
query[i][1] = sc.nextInt();
query[i][2] = i; //後で使うので点の番号も持っておく
}
//x座標でソート
ArrayFunction.sort(query);
//答えを保持しておく用の配列
String[] ans = new String[Q];
//ソートされた各点を先頭から見ていく
int index = 0;
//多角形の左端よりも左にあるものは全てOUT
while(index<Q&&query[index][0]<minX)
ans[query[index++][2]] = "OUT";
//多角形の上側の点
int upperIndex = (minIndex+N-1)%N;
//多角形の下側の点
int lowerIndex = (minIndex+1)%N;
//右端につくまでの間の点を処理
while(index<Q&&query[index][0]<maxX){
//上側の点のx座標が調べる点のx座標よりも大きくなるまでずらす
while(point[upperIndex][0]<query[index][0])
upperIndex = (upperIndex+N-1)%N;
//下側の点のx座標が調べる点のx座標よりも大きくなるまでずらす
while(point[lowerIndex][0]<query[index][0])
lowerIndex = (lowerIndex+1)%N;
//外積
long s = crossProduct(query[index],point[upperIndex],point[(upperIndex+1)%N]);
long t = crossProduct(query[index],point[lowerIndex],point[(lowerIndex+N-1)%N]);
//内積
long u1 = innerProduct(query[index],point[upperIndex],point[(upperIndex+1)%N]);
long u2 = innerProduct(point[upperIndex],point[upperIndex],point[(upperIndex+1)%N]);
long v1 = innerProduct(query[index],point[lowerIndex],point[(lowerIndex+N-1)%N]);
long v2 = innerProduct(point[lowerIndex],point[lowerIndex],point[(lowerIndex+N-1)%N]);
//外積から、多角形内部か判定
if(0<s&&t<0)
ans[query[index++][2]] = "IN";
//外積と内積から、辺上か判定
else if(s==0&&check(u1,u2)||t==0&&check(v1,v2))
ans[query[index++][2]] = "ON";
//上記の条件に合致しない=外部
else
ans[query[index++][2]] = "OUT";
}
//多角形の右端の辺がy軸に平行だった時用の処理(右端の各点のy座標を求める)
int y1,y2;
if(point[(maxIndex+N-1)%N][0]==maxX){
y1 = Math.min(point[(maxIndex+N-1)%N][1],point[maxIndex][1]);
y2 = Math.max(point[(maxIndex+N-1)%N][1],point[maxIndex][1]);
}
else if(point[(maxIndex+1)%N][0]==maxX){
y1 = Math.min(point[(maxIndex+1)%N][1],point[maxIndex][1]);
y2 = Math.max(point[(maxIndex+1)%N][1],point[maxIndex][1]);
}
else{
y1 = y2 = point[maxIndex][1]; //y軸に平行な辺が無ければ右端の点の座標を代入
}
//多角形の右端とx座標が同一な点の判定
while(index<Q&&query[index][0]==maxX){
ans[query[index][2]] = y1<=query[index][1]&&query[index][1]<=y2?"ON":"OUT";
index++;
}
//多角形の右端より右側にある点はOUT
while(index<Q)
ans[query[index++][2]] = "OUT";
//各判定結果を改行区切りで出力
out.println(ans,'\n');
out.close();
}
//内積用メソッド
private static long innerProduct(int[] p1,int[] p2,int[] baseP){
long a1 = p1[0]-baseP[0];
long b1 = p1[1]-baseP[1];
long a2 = p2[0]-baseP[0];
long b2 = p2[1]-baseP[1];
return a1*a2+b1*b2;
}
//外積用メソッド
private static long crossProduct(int[] p1,int[] p2,int[] baseP){
long a1 = p1[0]-baseP[0];
long b1 = p1[1]-baseP[1];
long a2 = p2[0]-baseP[0];
long b2 = p2[1]-baseP[1];
return a1*b2-b1*a2;
}
//aが0とbの間か判定するめそっど
private static boolean check(long a,long b){
return b<0?b<=a&&a<=0:0<=a&&a<=b;
}
}
難しかったです。けど理解はできたので、非常に勉強になったなと思いました。
感想
A,B:易しい
C:ちょっと悩んでしまってけれど、易しい方
D:√Mまで調べれば良さそうだな～ってのに気づいてからはすぐ実装できた
E:トポロジカルソートで上手くできそうって気づけて良かった
F,G:全然解法が思いつかなかった…
って感じでした。
GはChatGPTに一度聞いてみたんですが、そもそもコードを理解できず、修正を繰り返しているうちにコンテストが終わってました。やはり自分の実力以上のことは丸投げできないですね…精進します…。