はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでそれを載せようと思います。
では、見ていきましょう。
A - Cyclic
問題文はこちら
$100b + 10c + a$と$100c + 10a + b$を出力するよう求められているので、$100b + 10c$はN%100*10、$a$はN/100、$100c$はN%10*100、$10a + b$はN/10で作れるのでこれを用いて解きました。
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){
int N = sc.nextInt();
out.println((N%100*10+(N/100))+" "+(N%10*100+(N/10)));
out.close();
}
}
B - Strawberries
問題文はこちら
左右どっちかから貪欲に使うのが最適なので、左から連続している丈夫な歯を数えて$K$に達したらその歯を使ってイチゴを食べてみる、というシミュレーションで数え上げました。
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){
int N = sc.nextInt();
int K = sc.nextInt();
String S = sc.next();
int count = 0;
int ans = 0;
for(int i=0;i<N;i++){
if(S.charAt(i)=='O'){
if(++count==K){
ans++;
count = 0;
}
}
else{
count = 0;
}
}
out.println(ans);
out.close();
}
}
C - Sowing Stones
問題文はこちら
先頭から、今見ているマスにある石が$K$個なら$K-1$個を次のマスに移す、を繰り返せば良いので、これは今$2$個以上石があるマスで一番末尾のマスの石を石の無いマスに末尾から貪欲に置くことと同義なのでこれを実装しました。
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){
int N = sc.nextInt();
int M = sc.nextInt();
int[][] XA = new int[M][2];
for(int i=0;i<M;i++)
XA[i][0] = sc.nextInt();
for(int i=0;i<M;i++)
XA[i][1] = sc.nextInt();
Arrays.sort(XA,Arrays::compare);
if(XA[0][0]>1){
out.println(-1);
}
else{
long now = N;
long ans = 0;
for(int i=M-1;i>=0;i--){
long dist = now-XA[i][0];
if(dist>0){
if(XA[i][1]<=dist){
ans += dist*(dist+1)>>1;
ans -= (dist-XA[i][1])*(dist-XA[i][1]+1)>>1;
now -= XA[i][1];
}
else if(XA[i][1]>dist+1){
System.out.println(-1);
return;
}
else{
ans += dist*(dist+1)>>1;
now = XA[i][0]-1;
}
}
else
now--;
}
if(now>0){
out.println(-1);
}
else{
out.println(ans);
}
}
out.close();
}
}
D - Home Garden
問題文はこちら
情報としては植えた日付と今の日付さえわかっていればよいです。
したがって、PriorityQueueに植えた日付を、今の日付を別途long型変数などで持っておけば本問題を解くことができます。
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){
int Q = sc.nextInt();
PriorityQueue<Long> queue = new PriorityQueue<>();
long now = 0;
while(Q-->0){
int t = sc.nextInt();
if(t==1){
queue.add(now);
}
if(t==2){
int T = sc.nextInt();
now += T;
}
if(t==3){
int H = sc.nextInt();
long num = now-H;
int ans = 0;
while(queue.size()>0&&queue.peek()<=num){
queue.poll();
ans++;
}
out.println(ans);
}
}
out.close();
}
}
E - Sum of All Substrings
問題文はこちら
そのままを考えようとするととても実行時間には間に合わなそうなので、各桁の"寄与"について考えてみたいと思います。
例えば、最上位の桁の値は$i=1$のときのみで、今の位から1の位まで1回ずつ加算されるのはわかると思います(各$j$($1 \le j \le N$)において、最上位の桁の値は下から$j$番目の位に加算されるはずなので)。
これを全桁考えていくと、下から$s(1 \le s \le N)$桁目には上から$t(1 \le t \le N-s+1)$桁目の値が$t$回ずつ加算されているのではないかと見えてきます。
あとは下から一桁ずつこの加算した結果を元に繰り上がりを適切に処理すれば解が高速に求まります。
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){
int N = sc.nextInt();
char[] S = sc.nextCharArray();
ArrayDeque<Long> deq = new ArrayDeque<>();
long sum = 0;
for(int i=0;i<N;i++)
sum += (S[i]-'0')*(i+1);
long temp = 0;
for(int i=N-1;i>=0;i--){
temp += sum;
deq.add(temp%10);
temp /= 10;
sum -= (S[i]-'0')*(i+1);
}
StringBuilder ans = new StringBuilder();
if(temp>0)
ans.append(temp);
while(deq.size()>0)
ans.append(deq.pollLast());
out.println(ans.toString());
out.close();
}
}
F - Buildings 2
問題文はこちら
問題文を言い換えることを考えます。
要は$\max_{l \le i < x}H_i<H_x$が成り立つ$x(r<x \le N)$の個数が知れればよく、$H_{x_i}<H_{x_{i+1}}$が成り立つので、これは$\max_{l \le i \le r}H_i$を初項として、自分より大きい値を貪欲に選ぶ最長増加部分列問題(LIS)チックな数列の長さを$K$としたとき、$K-1$を求めよという問題に言い換えられると思います。
しかし、都度LISライクな数列の長さを求めていては実行時間超過をしてしまうので、$H$が大きい順に「TreeSet内で自分より大きい、最も小さいインデックスを探し、そこと連結したときの長さを記録し、TreeSetに自分のインデックスを追加する」という操作をします。すると、結果的に各要素を始点としたときのLISライクな数列の長さが全体$O(N \log N)$時間で解けます。
あとはクエリを受け取ってセグメント木などで$\max_{l \le i \le r}H_i$を求め、この値を始点としたLISライクな数列の長さから$1$引いた値を出力すれば良いです。
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){
int N = sc.nextInt();
int Q = sc.nextInt();
int[] H = sc.nextInt(N);
SegmentTree<Integer> segT = new SegmentTree<>(N,0,true){
public Integer function(Integer a,Integer b){
return Math.max(a,b);
}
};
for(int i=0;i<N;i++)
segT.update(i+1,H[i]);
int[] map = new int[N+1];
for(int i=0;i<N;i++)
map[H[i]] = i;
TreeSet<Integer> set = new TreeSet<>();
int[] next = new int[N];
int[] sum = new int[N];
for(int i=N;i>0;i--){
if(set.size()==0||set.ceiling(map[i])==null){
sum[map[i]] = 1;
next[map[i]] = -1;
}
else{
int index = set.ceiling(map[i]);
sum[map[i]] = sum[index]+1;
next[map[i]] = index;
}
set.add(map[i]);
}
while(Q-->0){
int l = sc.nextInt();
int r = sc.nextInt();
int max = segT.query(l+1,r);
out.println(map[max]<0?0:sum[map[max]]-1);
}
out.close();
}
}
実装しきれなかった…。
感想
A,B:易しい
C:実装に手間取った…
D:易しめ？
E:気づいたときめちゃんこ嬉しかった
F:実装し切りたかったなぁ
って感じでした。
Fが解けなかったが故の大敗北…レートが…。