はじめに
今回はコンテスト中にEまで解けたのでEまで載せようと思います。
なお、僕のライブラリはGitHubよりご確認ください。
では、見ていきましょう。
A - Buy a Pen
問題文はこちら
$C$に該当する変数に適当な大きさの値を代入することで選択しないようにさせて解を求めました。
A.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//R、G、B、Cの受け取り
int R = sc.nextInt();
int G = sc.nextInt();
int B = sc.nextInt();
char C = sc.nextChar(); //一文字目だけで判定できるので一文字だけ受け取る
//該当する変数に大きい値を入れる
if(C=='R')
R = 1000;
if(C=='G')
G = 1000;
if(C=='B')
B = 1000;
//答えの出力
out.println(MathFunction.min(R,G,B));
out.close();
}
}
B - Right Triangle
問題文はこちら
順列全探索で3点の選び方を変えながら内積で直角かを判定しました。
B.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//座標の受け取り
Point[] p = sc.nextPoint(3);
//順列全探索
int[] m = {0,1,2};
boolean flag = false;
do{
int subX1 = p[m[1]].x-p[m[0]].x;
int subY1 = p[m[1]].y-p[m[0]].y;
int subX2 = p[m[2]].x-p[m[0]].x;
int subY2 = p[m[2]].y-p[m[0]].y;
flag |= subX1*subX2+subY1*subY2==0;
}while(ArrayUtil.nextPermutation(m));
//答えの出力
out.println(flag?"Yes":"No");
out.close();
}
}
今思えば三平方の定理が一番手っ取り早いかも…。
C - Sum = 0
問題文はこちら
これはコンテスト後に書いたコードですが、先に$L$の総和を取っておき、先頭から貪欲に値を調整することで答えを構築することで高速に処理できます(詳しくは公式解説で)。
C.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、L、Rの受け取りとsum(L)の計算
int N = sc.nextInt();
int[] L = new int[N];
int[] R = new int[N];
long sum = 0;
for(int i=0;i<N;i++){
sum += L[i] = sc.nextInt();
R[i] = sc.nextInt();
}
//sum(L)が0より大きかったら構築不可なのでNo
if(sum>0){
System.out.println("No");
return;
}
//解の構築
long[] X = new long[N];
for(int i=0;i<N;i++){
long sub = Math.min(R[i]-L[i],-sum);
sum += sub;
X[i] = L[i]+sub;
}
//構築できたら出力、ダメだったらNo
if(sum==0){
System.out.println("Yes");
System.out.print(X[0]);
for(int i=1;i<N;i++){
System.out.print(" ");
System.out.print(X[i]);
}
System.out.println();
}
else{
System.out.println("No");
}
}
}
コンテスト中は$\sum_i X_i$が取り得る値の範囲を求めて、その範囲に$0$が入るように貪欲に値を調整していくというごちゃごちゃしたやり方をしました…。
D - Shortest Path 3
問題文はこちら
ダイクストラ法の典型問題って感じなのでそのまま特に工夫せず実装しました。
D.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = new int[N+1]; //1-indexedで
for(int i=1;i<=N;i++)
A[i] = sc.nextInt();
//隣接リストの構築
ArrayList<ArrayList<int[]>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
while(M-->0){
int U = sc.nextInt();
int V = sc.nextInt();
int B = sc.nextInt();
list.get(U).add(new int[]{V,B});
list.get(V).add(new int[]{U,B});
}
//ダイクストラ
long[] ans = new long[N+1];
Arrays.fill(ans,Long.MAX_VALUE);
PriorityQueue<long[]> queue = new PriorityQueue<>((a,b)->Long.compare(a[1],b[1]));
queue.add(new long[]{1,A[1]});
while(queue.size()>0){
long[] node = queue.poll();
int now = (int)node[0];
long cost = node[1];
if(ans[now]==Long.MAX_VALUE){
ans[now] = cost;
for(int[] p:list.get(now)){
long nextC = cost+p[1]+A[p[0]];
if(nextC<ans[p[0]])
queue.add(new long[]{p[0],nextC});
}
}
}
//答えの出力
long[] answer = new long[N-1];
for(int i=1;i<N;i++)
answer[i-1] = ans[i+1];
out.println(answer);
out.close();
}
}
E - Count Arithmetic Subsequences
問題文はこちら
メモ化再帰で解きました。
$1$項、$2$項の数列は明らかに等差数列なので、$3$項以上の組み合わせについて、等差数列として使用可能な項の数を求めてメモ化することで高速に解を求めました。
E.java
final class Main{
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner(System.in);
private static final SimpleWriter out = new SimpleWriter(System.out,autoFlush);
public static void main(String[] args){
//N、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
int[] ans = new int[N];
//座圧
TreeSet<Integer> set = new TreeSet<>();
for(int a:A)
set.add(a);
HashMap<Integer,Integer> map = new HashMap<>();
int ind = 0;
for(Integer num:set)
map.put(num,ind++);
//各値とそのindexを記録
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<map.size();i++)
list.add(new ArrayList<>());
for(int i=0;i<N;i++)
list.get(map.get(A[i])).add(i);
//3項以上のものを探す
for(int i=N-2;i>=0;i--){
for(int j=i+1;j<N;j++){
ArrayList<Integer> a = dfs(j+1,A[j]-A[i],A[j],N,list,map);
for(int k=0;k<a.size();k++){
ans[k+2] += +a.get(k);
if(MOD<=ans[k+2])
ans[k+2] -= MOD;
}
}
}
//2項以下のものを足して出力
ans[0] = N;
if(N>1)
ans[1] = N*(N-1)>>1;
out.println(ans);
out.close();
}
//メモ化再帰用のクラス
static class Node{
int sub;
int index;
public Node(int s,int i){
sub = s;
index = i;
}
@Override
public boolean equals(Object o){
if(o instanceof Node n){
return sub==n.sub&&index==n.index;
}
return false;
}
@Override
public int hashCode(){
return index<<20^index;
}
public String toString(){
return "["+sub+":"+index+"]";
}
}
private static final HashMap<Node,ArrayList<Integer>> memo = new HashMap<>();
private static final int MOD = 998244353;
private static final ArrayList<Integer> empty = new ArrayList<>();
//dfs(今見ているインデックス、公差、直前の値、その他諸々の値)で再帰
private static ArrayList<Integer> dfs(int index,int sub,int bef,int N,ArrayList<ArrayList<Integer>> list,HashMap<Integer,Integer> map){
//次の項に該当する値が存在するか？
if(map.containsKey(bef+sub)){
//次の項に該当する値が今見ているインデックスより後にあるか？
ArrayList<Integer> l = list.get(map.get(bef+sub));
int nextIndex = Searcher.upSearch(l,index);
if(nextIndex==l.size())
return empty;
//探索済みか？
Node node = new Node(sub,l.get(nextIndex));
if(memo.containsKey(node))
return memo.get(node);
//答えを求めてメモ
ArrayList<Integer> ans = new ArrayList<>();
ans.add(l.size()-nextIndex);
for(int i=nextIndex;i<l.size();i++){
ArrayList<Integer> a = dfs(l.get(i)+1,sub,bef+sub,N,list,map);
for(int j=0;j<a.size();j++){
if(ans.size()==j+1)
ans.add(0);
ans.set(j+1,ans.get(j+1)+a.get(j));
if(MOD<=ans.get(j+1))
ans.set(j+1,ans.get(j+1)-MOD);
}
}
memo.put(node,ans);
return ans;
}
return empty;
}
}
全然サンプルと合わなくてすんごい時間かけてしまった…。
感想
A:ちょっとめんどくさい
B:Bにしては難しめ？
C:パッと公式解説の解法が浮かばなかったのが悔やまれる…
D:易しい
E:かなり苦戦した…
って感じでした。
レートが…悲しい…。