はじめに
今回はFまで解けたので提出コードをそのまま載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Counting Passes
問題文はこちら
普通にfor文で受け取りながらL以上ならインクリメントする方針で解きました。
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、Lの受け取り
int N = sc.nextInt();
int L = sc.nextInt();
//数え上げ
int ans = 0;
while(N-->0)
if(sc.nextInt()>=L)
ans++;
//答えの出力
out.println(ans);
out.close();
}
}
B - Minimize Abs 1
問題文はこちら
問題文の式を考えてみると、$X_i = \min(R,\max(L,A_i))$であることがわかるので、それを求めました。
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、L、R、Aの受け取り
int N = sc.nextInt();
int L = sc.nextInt();
int R = sc.nextInt();
int[] A = sc.nextInt(N);
//答えの構築
int[] ans = new int[N];
for(int i=0;i<N;i++){
if(A[i]<L)
ans[i] = L;
else if(R<A[i])
ans[i] = R;
else
ans[i] = A[i];
}
//答えの出力
out.println(ans);
out.close();
}
}
Java21からはMath::clampを使えるので、言語アップデートを待ちましょう。
C - Minimize Abs 2
問題文はこちら
$x$は$\sqrt{D}$まで試せば良いと思ったので、その範囲で全探索しました。
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){
//Dの受け取り
long D = sc.nextLong();
//全探索
long ans = D;
for(long x=0;x*x*2<=D;x++){
long y = (int)Math.sqrt(D-x*x);
ans = Math.min(ans,Math.abs(D-x*x-y*y));
y++;
ans = Math.min(ans,Math.abs(D-x*x-y*y));
}
//答えの出力
out.println(ans);
out.close();
}
}
D - Counting Ls
問題文はこちら
問題文の条件を満たす三つ組のマスはL字型になると思ったので、予め各行、列のoの数を数えておき、L字のちょうど曲がり角の部分のマスを全探索すれば重複無く探索できるかなと考え、それを実装しました。
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、Sの受け取り
int N = sc.nextInt();
char[][] S = sc.nextCharArray(N);
//各行、列のoの数を数える
int[] countI = new int[N];
int[] countJ = new int[N];
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(S[i][j]=='o'){
countI[i]++;
countJ[j]++;
}
}
}
//数え上げ
long ans = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if(S[i][j]=='o'){
//自分以外で数えたいので-1してる
ans += (countI[i]-1)*(countJ[j]-1);
}
}
}
//答えの出力
out.println(ans);
out.close();
}
}
気付けば特に悩まないですね。
E - Mex and Update
問題文はこちら
$A$に含まれていない値をTreeSetで管理することでこの問題を解きました。
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、Q、Aの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
int[] A = sc.nextInt(N);
//Map代わり
int[] count = new int[N+1];
for(int num:A)
if(num<N)
count[num]++;
//Set(Mex候補)
TreeSet<Integer> set = new TreeSet<>();
for(int i=0;i<=N;i++)
if(count[i]==0)
set.add(i);
//クエリの処理
while(Q-->0){
//i、xの受け取り
int i = sc.nextInt()-1;
int x = sc.nextInt();
//Mex候補になるか確認
if(A[i]<N)
if(--count[A[i]]==0)
set.add(A[i]);
A[i] = x;
//Mex候補から外れるか確認
if(A[i]<N)
if(count[A[i]]++==0)
set.remove(A[i]);
//mexの出力
out.println(set.first());
}
out.close();
}
}
最初NをSetに入れるのを忘れてしまって2回もペナルティを頂いてしまいました…。
F - Minimize Bounding Square
問題文はこちら
$X$座標と$Y$座標の話は独立に考えて良いため、$X$座標に関してのみ最初は書きます。
ある非負整数$M$について、$X$座標と平行な辺の長さを$M$にするために必要なコストは左右から、移動する点の少ない方を貪欲に動かす手法を用いれば$O(N)$で答えが出せるので、辺の長さを$i$にするコストは$K$以下か？という判定問題に落とし込め、これは決め打ち二分探索を用いることで最小の長さを求めることができます。あとは、$X$座標と$Y$座標を同時に処理することで本問題を解きました。
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、K、X、Yの受け取り
int N = sc.nextInt();
long K = sc.nextLong();
int[] X = new int[N];
int[] Y = new int[N];
for(int i=0;i<N;i++){
X[i] = sc.nextInt();
Y[i] = sc.nextInt();
}
//ソートしても大丈夫なのでソートしておく
Arrays.sort(X);
Arrays.sort(Y);
//二分探索(ラムダ式の中が判定関数)
int ans = Searcher.overSearch(0,(int)1e9,0,(int i)->{
long sum = 0;
//X座標と平行な辺をi以下にする
int xL = X[0];
int xR = X[N-1];
int countXL = 1;
int countXR = 1;
while(i<xR-xL){
if(countXL<countXR){
if(xR-X[countXL]<i)
sum += (long)countXL*(xR-xL-i);
else
sum += (long)countXL*(X[countXL]-X[countXL-1]);
xL = X[countXL++];
}
else{
if(X[N-countXR-1]-xL<i)
sum += (long)countXR*(xR-xL-i);
else
sum += (long)countXR*(X[N-countXR]-X[N-countXR-1]);
xR = X[N-(++countXR)];
}
}
//Y座標と平行な辺をi以下にする
int yL = Y[0];
int yR = Y[N-1];
int countYL = 1;
int countYR = 1;
while(i<yR-yL){
if(countYL<countYR){
if(yR-Y[countYL]<i)
sum += (long)countYL*(yR-yL-i);
else
sum += (long)countYL*(Y[countYL]-Y[countYL-1]);
yL = Y[countYL++];
}
else{
if(Y[N-countYR-1]-yL<i)
sum += (long)countYR*(yR-yL-i);
else
sum += (long)countYR*(Y[N-countYR]-Y[N-countYR-1]);
yR = Y[N-(++countYR)];
}
}
//かかったコストがK以下なら1、Kを超えるなら0
return sum>K?0:1;
});
//答えの出力
out.println(ans);
out.close();
}
}
かなり悩んでしまいましたが時間内に解けて良かったです。
感想
A,B,C,D:易しめ
E:Eにしてはかなり易しいかも？
F:結構悩んじゃった…
って感じでした。
ペナを減らせるようちゃんと注意を払わないと、ですねぇ…。