はじめに
今回はFまでコンテスト中に解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Weak Beats
問題文はこちら
愚直に調べました。
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 ) {
//Sの受け取り
String S = sc.next();
//偶数番目が1になっていないか調べる
for(int i=1;i<S.length();i+=2){
if(S.charAt(i)=='1'){
System.out.println("No");
return; //偶数番目が1ならNoを出力して終わらせる
}
}
//ループを抜けた=条件を満たしているのでYesを出力
out.println("Yes");
out.close();
}
}
偶数番目が1である数字とビット論理積を取る、という手法もありましたね
A改.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//Sを2進数と解釈して受け取り
int S = sc.nextInt(2);
//偶数番目のビットが立っていないか調べる
System.out.println((S&0x5555)==0?"Yes":"No");
}
}
B - Round-Robin Tournament
問題文はこちら
問題文の通りに実装しました。
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の受け取り
int N = sc.nextInt();
//new int[2]{勝利数,プレイヤーの番号}の配列を作成する
int[][] S = new int[N][2];
for(int i=0;i<N;i++){
String subS = sc.next();
int count = 0;
for(char c:subS.toCharArray())
count += c=='o'?1:0;
S[i][0] = count;
S[i][1] = i+1;
}
//条件の通りにソート(呼び出されるsortメソッドはTim Sortで実装されていて、これは安定ソートなので勝利数が一致したときの分岐は要りませんでした)
Arrays.sort(S,(a,b)->a[0]==b[0]?a[1]-b[1]:b[0]-a[0]);
//順に番号を出力
for(int i=0;i<N;i++){
out.print(S[i][1]);
out.print(" ");
}
out.println();
out.close();
}
}
C - World Tour Finals
問題文はこちら
ちょっと面倒ですが、愚直に全探索しました。
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、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(M);
//各人の解いた問題と総得点を受け取る
boolean[][] solved = new boolean[N][M];
int[] score = new int[N];
for(int i=0;i<N;i++){
String S = sc.next();
for(int j=0;j<M;j++)
if(solved[i][j]=S.charAt(j)=='o')
score[i] += A[j];
score[i] += i+1;
}
//問題の得点が大きい順にインデックスをソート(比較関数を渡したいのでInteger[]で)
Integer[] problem = new Integer[M];
Arrays.setAll(problem,i->i);
Arrays.sort(problem,(a,b)->A[b]-A[a]);
//各人に対しての答えを求める
for(int i=0;i<N;i++){
//自分以外の最大値を求める
int max = 0;
for(int j=0;j<N;j++){
if(i==j)
continue;
max = Math.max(max,score[j]);
}
//maxを上回るまで得点が大きい順に問題を解く
int now = score[i];
int ans = 0;
for(int j=0;now<=max;j++){
if(solved[i][problem[j]])
continue;
now += A[problem[j]];
ans++;
}
//解いた問題の総数を求める
out.println(ans);
}
out.close();
}
}
D - Merge Slimes
問題文はこちら
小さい方から愚直に合成すれば最小になるので、TreeMapを使ってシミュレーションしました。
最悪ケースを考えた時にkeyがlongに収まらない気がしたのでBigIntegerを用いています。
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の受け取り
int N = sc.nextInt();
//スライムをTreeMapに格納
TreeMap<BigInteger,Long> map = new TreeMap<>();
while(N-->0){
BigInteger S = BigInteger.valueOf(sc.nextLong());
long C = sc.nextLong();
map.merge(S,C,Long::sum);
}
//答え用変数
long ans = 0;
//合成できる可能性のあるスライムが無くなるまで回す
while(map.size()>0){
//今一番小さいスライムを取り出す
Map.Entry<BigInteger,Long> entry = map.pollFirstEntry();
BigInteger size = entry.getKey();
long count = entry.getValue();
//奇数なら1体だけ余るので答えに加算
ans += count%2;
//合成されたスライムがいるならMapに戻す
if(count>1){
count >>= 1;
map.merge(size.shiftLeft(1),count,Long::sum);
}
}
//答えの出力
out.println(ans);
out.close();
}
}
BigIntegerを用いている分まぁまぁ重いですけど、1200ms台なので許容範囲かなと思ってます。
E - Playlist
問題文はこちら
動的計画法で解きました。
最後に曲$1$が再生されてさえくれれば良いので、「$\mathrm{dp}[i]:$時刻$i$で何かしらの曲が終わる確率」として遷移し、時刻$X+0.5$で曲$1$が再生されているには時刻$X-A_0+1～X$で曲が終わって曲$1$が再生される必要があるので、$\frac{1}{N}\sum_{i=\max(0,X-A_0+1)}^{X}{\mathrm{dp}[i]}$が答えになると思い、実装しました。
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、X、Tの受け取り
int N = sc.nextInt();
int X = sc.nextInt();
int[] T = sc.nextInt(N);
//法
final int mod = 998244353;
//逆元の前計算(1/N)
long odds = MathFunction.modPow(N,mod-2,mod);
//DPテーブルの作成
long[] dp = new long[X+1];
dp[0] = 1;
//遷移
for(int i=0;i<X;i++){
for(int t:T){
if(t+i<=X){
dp[t+i] += dp[i]*odds%mod;
dp[t+i] %= mod;
}
}
}
//上記の式の総和を求める
long ans = 0;
for(int i=0;i<Math.min(X+1,T[0]);i++)
ans += dp[X-i];
ans %= mod;
//sum/N mod 998244353を出力
out.println(ans*odds%mod);
out.close();
}
}
結構悩みましたけど、解法が浮かんで良かったです。
F - Push and Carry
問題文はこちら
基本的には目的地から見た荷物の背後に回り込んで移動させるのが最善なので、目的地の座標に対して荷物の座標が、$x$座標も$y$座標も異なるなら$x$座標と$y$座標のどちらを先に合わせるかの$2$通りのみ考えれば良く、どちらか一方の座標が同一ならば異なる方を合わせるように移動することだけを考えれば良いと思い、実装しました。どっちの座標も一緒である状態は制約上あり得ないので考慮していないです。
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 ) {
//座標の受け取り
long XA = sc.nextLong();
long YA = sc.nextLong();
long XB = sc.nextLong();
long YB = sc.nextLong();
long XC = sc.nextLong();
long YC = sc.nextLong();
//x座標が異なる時
if(XB!=XC){
//y座標も異なる時
if(YB!=YC){
//x座標から合わせる時の答えを求める
long ans1 = Math.abs(XA-XB-Long.signum(XB-XC))+Math.abs(YA-YB);
if(YA==YB&&Long.signum(XB-XC)==Long.signum(XB-XA))
ans1 += 2;
ans1 += Math.abs(XB-XC);
ans1 += 2;
ans1 += Math.abs(YB-YC);
//y座標から合わせる時の答えを求める
long ans2 = Math.abs(XA-XB)+Math.abs(YA-YB-Long.signum(YB-YC));
if(XA==XB&&Long.signum(YB-YC)==Long.signum(YB-YA))
ans2 += 2;
ans2 += Math.abs(YB-YC);
ans2 += 2;
ans2 += Math.abs(XB-XC);
//小さい方を出力
out.println(Math.min(ans1,ans2));
}
//y座標は同じ時
else{
//x座標を合わせるのにかかる操作数を求めて出力
long ans = Math.abs(XA-XB-Long.signum(XB-XC))+Math.abs(YA-YB);
if(YA==YB&&Long.signum(XB-XC)==Long.signum(XB-XA))
ans += 2;
ans += Math.abs(XB-XC);
out.println(ans);
}
}
//x座標は同じ時(制約上y座標が絶対異なる)
else{
//y座標を合わせるのにかかる操作数を求めて出力
long ans = Math.abs(XA-XB)+Math.abs(YA-YB-Long.signum(YB-YC));
if(XA==XB&&Long.signum(YB-YC)==Long.signum(YB-YA))
ans += 2;
ans += Math.abs(YB-YC);
out.println(ans);
}
out.close();
}
}
かなり手間取りました…。ペナさえ出さなければもっとマシな成績だったのに…。
感想
A:易しめ
B:配列のソートはArrays::sortでサクッとって感じ
C:ちょっとめんどくさいけど、易しい方
D:愚直でも間に合うので易しいかも(重いけど)
E:DPかもと思えて良かった。ちょっと難しめ？
F:割と考察さえできれば解けるかなって感じ(ちゃんと場合分けとかできますか？ってところが難易度高め)
って感じでした
Fでペナ出さなければ…とは思いましたが、まぁそこも含めて実力ですからね…ちゃんと実装力鍛えないと…。