はじめに
今回はDまでとF、コンテスト後にEが解けたのでそれを載せようと思います。
では、見ていきましょう。
A - Daily Cookie
問題文はこちら
今の@の個数を数えて答えを求めました。
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){
int N = sc.nextInt();
int D = sc.nextInt();
int ans = 0;
for(char c:sc.nextCharArray())
if(c=='@')
ans++;
out.println(N-ans+D);
out.close();
}
}
B - Daily Cookie 2
問題文はこちら
愚直にシミュレーションして解きました。
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){
int N = sc.nextInt();
int D = sc.nextInt();
char[] S = sc.nextCharArray();
while(N-->0){
if(S[N]=='@'){
S[N] = '.';
if(--D==0)
break;
}
}
out.println(S);
out.close();
}
}
C - Kaiten Sushi
問題文はこちら
事前に、$A$を先頭から見ていきこれまでで一番小さいならその$A_i$をkeyに、iをvalueに持ったTreeMapを構築し、$B_i$以下のkeyを探すことで解が求まります。
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){
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(M);
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int i=1;i<=N;i++)
if(map.floorKey(A[i-1])==null)
map.put(A[i-1],i);
for(int b:B){
Integer ans = map.floorKey(b);
out.println(ans==null?-1:map.get(ans));
}
out.close();
}
}
D - Keep Distance
問題文はこちら
全部出力しなくちゃいけないことから、無駄なくちゃんと枝切りをして全探索すれば十分間に合うというメタ読みができます。
そこで、差が$10$ピッタリずつで$1$通り以上構築できるなら探索する、という制限でDFSをすることで無駄なく探索しました。
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){
int N = sc.nextInt();
int M = sc.nextInt();
ArrayList<int[]> list = new ArrayList<>();
dfs(0,N,M,new int[N],list);
out.println(list.size());
for(int[] ans:list)
out.println(ans);
out.close();
}
private static void dfs(int now,int N,int M,int[] ans,ArrayList<int[]> list){
if(now==N)
list.add(ans.clone());
else{
for(int i=now>0?ans[now-1]+10:1;i<=M-(N-now-1)*10;i++){
ans[now] = i;
dfs(now+1,N,M,ans,list);
}
}
}
}
E - Expansion Packs
問題文はこちら
公式解説の通りです。
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){
int N = sc.nextInt();
int X = sc.nextInt();
int[] P = sc.nextInt(N);
double[] dp = new double[N+1];
dp[0] = 1.0;
for(int p:P){
for(int i=N;i>0;i--)
dp[i] = (dp[i]*(100-p)+dp[i-1]*p)/100.0;
dp[0] *= (100-p)/100.0;
}
double[] ans = new double[X+1];
for(int i=1;i<=X;i++){
for(int j=1;j<=N;j++)
ans[i] += ans[Math.max(i-j,0)]*dp[j];
ans[i] += 1;
ans[i] /= 1-dp[0];
}
out.println(ans[X]);
out.close();
}
}
F - Falling Bars
問題文はこちら
一番下の位置にあるバーが当然一番下に来るという予想はなんとなくつくと思います。すると、その次に下の位置にあるバーはこの一番下のバーにのみ影響を受けるという予想もつくかと思います。したがって、一番下にあるバーから順に、列の高さを管理した遅延セグメント木でバーが位置するべき高さを求めては高さを更新、を繰り返していくことで解が高速に求まりそうです。
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){
int H = sc.nextInt();
int W = sc.nextInt();
int N = sc.nextInt();
int[][] bars = new int[N][4];
for(int i=0;i<N;i++){
bars[i][0] = sc.nextInt();
bars[i][1] = sc.nextInt();
bars[i][2] = sc.nextInt();
bars[i][3] = i;
}
Arrays.sort(bars,Arrays::compare);
ArrayUtil.reverseRange(bars,0,N);
LazySegmentTree<Integer,Integer> lSegT = new LazySegmentTree<>(W,H+1,H+1,true){
public Integer function(Integer a,Integer b){
return Math.min(a,b);
}
public Integer mapping(Integer a,Integer b){
return Math.min(a,b);
}
public Integer composition(Integer a,Integer b){
return Math.min(a,b);
}
};
int[] ans = new int[N];
for(int[] bar:bars){
int R = bar[0];
int C = bar[1];
int L = bar[2];
int index = bar[3];
int nextR = lSegT.query(C,C+L)-1;
lSegT.apply(C,C+L,nextR);
ans[index] = nextR;
}
out.println(ans,"\n");
out.close();
}
}
感想
A,B:易しい
C,D:この難易度帯にしては易しい？
E:全然解けなかった…苦手…
F:もっと早めにこっちに切り替えればよかった…
って感じでした。
う～ん…全然レートが上がらなくてキツイ…。