はじめに
今回はコンテスト中にGまで解けたのでそのコードをそのまま載せようと思います。
では、見ていきましょう。
なお、ライブラリは提出結果よりご確認ください。
A - New Scheme
問題文はこちら
直前の値だけもって、順に受け取って処理しました。
A.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//仮想的にNを
int N = 8;
//直前の数字(Sは0以上なので初期値は0で)
int bef = 0;
//8回受け取り
while(N-->0){
int S = sc.nextInt();
//条件を満たしていなければNoを出力して終了
if(bef>S||S<100||675<S||S%25!=0){
System.out.println("No");
return;
}
bef = S;
}
//ループを抜けた=Yes
out.println("Yes");
out.close();
}
}
そんなに難しくないですね。
B - Default Price
問題文はこちら
HashMapを使って処理しました。
B.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、S、D、Pの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
String[] S = sc.next(N);
String[] D = sc.next(M);
int[] P = sc.nextInt(M+1);
//Mapの構築
HashMap<String,Integer> map = new HashMap<>();
for(int i=0;i<M;i++)
map.put(D[i],P[i+1]);
//答え用変数
int sum = 0;
//それぞれの値段を調べて加算(無ければP[0]を返すように)
for(String s:S)
sum += map.getOrDefault(s,P[0]);
//答えの出力
out.println(sum);
out.close();
}
}
普通に全探索でも間に合うと思いますが、こっちの方が簡潔かなぁと思ってこの方法で実装しました。
C - Standings
問題文はこちら
それぞれの人の情報を保持するPersonクラスを作ってArrays::sortに比較方法を渡す方法で解きました。
C.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//nの受け取り
int N = sc.nextInt();
//Personクラスの宣言
class Person{
int id,A,B;
public Person(int i,int a,int b){
id = i;
A = a;
B = b;
}
}
//それぞれの人の情報の受け取り
Person[] p = new Person[N];
for(int i=1;i<=N;i++)
p[i-1] = new Person(i,sc.nextInt(),sc.nextInt());
//ソート
Arrays.sort(p,(a,b)->{
long num = (long)a.A*(b.A+b.B)-(long)b.A*(a.A+a.B);
if(num==0)
return Integer.compare(a.id,b.id); //成功率が一緒なら番号の小さい順に
return -Long.signum(num); //成功率が違うなら降順に
});
//別配列に答えを格納(ライブラリ的に出力がしやすいので)
int[] ans = new int[N];
for(int i=0;i<N;i++)
ans[i] = p[i].id;
//答えの出力
out.println(ans);
out.close();
}
}
Comparableを実装するのとどっちがよりサクッと実装できるかなと悩みましたがまぁArrays::sortに渡せば良いかとなってこっちの方法で実装しました。
D - Snuke Maze
問題文はこちら
BFSで解きました。
D.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( 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);
//BFS
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(0);
deq.add(0);
boolean[][] checked = new boolean[H][W];
checked[0][0] = true;
int[] d = {1,-1,0,0,1,-1};
while(deq.size()>0){
int x = deq.pollFirst();
int y = deq.pollFirst();
for(int i=0;i<4;i++){
int nX = x+d[i];
int nY = y+d[i+2];
if(0<=nX&&nX<H&&0<=nY&&nY<W&&!checked[nX][nY]){
//snukeの順に移動できるかどうかも見るように
if(S[x][y]=='s'&&S[nX][nY]=='n'){
deq.add(nX);
deq.add(nY);
checked[nX][nY] = true;
}
if(S[x][y]=='n'&&S[nX][nY]=='u'){
deq.add(nX);
deq.add(nY);
checked[nX][nY] = true;
}
if(S[x][y]=='u'&&S[nX][nY]=='k'){
deq.add(nX);
deq.add(nY);
checked[nX][nY] = true;
}
if(S[x][y]=='k'&&S[nX][nY]=='e'){
deq.add(nX);
deq.add(nY);
checked[nX][nY] = true;
}
if(S[x][y]=='e'&&S[nX][nY]=='s'){
deq.add(nX);
deq.add(nY);
checked[nX][nY] = true;
}
}
}
}
//右下にたどり着いた？
out.println(checked[H-1][W-1]?"Yes":"No");
out.close();
}
}
Mapで条件分岐省略した方が良いよなぁと思いながらコピペした方が速い気がして雑に全部書きました。
E - MEX
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i][j][k]$を$i$文字目まででMEXの$j$文字目まで構築した時の状態が$k$である通り数として保持して遷移すると、$\mathrm{dp}[N][3][1]+\mathrm{dp}[N][3][5]+2\times\mathrm{dp}[N][3][3]+3\times\mathrm{dp}[N][3][7]$が答えとなります。
E.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、A、Sの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
String S = sc.next();
//dpテーブル
long[][][] dp = new long[N+1][4][8];
dp[0][0][0] = 1; //初期値
//遷移
for(int i=0;i<N;i++){
for(int j=0;j<4;j++)
for(int k=0;k<8;k++)
dp[i+1][j][k] = dp[i][j][k];
if(S.charAt(i)=='M')
for(int j=0;j<8;j++)
dp[i+1][1][j|(1<<A[i])] += dp[i][0][j];
if(S.charAt(i)=='E')
for(int j=0;j<8;j++)
dp[i+1][2][j|(1<<A[i])] += dp[i][1][j];
if(S.charAt(i)=='X')
for(int j=0;j<8;j++)
dp[i+1][3][j|(1<<A[i])] += dp[i][2][j];
}
//答えの和を求めて出力
long ans = dp[N][3][1]+dp[N][3][5]+2*dp[N][3][3]+3*dp[N][3][7];
out.println(ans);
out.close();
}
}
これもMap使ってもっと記述量減らせたんですが、気付いたのがif(S.charAt(i)=='M')を書き終わったあたりだったのでそのまま書きました。
F - Vouchers
問題文はこちら
PriorityQueueを使った貪欲法で解きました。
正当性は公式解説に任せます。
F.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、P、クーポンの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] P = sc.nextInt(N);
int[][] coupon = new int[M][2];
for(int i=0;i<M;i++)
coupon[i][0] = sc.nextInt();
for(int i=0;i<M;i++)
coupon[i][1] = sc.nextInt();
//クーポンをLでソート
Arrays.sort(coupon,(a,b)->Integer.compare(a[0],b[0]));
//Pもソート
Arrays.sort(P);
//クーポンのDが大きい順に取り出せるQueue
PriorityQueue<int[]> queue = new PriorityQueue<>((a,b)->-Integer.compare(a[1],b[1]));
//クーポンをどこまで見たか用の変数
int index = 0;
//答え用変数
long ans = 0;
//安い順に見ていく
for(int num:P){
//とりあえず加算
ans += num;
//現時点で使えるクーポンをqueueに移す
while(index<M&&coupon[index][0]<=num)
queue.add(coupon[index++]);
//適用できるクーポンがあれば一番Dが大きい物を適用
if(queue.size()>0)
ans -= queue.poll()[1];
}
//答えの出力
out.println(ans);
out.close();
}
}
最初値段が大きい方から決めたりクーポンをDの降順に並べ替えて貪欲にやったりしてペナを出してしまいました…。
G - Minimum Xor Pair Query
問題文はこちら
確証を持ってなかったんですが、公式解説にある性質がありそうな気がしてそれを実装しました。
G.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimplePrinter out = new SimplePrinter( System.out, autoFlush );
public static void main ( String[] args ) {
//Qの受け取り
int Q = sc.nextInt();
//MultiMapとしてのTreeMap(各値の存在判定用)
TreeMap<Integer,Integer> map = new TreeMap<>();
//各値の隣同士のxorを格納するMap
TreeMap<Integer,Integer> xor = new TreeMap<>();
//Q回クエリを読み込む
while(Q-->0){
int q = sc.nextInt();
//追加
if(q==1){
int x = sc.nextInt();
//xの前後の値を見て、存在すればxorに追加しておく
Integer c1 = map.ceilingKey(x);
Integer c2 = map.floorKey(x);
if(c1!=null)
xor.merge(x^c1,1,Integer::sum);
if(c2!=null)
xor.merge(x^c2,1,Integer::sum);
//どっちもあるときはc1とc2が隣り合わなくなるから消す必要がある
if(c1!=null&&c2!=null)
xor.merge(c1^c2,-1,(a,b)->a+b==0?null:a+b);
map.merge(x,1,Integer::sum); //mapにも追加しておく
}
//削除
else if(q==2){
int x = sc.nextInt();
map.merge(x,-1,(a,b)->a+b==0?null:a+b); //mapから消す
//自分の前後の値とのxorも削除しておく
Integer c1 = map.ceilingKey(x);
Integer c2 = map.floorKey(x);
if(c1!=null)
xor.merge(x^c1,-1,(a,b)->a+b==0?null:a+b);
if(c2!=null)
xor.merge(x^c2,-1,(a,b)->a+b==0?null:a+b);
//どっちもあったらc1とc2が隣り合うことになるから追加しておく
if(c1!=null&&c2!=null)
xor.merge(c1^c2,1,(a,b)->a+b==0?null:a+b);
}
//出力はxorで一番小さいもの
else
out.println(xor.firstKey());
}
out.close();
}
}
削除の方がバグってて1ペナ出してしまいましたが、解けて良かったです。
感想
A,B:易しい
C:実装してて誤差出そうだな～と整数で比較することにできたのが良かった
D:Twitterで見かけたけどsunukeと勘違いした人がいたっぽい
問題自体は面白いなと思った
E:Aの種類が十分に少ないのでDPでいけそうだと思えた
F:こういうのは良い感じに貪欲法が適用できそうと思えたし実際そうだった
G:$x$と$x+1$があればそこでxorが良さそうだよな～とか考えた時に、隣同士でやれば良いかも…？と思えた
って感じでした。
初めての7完！！！毎回こんなに調子が良ければ最高なんですけどねぇ。