はじめに
今回はコンテストに出ていませんがFまでは解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Tomorrow
問題文はこちら
$d$に$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){
//M、D、y、m、dの受け取り
int M = sc.nextInt();
int D = sc.nextInt();
int y = sc.nextInt();
int m = sc.nextInt();
int d = sc.nextInt();
//一日進める
d++;
//もしD日を超えてしまっていたなら翌月の1日に
if(D<d){
m++;
d = 1;
}
//もしM月を超えてしまっていたなら翌年の1月に
if(M<m){
y++;
m = 1;
}
//答えの出力
out.printf("%d %d %d\n",y,m,d);
out.close();
}
}
B - Buy One Carton of Milk
問題文はこちら
ダイクストラ法の要領で解きました。
PriorityQueueで今の候補を管理するようにして、今見ている中で購入金額が一番小さいものを取り出し、それぞれのパックを購入した時の状態を再度PriorityQueueにaddしていくと、最も金額が小さく目的の個数購入できる状態を取り出すことができます。
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、S、M、Lの受け取り
int N = sc.nextInt();
int S = sc.nextInt();
int M = sc.nextInt();
int L = sc.nextInt();
//ダイクストラ法
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->Integer.compare(a[0],b[0]));
//初期値代入([0]が値段、[1]が個数)
queue.add(new int[]{0,0});
//実質while(true)
while(queue.size()>0){
int[] now = queue.poll();
//もし個数がN個を超えていたらこれが答えなので値段を出力して終了
if(N<=now[1]){
out.println(now[0]);
break;
}
//今の状態で各パックを購入した時の状態を再度add
queue.add(new int[]{now[0]+S,now[1]+6});
queue.add(new int[]{now[0]+M,now[1]+8});
queue.add(new int[]{now[0]+L,now[1]+12});
}
out.close();
}
}
なんか、3重forで全探索するのが全然見えませんでした…。
C - Sum of Numbers Greater Than Me
問題文はこちら
TreeSetで$A$の重複を省いたものを昇順で構築し、二分探索して$A_i$がどこに位置するかを求めながらBinary Indexed Tree(Fenwick Tree)でで累積和を構築し、答えを求めました。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//重複を削除して昇順に並べ替え
TreeSet<Integer> set = new TreeSet<>();
for(int num:A)
set.add(num);
int[] array = new int[set.size()];
for(int i=0;i<array.length;i++)
array[i] = set.pollFirst();
//BITで累積和を構築
BIT bit = new BIT(array.length);
for(int num:A)
bit.add(Searcher.upSearch(array,num)+1,num);
//A_iの答えを求めて出力
long[] ans = new long[N];
for(int i=0;i<N;i++)
ans[i] = bit.sum(array.length)-bit.sum(Searcher.upSearch(array,A[i])+1);
out.println(ans);
out.close();
}
}
CでBIT使うのは何だかオーバーキルみたいな気がするなぁって思って公式解説読みましたが、たしかに、動的に総和を調整しながら求めれば楽でしたね…。
D - Tile Pattern
問題文はこちら
区切り方は公式解説を参照してもらった方が早いので省略しますが、9分割してそれぞれがどれだけ含まれているかを求めることで答えを求めました。
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、Q、Sの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
char[][] S = sc.nextCharArray(N);
//累積和の構築
int[][] sum = new int[N+1][N+1];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
sum[i+1][j+1] = sum[i+1][j]+sum[i][j+1]-sum[i][j];
if(S[i][j]=='B')
sum[i+1][j+1]++;
}
}
//クエリの処理
while(Q-->0){
//A、B、C、Dの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
int D = sc.nextInt();
//左上
long sum1 = sum(sum,A%N,B%N,N,N);
//上
long sum2 = sum(sum,A%N,0,N,N);
//右上
long sum3 = sum(sum,A%N,0,N,D%N+1);
//左
long sum4 = sum(sum,0,B%N,N,N);
//右
long sum5 = sum(sum,0,0,N,D%N+1);
//左下
long sum6 = sum(sum,0,B%N,C%N+1,N);
//下
long sum7 = sum(sum,0,0,C%N+1,N);
//右下
long sum8 = sum(sum,0,0,C%N+1,D%N+1);
//中央
long sum9 = sum(sum,0,0,N,N);
//総和を求める
long ans = sum1+sum3+sum6+sum8;
ans += (C/N-A/N-1)*sum9*(D/N-B/N-1);
ans += (D/N-B/N-1)*(sum2+sum7);
ans += (C/N-A/N-1)*(sum4+sum5);
//出力
out.println(ans);
}
out.close();
}
//累積和から指定された区間の総和を求めるメソッド
private static int sum(int[][] sum,int x1,int y1,int x2,int y2){
return sum[x2][y2]-sum[x1][y2]-sum[x2][y1]+sum[x1][y1];
}
}
めっちゃ汚くなっちゃった…。
E - Set Meal
問題文はこちら
$A_i$との組み合わせで最高額になるのは、食べ合わせが悪い組み合わせを除いて最高額の$B_j$との組み合わせです。したがって各$i$について、$A_i$との最高額となる組み合わせを求めてあげれば、その高々$N$個($A_i$に対して全$B_j$が悪い組み合わせの場合もあるので)の候補の中に求めたい最高額のものが含まれるはずです。これを求めてあげれば良いです。
なお、$B$をソートしておけば$O(N+L)$で求められるので十分高速に処理できます。これは、$B$を降順で見たときに悪い組み合わせを避けるようにずらして見ていくことを考えるとずらす回数の総数が高々$L$回であることからも理解できるかと思います。
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、L、a、bの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int L = sc.nextInt();
int[] a = sc.nextInt(N);
int[][] b = new int[M][2];
for(int i=0;i<M;i++){
b[i][0] = sc.nextInt();
b[i][1] = i+1; //インデックスをペアで持たせる
}
//ソートしておく
Arrays.sort(b,(s,t)->Integer.compare(s[0],t[0]));
//悪い組み合わせをsetで持っておく
HashSet<Point> set = new HashSet<>();
while(L-->0)
set.add(sc.nextPoint());
/最高額記録用変数
int ans = 0;
//Aを固定して見ていく
for(int i=0;i<N;i++){
//悪い組み合わせでない最高額のBを探す
int index = M-1;
while(0<=index&&set.contains(new Point(i+1,b[index][1])))
index--;
//全部悪い組み合わせでなければ候補として扱う
if(0<=index)
ans = Math.max(ans,a[i]+b[index][0]);
}
//答えの出力
out.println(ans);
out.close();
}
}
これはすぐに思いつきました。
F - Palindrome Query
問題文はこちら
回文であることを判定するには反転しても一致するかを見れば良いので、文字列$S$と反転した文字列$T$について、$S$の$[l,r]$と$T$の$[N-r+1,N-l+1]$が一致しているかを高速に処理できれば良いかなと思ったのでRollingHashを使って解きました。
動的に変化させるRollingHashをライブラリには持っていなかったのでBinary Indexed Tree(Fenwick Tree)を使ってそれっぽく処理させるようにして解きました。
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);
//RollingHash用
private static final long MASK30 = (1L<<30)-1;
private static final long MASK31 = (1L<<31)-1;
private static final long MOD = (1L<<61)-1;
private static final long MASK61 = MOD;
public static void main(String[] args){
//baseはテキトーに123にしちゃった
//N、Qの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
//MODを取るBITをSとreverse(S)で構築
BIT_MOD bit = new BIT_MOD(N);
BIT_MOD rBit = new BIT_MOD(N);
char[] S = sc.nextCharArray();
for(int i=0;i<N;i++){
bit.add(i+1,multiply(S[i]-'a'+1,modPow(123,N-i-1)));
rBit.add(N-i,multiply(S[i]-'a'+1,modPow(123,i)));
}
//予め逆元を取っておく
long div = modPow(123,MOD-2);
while(Q-->0){
//クエリの種類の受け取り
int t = sc.nextInt();
if(t==1){
//cで更新する
int x = sc.nextInt();
char c = sc.nextChar();
bit.add(x,multiply(c-S[x-1],modPow(123,N-x)));
rBit.add(N-x+1,multiply(c-S[x-1],modPow(123,x-1)));
S[x-1] = c;
}
else{
//ハッシュ値で比較
int L = sc.nextInt();
int R = sc.nextInt();
long A = multiply((bit.sum(R)-bit.sum(L-1)+MOD)%MOD,modPow(div,N-R));
long B = multiply((rBit.sum(N-L+1)-rBit.sum(N-R)+MOD)%MOD,modPow(div,L-1));
out.println(A==B?"Yes":"No");
}
}
out.close();
}
//a^b mod 2^61-1
private static long modPow(long a,long b){
long ans = 1;
while(b>0){
if((b&1)==1)
ans = multiply(ans,a);
a = multiply(a,a);
b >>= 1;
}
return ans;
}
// a*b mod 2^61-1
private static long multiply(final long a,final long b){
final long au = a>>31;
final long ad = a&MASK31;
final long bu = b>>31;
final long bd = b&MASK31;
final long mid = ad*bu+au*bd;
final long midu = mid>>30;
final long midd = mid&MASK30;
return mod(au*bu*2+midu+(midd<<31)+ad*bd);
}
// x mod 2^61
private static long mod(final long x){
final long xu = x>>61;
final long xd = x&MASK61;
long ans = xu+xd;
if(MOD<=ans){
ans -= MOD;
}
return ans;
}
}
//MODを取るBIT
final class BIT_MOD{
final int size;
final private long[] tree;
final private long MOD = (1L<<61)-1;
public BIT_MOD(int n){
size = n;
tree = new long[n+1];
}
public long sum(int i){
long sum = 0;
while(i>0){
sum += tree[i];
sum %= MOD;
i ^= i&(-i);
}
return sum;
}
public void add(int i,long x){
if(x<0)
x += MOD;
while(i<=size){
tree[i] += x;
tree[i] %= MOD;
i += i&(-i);
}
}
}
かなり重いですね…。もっとサクッと実装できる実装力が欲しいものです。
感想
A,B,C:ほんのりめんどくさいが易しい方
D:気づけるかがキーになってくる問題っぽい
E:思ったよりサクッと気づけたのできっと易しい方
F:RollingHash自体はすぐ気づいたので実装力次第
って感じでした。
緑以下コンに行っていたので出れませんでしたが、出てもあんまり良い成績とれるような回ではなかった気がするのでまぁ、結果オーライ…？