はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでFまで載せようと思います。
なお、僕のライブラリは提出結果をご確認ください。
では、見ていきましょう。
A - Christmas Present
問題文はこちら
単に比較して答えを出力しました。
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){
//B、Gの受け取り
int B = sc.nextInt();
int G = sc.nextInt();
//高い方を答える
out.println(B<G?"Glove":"Bat");
out.close();
}
}
B - Christmas Trees
問題文はこちら
$A$基準で考えるために$L$、$R$から$A$を引き、切り捨て除算の都合上$L$が0以上になるように$L$、$R$に$M$の倍数を足して「$L$以上$R$以下に$M$の倍数はいくつありますか？」という問題に変形してやって解きました。
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){
//A、M、L、Rの受け取り
long A = sc.nextLong();
long M = sc.nextLong();
long L = sc.nextLong();
long R = sc.nextLong();
//Aを基準点にするためにずらす
L -= A;
R -= A;
//Lが0以上になるように調整
long sub = Math.max(0,(-L+M)/M);
L += sub*M;
R += sub*M;
//答えの出力
out.println(R/M-(L-1)/M);
out.close();
}
}
C - Socks 2
問題文はこちら
$K$が偶数ならなくした隣り合う二組同士をペアにするのが最適なので、それを求めてあげるとして、$K$が奇数のときは$1$番目、$3$番目、…、$N$番目のいずれかをペアにしないで余らせるのが最適なので、先に$1$番目を残した時の解を求め、$1$番目と$2$番目をペアにする代わりに$2$番目と$3$番目のペアを解消する、という増減を加算してあげることで$3$番目を残した時の解が高速で求められ、これを繰り返すことで$O(N)$で最小値を全探索できます。
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、K、Aの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
int[] A = sc.nextInt(K);
//Kが偶数なら自明なのでサクッと求めて出力
if(K%2==0){
int ans = 0;
for(int i=0;i<K;i+=2)
ans += A[i+1]-A[i];
out.println(ans);
}
//奇数ならスライドする感じで答えを探す
else{
int ans = 0;
for(int i=1;i<K;i+=2)
ans += A[i+1]-A[i];
int now = ans;
for(int i=1;i<K-1;i+=2){
now -= A[i+1]-A[i];
now += A[i]-A[i-1];
ans = Math.min(ans,now);
}
out.println(ans);
}
out.close();
}
}
D - Reindeer and Sleigh
問題文はこちら
$R$はソートしても問題無いのでソート済みとして話します。
より必要な頭数が少ないソリを選んだ方が有利であるのは自明なので、$R$の累積和をkeyに、インデックスをvalueにしたTreeMapを構築してあげることで各クエリはmap.floorEntry(X).getValue()が答えになります。
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、Rの受け取り
int N = sc.nextInt();
int Q = sc.nextInt();
int[] R = sc.nextInt(N);
//上記のTreeMapを構築
TreeMap<Long,Integer> map = new TreeMap<>();
long now = 0;
map.put(now,0);
Arrays.sort(R);
for(int i=0;i<N;i++){
now += R[i];
map.put(now,i+1);
}
//各クエリに答える
while(Q-->0){
long X = sc.nextLong();
out.println(map.floorEntry(X).getValue());
}
out.close();
}
}
E - Christmas Color Grid 1
問題文はこちら
ある赤のマスを緑に変えることを考えると、隣り合う連結成分の分だけ連結成分が増減するので、それを見ていけば各赤マスを選んだ時の連結成分の数がわかるのであとは赤マスの個数の逆元をかけてあげれば答えが出ます。
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){
//H、W、Sの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
char[][] S = sc.nextCharArray(H);
//現在の連結成分の構築
UnionFind uf = new UnionFind(H*W);
int count = 0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='#'){
if(0<i&&S[i-1][j]=='#')
uf.unite(i*W+j,(i-1)*W+j);
if(i+1<H&&S[i+1][j]=='#')
uf.unite(i*W+j,(i+1)*W+j);
if(0<j&&S[i][j-1]=='#')
uf.unite(i*W+j,i*W+j-1);
if(j+1<W&&S[i][j+1]=='#')
uf.unite(i*W+j,i*W+j+1);
}
else
count++;
}
}
long sum = 0;
//赤のマスを緑にしたときの連結成分の個数をsumに加算していく
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='.'){
HashSet<Integer> set = new HashSet<>();
if(0<i&&S[i-1][j]=='#')
set.add(uf.root((i-1)*W+j));
if(i+1<H&&S[i+1][j]=='#')
set.add(uf.root((i+1)*W+j));
if(0<j&&S[i][j-1]=='#')
set.add(uf.root(i*W+j-1));
if(j+1<W&&S[i][j+1]=='#')
set.add(uf.root(i*W+j+1));
sum += uf.groupCount()-set.size()+1-count;
}
}
}
//赤の個数だけ通り数があるので赤の個数で割ってあげる
final int mod = 998244353;
out.println(sum%mod*MathFunction.modPow(count,mod-2,mod)%mod);
out.close();
}
}
F - Christmas Present 2
問題文はこちら
詳しい話は公式解説に任せます。
僕の実装では自作AVL木によるmulti_setで最小値を管理しています。
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、Sと各地点の受け取り
int N = sc.nextInt();
int K = sc.nextInt();
Point S = sc.nextPoint();
Point[] p = new Point[N+1];
p[N] = S;
for(int i=0;i<N;i++)
p[i] = sc.nextPoint();
//解説のdの構築
double[] d = new double[N];
double ans = Math.hypot(p[0].x-S.x,p[0].y-S.y);
for(int i=0;i<N;i++){
d[i] = Math.hypot(p[i].x-S.x,p[i].y-S.y)+Math.hypot(p[i+1].x-S.x,p[i+1].y-S.y)
-Math.hypot(p[i+1].x-p[i].x,p[i+1].y-p[i].y);
ans += Math.hypot(p[i+1].x-p[i].x,p[i+1].y-p[i].y);
}
//区間最小値を求めるためのAVL木
TreeMulti<Double> map = new TreeMulti<>();
map.add(0.0);
//DP
double[] dp = new double[N+1];
for(int i=1;i<=N;i++){
dp[i] = map.first()+d[i-1];
//区間の調整
map.add(dp[i]);
if(K<=i)
map.remove(dp[i-K]);
}
//答えのしゅつりょく
ans += dp[N];
out.println(ans);
out.close();
}
}
なんか全然合わなくて解説見ながらちょっと調整したけど何が変わったのかいまだにわかってない()。
感想
A:易しい
B:ちょっと手間取っちゃった
C:割と早めに気付いた
D:謎に易しい
E:メモ書きで試してみたら早めに見えてきた
F:う～ん…見えない…
って感じでした。
悪くはない気がしますが…う～ん…。