はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - Print 341
問題文はこちら
制約から101010...0101みたいな感じになると予想できて、最初の1を除けば01を$N$回繰り返せば良いので、そのように実装しました。
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){
//Nの受け取り
int N = sc.nextInt();
//答えの構築
out.print(1);
for(int i=0;i<N;i++)
out.print("01");
out.println();
out.close();
}
}
B - Foreign Exchange
問題文はこちら
国$1$から貪欲に交換した方が得なので、そのように実装しました。
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、Aの受け取り
int N = sc.nextInt();
long[] A = sc.nextLong(N);
//貪欲に変換
for(int i=0;i<N-1;i++){
int S = sc.nextInt();
int T = sc.nextInt();
A[i+1] += A[i]/S*T;
}
//答えの出力
out.println(A[N-1]);
out.close();
}
}
C - Takahashi Gets Lost
問題文はこちら
制約がそんなに大きくないので、全マスについて不時着したときに条件を満たすように移動できるかシミュレーションすることで解きました。
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){
//H、W、N、T、Sの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int N = sc.nextInt();
char[] T = sc.nextCharArray();
char[][] S = sc.nextCharArray(H);
//答えを記録する用
HashSet<Point> set = new HashSet<>();
//全始点シミュレーション
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='#')
continue;
Point p = move(i,j,T,S);
if(p!=null)
set.add(p);
}
}
//答えの出力
out.println(set.size());
out.close();
}
//シミュレーション用メソッド
private static Point move(int x,int y,char[] T,char[][] S){
for(char c:T){
switch(c){
case 'U' -> x--;
case 'D' -> x++;
case 'L' -> y--;
case 'R' -> y++;
}
if(S[x][y]=='#')
return null;
}
return new Point(x,y);
}
}
D - Only one of two
問題文はこちら
正整数$A$に対して、$1$から$A$までの整数で正整数$B$で割り切れる数は$\lfloor \frac{A}{B} \rfloor$個あるので、$1$から$A$までで$N$か$M$のどちらかで割り切れる個数は包除原理から$\lfloor \frac{A}{N} \rfloor + \lfloor \frac{A}{M} \rfloor - \lfloor \frac{A}{\mathrm{lcm}(N,M)} \rfloor$個と求まります。ここで、問題文では一方のみで割り切れることを考えているので、どちらでも割れる$\lfloor \frac{A}{\mathrm{lcm}(N,M)} \rfloor$個を引いてあげれば問題文の条件を満たす整数の個数が求まります。
以上から、この判定問題は$O(1)$で行なえ、二分探索と組み合わせることで目的の値を求めることができます。
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、Kの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
long K = sc.nextLong();
//二分探索
long a = 1;
long b = Long.MAX_VALUE>>1;
long ans = b;
long L = MathFunction.lcm(N,M);
while(a-b<1){
long c = a+b>>1;
if(c/N+c/M-c/L*2>=K) //K個以上あるかで分岐
b = (ans=c)-1;
else
a = c+1;
}
//答えの出力
out.println(ans);
out.close();
}
}
コンテスト中はぐっちゃぐちゃなコードを書いてしまってめちゃくちゃ悩んでしまいました…。
E - Alternating String
問題文はこちら
前後の文字とこの区間が良い文字列かを保持したクラスを作って、これを遅延セグメント木に載せることで解きました。
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);
//遅延セグ木に載せる用のクラス
private static class Node{
boolean isGood;
int head,tail;
Node(boolean ig,int h,int t){
isGood = ig;
head = h;
tail = t;
}
}
public static void main(String[] args){
//N、Q、Sの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
char[] S = sc.nextCharArray();
//遅延セグ木の構築
Node[] table = new Node[N];
for(int i=0;i<N;i++){
int subS = S[i]=='0'?0:1;
table[i] = new Node(true,subS,subS);
}
LazySegmentTree<Node,Integer> lSegT = new LazySegmentTree<>(table,new Node(true,-1,-1),0,true){
public Node mapping(Node n,Integer num){
n.head ^= num;
n.tail ^= num;
return n;
}
public Node function(Node a,Node b){
return new Node(
a.isGood && b.isGood && a.tail!=b.head,
a.head,
b.tail);
}
public Integer composition(Integer a,Integer b){
return a^b;
}
};
//クエリ処理
while(Q-->0){
int t = sc.nextInt();
int L = sc.nextInt();
int R = sc.nextInt();
if(t==1){
lSegT.apply(L,R+1,1);
}
else{
out.println(lSegT.query(L,R+1).isGood?"Yes":"No");
}
}
out.close();
}
}
F - Breakdown
問題文はこちら
公式解説のものを実装しました。
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、M、辺の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[][] pathes = sc.nextInt(M,2);
//1-indexedでW、Aの受け取り(他と統一したかったので)
int[] W = new int[N+1];
for(int i=1;i<=N;i++)
W[i] = sc.nextInt();
int[] A = new int[N+1];
for(int i=1;i<=N;i++)
A[i] = sc.nextInt();
//移動できる方向にのみ移動するようにした隣接リストの構築
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
for(int[] p:pathes){
if(W[p[1]]<W[p[0]])
list.get(p[0]).add(p[1]);
if(W[p[0]]<W[p[1]])
list.get(p[1]).add(p[0]);
}
//数値を昇順になるように並べ替え
PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->Integer.compare(W[a],W[b]));
for(int i=1;i<=N;i++)
queue.add(i);
int[] index = new int[N+1];
int[] id = new int[N+1];
for(int i=1;i<=N;i++){
int num = queue.poll();
index[i] = num;
id[num] = i;
}
//昇順にDPを処理していく
long[] dp = new long[N+1];
for(int i=1;i<=N;i++){
long[] table = new long[W[index[i]]];
for(int prev:list.get(index[i]))
for(int j=W[index[i]]-1;j>=W[prev];j--)
table[j] = Math.max(table[j],table[j-W[prev]]+dp[id[prev]]);
dp[i] = table[W[index[i]]-1]+1;
}
//各コマに対する答えを数え上げ
long ans = 0;
for(int i=1;i<=N;i++)
ans += dp[id[i]]*A[i];
//答えの出力
out.println(ans);
out.close();
}
}
実装ミスってバグり散らかしてたらコンテスト終わってた…実装力さん…。
感想
A,B,C:易しい
D:回りくどい実装を本番でしてしまった…
E:解説見たら確かに…つい楽をしてしまった…
F:DPでできそう、までは進んだけど実装できなかった…
って感じでした。
なんかなぁ…もう一歩解きたいよねぇ…。