はじめに
今回はコンテスト中にFまで、コンテスト後にGを解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - Wrong Answer
問題文はこちら
$A+B$が$0$になるとき以外は$0$を、$A+B$が$0$のときは$1$を出力するようにしました。
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){
//A、Bの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
//A+Bでない値の出力
out.println(A+B==0?1:0);
out.close();
}
}
B - Adjacency Matrix
問題文はこちら
順に見ていって辺が伸びている頂点をArrayListに記録して出力する方針で実装しました。
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){
//Nの受け取り
int N = sc.nextInt();
//各頂点に対して答えを求める
for(int i=1;i<=N;i++){
//結ばれている頂点を格納する
ArrayList<Integer> ans = new ArrayList<>();
for(int j=1;j<=N;j++)
if(sc.nextInt()>0)
ans.add(j);
//答えの出力
out.println(ans);
}
out.close();
}
}
C - 343
問題文はこちら
回文になっているかは反転しても一致しているかを見れば良いので、Math::cbrtメソッドを使って上限を求めておいて全探索しました。
C.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の受け取り
long N = sc.nextLong();
//探索上限の設定
long max = (long)Math.cbrt(N);
//答えを範囲内で全探索
long ans = 0;
for(long i=1;i<=max;i++){
String S = String.valueOf(i*i*i);
if(S.equals(Converter.reverse(S)))
ans = i*i*i;
}
out.println(ans);
out.close();
}
}
D - Diversity of Scores
問題文はこちら
各選手が今何点か、各点数の選手が何人いるかだけ知れれば良いので、前者は配列で、後者はkeyを得点、valueを人数としたTreeMapで管理して解きました。
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、Tの受け取り
int N = sc.nextInt();
int T = sc.nextInt();
//各得点に対する人数を記録する用のMap(今思えばHashMapでも良かった)
TreeMap<Long,Integer> map = new TreeMap<>();
map.put(0L,N);
//各選手の得点を記録する用の配列
long[] p = new long[N+1];
//各クエリに答える
while(T-->0){
//A、Bの受け取り
int A = sc.nextInt();
long B = sc.nextLong();
//増減の記録
map.merge(p[A],-1,(a,b)->a+b==0?null:a+b);
p[A] += B;
map.merge(p[A],1,Integer::sum);
//種類数を答える
out.println(map.size());
}
out.close();
}
}
E - 7x7x7
問題文はこちら
一つの立方体の位置を$(0,0,0)$に固定してしまえば$6$変数の全探索ができ、一変数あたり$20$通りくらいは回せるので$[-10,10)$の範囲で全探索しました。
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){
//V1～V3の受け取り
int V1 = sc.nextInt();
int V2 = sc.nextInt();
int V3 = sc.nextInt();
int sum = V1+V2*2+V3*3;
//そもそも構築不可能な値ならさっさと省く
if(sum!=MathFunction.pow(7,3)*3){
System.out.println("No");
return;
}
//全探索
for(int i=-10;i<10;i++){
for(int j=-10;j<10;j++){
for(int k=-10;k<10;k++){
for(int l=-10;l<10;l++){
for(int n=-10;n<10;n++){
for(int m=-10;m<10;m++){
//答えが見つかれば答えて終了
if(check(0,0,0,i,j,k,l,m,n,V1,V2,V3)){
System.out.printf("Yes\n0 0 0 %d %d %d %d %d %d\n",i,j,k,l,m,n);
return;
}
}
}
}
}
}
}
//見つからなければNo
out.println("No");
out.close();
}
//条件を満たしているか判定する用のメソッド(めちゃめちゃ汚くなっちゃった…)
private static boolean check(int a1,int b1,int c1,int a2,int b2,int c2,int a3,int b3,int c3,int V1,int V2,int V3){
//三つ全部に含まれる領域
int xMin = MathFunction.max(a1,a2,a3);
int xMax = MathFunction.min(a1,a2,a3);
int yMin = MathFunction.max(b1,b2,b3);
int yMax = MathFunction.min(b1,b2,b3);
int zMin = MathFunction.max(c1,c2,c3);
int zMax = MathFunction.min(c1,c2,c3);
int v3 = Math.max(0,xMax-xMin+7)*Math.max(0,yMax-yMin+7)*Math.max(0,zMax-zMin+7);
if(v3!=V3)
return false;
//二つに含まれる領域
xMin = MathFunction.max(a1,a2);
xMax = MathFunction.min(a1,a2);
yMin = MathFunction.max(b1,b2);
yMax = MathFunction.min(b1,b2);
zMin = MathFunction.max(c1,c2);
zMax = MathFunction.min(c1,c2);
int v2 = Math.max(0,xMax-xMin+7)*Math.max(0,yMax-yMin+7)*Math.max(0,zMax-zMin+7);
xMin = MathFunction.max(a1,a3);
xMax = MathFunction.min(a1,a3);
yMin = MathFunction.max(b1,b3);
yMax = MathFunction.min(b1,b3);
zMin = MathFunction.max(c1,c3);
zMax = MathFunction.min(c1,c3);
v2 += Math.max(0,xMax-xMin+7)*Math.max(0,yMax-yMin+7)*Math.max(0,zMax-zMin+7);
xMin = MathFunction.max(a2,a3);
xMax = MathFunction.min(a2,a3);
yMin = MathFunction.max(b2,b3);
yMax = MathFunction.min(b2,b3);
zMin = MathFunction.max(c2,c3);
zMax = MathFunction.min(c2,c3);
v2 += Math.max(0,xMax-xMin+7)*Math.max(0,yMax-yMin+7)*Math.max(0,zMax-zMin+7);
v2 -= v3*3;
//V2もV3も一致していればV1も一致しているはずなので判定はV2までで良い
return v2==V2;
}
}
負の範囲も探索しないといけないことに気付かなくてよくわからないままWA出したりAC出したりしました()。
F - Second Largest Query
問題文はこちら
ある区間の最大値と個数、次に大きい値と個数を保持していれば区間同士を連結したときのこれらの値も高速に求めることができるので、セグメント木を用いて各区間の値を保持し、各クエリを処理しました。
F.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、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//セグ木に載せる用のクラス
class Node{
int max1,max2;
int sum1,sum2;
Node(int m1,int m2,int s1,int s2){
max1 = m1;
max2 = m2;
sum1 = s1;
sum2 = s2;
}
}
//セグ木の構築
Node[] A = new Node[N];
for(int i=0;i<N;i++)
A[i] = new Node(sc.nextInt(),0,1,0);
SegmentTree<Node> segT = new SegmentTree<>(A,new Node(0,0,0,0),true){
TreeMap<Integer,Integer> map;
public Node function(Node a,Node b){
if(map==null)
map = new TreeMap<>();
map.clear();
map.put(-1,0);
map.merge(a.max1,a.sum1,Integer::sum);
map.merge(a.max2,a.sum2,Integer::sum);
map.merge(b.max1,b.sum1,Integer::sum);
map.merge(b.max2,b.sum2,Integer::sum);
Entry<Integer,Integer> e1 = map.pollLastEntry();
Entry<Integer,Integer> e2 = map.pollLastEntry();
return new Node(e1.getKey(),e2.getKey(),e1.getValue(),e2.getValue());
}
};
//各クエリを処理する
while(Q-->0){
int t = sc.nextInt();
if(t==1){
int p = sc.nextInt();
int x = sc.nextInt();
segT.update(p,new Node(x,0,1,0));
}
else{
int l = sc.nextInt();
int r = sc.nextInt();
out.println(segT.query(l,r).sum2);
}
}
out.close();
}
}
Eで悩み続けてた時にこっちに移る判断ができて良かったです。
G - Compress Strings
問題文はこちら
公式解説の通りです。
そんなに個数は多くないのでArrayListで最初$S$を保持し、他の文字列が自身を包含していたらremoveメソッドで削除しています。
部分一致の長さはRollingHashを用いて求めています。
G.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の受け取り
int N = sc.nextInt();
//Sの受け取り(包含している文字列の削除)
ArrayList<RollingHash> rh = new ArrayList<>();
for(int i=0;i<N;i++)
rh.add(new RollingHash(sc.next()));
Collections.sort(rh,(a,b)->Integer.compare(b.length(),a.length()));
for(int i=0;i<rh.size();i++)
for(int j=rh.size()-1;j>i;j--)
if(rh.get(i).contains(rh.get(j)))
rh.remove(j);
RollingHash[] S = rh.toArray(new RollingHash[rh.size()]);
N = S.length;
//一致している長さを記録
int[][] max = new int[N][N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
for(int k=1;k<=Math.min(S[i].length(),S[j].length());k++)
if(S[i].equals(S[j],S[i].length()-k,S[i].length(),0,k))
max[i][j] = k;
}
}
//巡回セールスマン問題に帰着して解く(bitDP)
int[][] dp = new int[1<<N][N];
for(int i=0;i<1<<N;i++)
Arrays.fill(dp[i],Integer.MAX_VALUE>>1);
for(int i=0;i<N;i++)
dp[1<<i][i] = S[i].length();
for(int i=1;i<1<<N;i++)
for(int j=0;j<N;j++)
if((i&(1<<j))>0)
for(int k=0;k<N;k++)
if((i&(1<<k))==0)
dp[i|(1<<k)][k] = Math.min(dp[i|(1<<k)][k],dp[i][j]+S[k].length()-max[j][k]);
//答えを求める
int ans = Integer.MAX_VALUE;
for(int i=0;i<N;i++)
ans = Math.min(ans,dp[(1<<N)-1][i]);
//答えの出力
out.println(ans);
out.close();
}
}
いやぁ…気づけなかった…無念…。
感想
A,B,C,D:易しい
E:めちゃめちゃ悩んだし大量にペナを生み出してしまった…。
F:Fにしては易しめ？
G:何も思いつかなかった…
って感じでした。
久々にHighest更新できました。
このままレートを伸ばせていけたら良いが…。