はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでそれらを載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - Arithmetic Progression
問題文はこちら
$A$が$B$になるまでループを回しながら$D$だけ加算していけば目的の数列を構築できます。
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、Dの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
int D = sc.nextInt();
//Bになるまでループ
for(;A!=B;A+=D)
out.print(A+" ");
//最後は空白じゃなくて改行
out.println(B);
out.close();
}
}
B - Append
問題文はこちら
動的に要素を追加したいのでArrayList<Integer>で処理しました。
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){
//Qの受け取り
int Q = sc.nextInt();
ArrayList<Integer> A = new ArrayList<>();
//問題文通りに処理
while(Q-->0){
int t = sc.nextInt();
if(t==1)
A.add(sc.nextInt());
else
out.println(A.get(A.size()-sc.nextInt()));
}
out.close();
}
}
C - Divide and Divide
問題文はこちら
一番大きい値を貪欲に選んでいくことを考えると、値をkey、個数をvalueとしたTreeMap<Long,Long>で処理できると考え、これで実装しました。
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();
//Mapで黒板に書いてある値を管理
TreeMap<Long,Long> map = new TreeMap<>();
long ans = 0;
map.put(N,1L);
//操作できなくなるまで回す
while(map.size()>0){
Map.Entry<Long,Long> entry = map.pollLastEntry();
long key = entry.getKey();
long val = entry.getValue();
if(key>1){ //操作できるなら次の値を書き込む
ans += key*val;
map.merge(key/2,val,Long::sum);
map.merge((key+1)/2,val,Long::sum);
}
}
//答えの出力
out.println(ans);
out.close();
}
}
D - Super Takahashi Bros.
問題文はこちら
ダイクストラ法で解ける見た目なので(単一頂点からの最短経路問題なので)、それで解きました。
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の受け取り
int N = sc.nextInt();
//隣接行列の構築
ArrayList<ArrayList<int[]>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
for(int i=1;i<N;i++){
int A = sc.nextInt();
int B = sc.nextInt();
int X = sc.nextInt();
list.get(i).add(new int[]{i+1,A});
list.get(i).add(new int[]{X,B});
}
//Queueに乗せるようのクラス
class Node{
int now;
long val;
public Node(int n,long v){
now = n;
val = v;
}
}
//初期値設定
PriorityQueue<Node> queue = new PriorityQueue<>((a,b)->Long.compare(a.val,b.val));
queue.add(new Node(1,0));
long[] cost = new long[N+1];
Arrays.fill(cost,Long.MAX_VALUE);
cost[1] = 0;
//ダイクストラ
while(queue.size()>0){
Node node = queue.poll();
if(node.val==cost[node.now]){
for(int[] path:list.get(node.now)){
if(cost[node.now]+path[1]<cost[path[0]]){
cost[path[0]] = cost[node.now]+path[1];
queue.add(new Node(path[0],cost[path[0]]));
}
}
}
}
//答えの出力
out.println(cost[N]);
out.close();
}
}
E - Mancala 2
問題文はこちら
区間への加算が必要なので遅延セグメントツリーで処理しました。
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、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//セグ木に乗せたかったのでラッパークラスで
Long[] A = new Long[N];
for(int i=0;i<N;i++)
A[i] = sc.nextLong();
//Bの受け取り
int[] B = sc.nextInt(M);
//遅延セグ木
LazySegmentTree<Long,Long> lSegT = new LazySegmentTree<>(A,0L,0L,false){
public Long mapping(Long a,Long b){
return Long.sum(a,b);
}
public Long composition(Long a,Long b){
return Long.sum(a,b);
}
public Long function(Long a,Long b){
return Long.sum(a,b);
}
};
//Bに沿って処理
for(int num:B){
long sum = lSegT.get(num);
lSegT.update(num,0L);
lSegT.apply(0,N,sum/N);
sum %= N;
if(N<sum+num+1)
lSegT.apply(0,(int)sum+num+1-N,1L);
if(num<N)
lSegT.apply(num+1,Math.min(N,num+(int)sum+1),1L);
}
//石の数を求めて配列に
Long[] ans = new Long[N];
for(int i=0;i<N;i++)
ans[i] = lSegT.get(i);
out.println(ans);
out.close();
}
}
定数倍が重いのもあってちょっと実行時間がキツめ…。
F - S = 1
問題文はこちら
証明は公式解説に任せますが、拡張ユークリッドの互除法を用いて解きました。
F.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//X、Yの受け取り
long X = sc.nextLong();
long Y = sc.nextLong();
//何となく絶対値で拡張ユークリッド
long[] d = extendedGcd(Math.abs(X),Math.abs(Y));
//最大公約数が2より大きいなら無理
if(d[0]>2){
System.out.println(-1);
return;
}
//値調整
if(d[0]==1){
d[1] *= 2;
d[2] *= 2;
}
if(Long.signum(X)==Long.signum(Y)){
d[1] *= -1;
}
//答えの出力
System.out.println(d[2]+" "+d[1]);
}
//拡張ユークリッドの互除法
//aX+bY=gcd(a,b)を満たすとき、new long[]{gcd(a,b), X, Y}が返ってくる
private static long[] extendedGcd(long a,long b){
if(b==0){
return new long[]{a,1,0};
}
long[] d = extendedGcd(b,a%b);
d[1] -= a/b*d[2];
return new long[]{d[0],d[2],d[1]};
}
}
符号こねくり回してしまって本番中解けなかった…。
感想
A,B,C,D:易しい
E:遅延セグ木はFなイメージが少しあったけど、まぁ別解もあるからEが妥当なのかな
F:うぉぉぉぉぉぉぉぉぉん😭😭😭😭😭😭😭😭😭😭
って感じでした。
ギリギリ青に留まれましたが、次回が…怖い…。