※2022/10/17 Fを追記しました
はじめに
今回はコンテスト中にDまで、コンテスト後にEが解けたのでEまで書きます。
では、見ていきましょう。
A - Apple
問題文はこちら
X円払って1個買うかY円払って3個買うかですが、要はどっちがお得かを求めれば良いです。
YがXの3倍より大きいならX円でN個買った方がお得です。一方、Xの三倍よりもYの方が小さいなら3個セットの方がお得です。
ということでそれをMath.minを使って記述して解きました。
Nは3の倍数とは限らないので3個セットで買うときはX*(N%3)を足すことに注意しましょう。
A.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//値の受け取り
int X = System.in.nextInt();
int Y = System.in.nextInt();
int N = System.in.nextInt();
//安く買える方の代金を出力
System.out.println(Math.min(X*N,Y*(N/3)+X*(N%3)));
System.out.close();
}
}
比較的簡単ですね。
B - Explore
問題文はこちら
普通にシミュレーションしました。
ボーナスは部屋に入った時に貰えるので先に受け取り、その後にAだけ消費するようにすれば良いです。
B.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//値の受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
long T = System.in.nextLong();
int[] A = System.in.nextInt(N-1);
//部屋番号をindexにした
int[] bonus = new int[N];
while(M-->0){
bonus[System.in.nextInt()-1] = System.in.nextInt();
}
//部屋番号をiで管理(indexが0から始まるので部屋番号-1が格納されている)
int i = 0;
while(i<N-1){
//足してから引く
T += bonus[i];
T -= A[i++];
//0以下になったらループから抜ける
if(T<=0){
break;
}
}
//0より大きい状態で終えたか？
System.out.println(T>0?"Yes":"No");
System.out.close();
}
}
持ち時間Tはbonusがすんごい大きくて消費する持ち時間が凄く小さい時にintじゃ収まらなくなるのでlongにしました(ペナルティを頂いてしまった･･･)。
C - Belt Conveyor
問題文はこちら
B同様シミュレーションしました。
実際に移動してみて、動けなくなったらその座標を出力。もし一度来たことのある場所にたどり着いたらループ確定なので-1を出力。って感じです。
C.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//値の受け取り
int H = System.in.nextInt();
int W = System.in.nextInt();
char[][] map = new char[H][W];
for(int i=0;i<H;i++){
map[i] = System.in.next().toCharArray();
}
//初期位置
int x = 0;
int y = 0;
//一度通った場所か管理する配列
boolean[][] check = new boolean[H][W];
//break使って抜けたいのでラベル付き
Loop:
while(true){
//今いる場所をtrueに
check[x][y] = true;
//文字に合わせて移動(移動できなかったらLoopを抜ける)
switch(map[x][y]){
case 'U':
if(x==0)break Loop;
x--;
break;
case 'D':
if(x==H-1)break Loop;
x++;
break;
case 'L':
if(y==0)break Loop;
y--;
break;
case 'R':
if(y==W-1)break Loop;
y++;
break;
}
//一度来たことがある？
if(check[x][y]){
System.out.println(-1);
System.out.close();
return;
}
}
//1小さいのでx、yともに+1する
x++;y++;
System.out.println(x+" "+y);
System.out.close();
}
}
特に難しくはないですね。
D - Iroha and Haiku (New ABC Edition)
問題文はこちら
累積和としゃくとり法で実装しました。
xを固定して、P以上になるまでyをずらし、Q以上になるまでzをずらし、R以上になるまでwをずらすって感じです。
D.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//値の受け取り
int N = System.in.nextInt();
long P = System.in.nextLong();
long Q = System.in.nextLong();
long R = System.in.nextLong();
int[] A = System.in.nextInt(N);
//累積和
long[] sum = new long[N+1];
for(int i=1;i<=N;i++)sum[i] = sum[i-1]+A[i-1];
//適当な初期値
int y=1,z=2,w=3;
//xを0から順にずらしていく
for(int x=0;x<N;x++){
//それぞれが条件を満たすまでインクリメント
while(sum[y]-sum[x]<P&&y<N)y++;
while(sum[z]-sum[y]<Q&&z<N)z++;
while(sum[w]-sum[z]<R&&w<N)w++;
//条件を満たしている？
if(sum[y]-sum[x]==P&&
sum[z]-sum[y]==Q&&
sum[w]-sum[z]==R){
System.out.println("Yes");
System.out.close();
return;
}
}
//forを抜けた=Noを出力
System.out.println("No");
System.out.close();
}
}
しゃくとり法勉強したのが当日だったので運が良かったです(longで受け取るの忘れてペナルティを頂きましたが･･･)。
E - Warp
問題文はこちら
大体公式解説通りのはずです(公式解説の遷移の仕方がよくわからなかった)。
i回ワープしたときに1番目のワープ(以下ワープ1)をj回、2番目のワープ(以下ワープ2)をk回した時の経路の数をdp[i][j][k]とした動的計画法で解きました(3番目のワープ(以下ワープ3)はi-j-kで求められるので要らない)。
ワープ1をj回、ワープ2をk回、ワープ3をi-j-k回にする直前の経路は(j-1, k, i-j-k)と(j, k-1, i-j-k)と(j, k, i-j-k-1)の三通りなので、漸化式は以下のような感じになるかと思います。
$dp[i][j][k]=dp[i-1][j-1][k]+dp[i-1][j][k-1]+dp[i-1][j][k] (i,j,k>0)$
jが0ならdp[i-1][j-1][k]の部分は0、kが0ならdp[i-1][j][k-1]の部分は0です(-1回という移動はあり得ないので)。
E.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
static int mod = 998244353;
public static void main(String[] args)throws IOException{
//各値の受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
long A = System.in.nextLong();
long B = System.in.nextLong();
long C = System.in.nextLong();
long D = System.in.nextLong();
long E = System.in.nextLong();
long F = System.in.nextLong();
//障害物の管理(x,yの二つをキーにしたいのでArrayList<Long>を突っ込む
HashSet<ArrayList<Long>> block = new HashSet<ArrayList<Long>>();
while(M-->0){
ArrayList<Long> temp = new ArrayList<Long>();
temp.add(System.in.nextLong());
temp.add(System.in.nextLong());
block.add(temp);
}
//dp[i][j][k]=i回ワープを行なっていて、ワープ1がj回、ワープ2がk回
int[][][] dp = new int[N+1][N+1][N+1];
//(0,0)に最初いるので1
dp[0][0][0] = 1;
for(int i=1;i<=N;i++){
for(int j=0;j<=i;j++){
for(int k=0;k<=i-j;k++){
//座標を計算
long x = A*j+C*k+E*(i-j-k);
long y = B*j+D*k+F*(i-j-k);
//障害物を検索するためにArrayListに格納
ArrayList<Long> temp = new ArrayList<Long>();
temp.add(x);
temp.add(y);
//障害物は無い？
if(!block.contains(temp)){
dp[i][j][k] += j!=0 ? dp[i-1][j-1][k] : 0;
dp[i][j][k] %= mod;
dp[i][j][k] += k!=0 ? dp[i-1][j][k-1] : 0;
dp[i][j][k] %= mod;
dp[i][j][k] += dp[i-1][j][k];
dp[i][j][k] %= mod;
}
}
}
}
//N回ワープしたときの経路の総数を数え上げ
int ans = 0;
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++){
ans += dp[N][i][j];
ans %= mod;
}
}
//出力
System.out.println(ans);
System.out.close();
}
}
本番はわからなかった･･･。DP苦手過ぎる･･･。
感想
A、B:比較的簡単。
C:ちょっとめんどくさい。けど易しい。
D:知ってればサクッと解ける(公式解説はしゃくとり法ではなく二分探索らしい)。
E:DPわからん･･･けどちょっと易しめ･･･？
って感じでした。
4完だったので嬉しいですが、4完できると「5完したかったな･･･」ってなりますね。
追記(F - Manhattan Cafe)
ayataka5さんの解説のおかげで解けたので載せておきます。
方針は上記の記事と全く同じです。
F.java
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
static int mod = 998244353;
public static void main(String[] args)throws IOException{
//N、D、p、qの受け取り
int N = System.in.nextInt();
int D = System.in.nextInt();
int[] p = System.in.nextInt(N);
int[] q = System.in.nextInt(N);
//dp[i][j]:pとの距離がi、qとの距離がjの個数
int[][] dp = new int[D+1][D+1];
//初期値
dp[0][0] = 1;
//N次元目まで遷移する
for(int i=0;i<N;i++){
//累積和を取るために複製(sum1が左上->右下、sum2が左下->右上)
int[][] sum1 = new int[D+1][D+1];
int[][] sum2 = new int[D+1][D+1];
for(int j=0;j<dp.length;j++){
java.lang.System.arraycopy(dp[j],0,sum1[j],0,dp[j].length);
java.lang.System.arraycopy(dp[j],0,sum2[j],0,dp[j].length);
}
//それぞれ累積和を取る
for(int j=0;j<D;j++){
for(int k=0;k<D;k++){
sum1[j+1][k+1] += sum1[j][k];
sum1[j+1][k+1] %= mod;
}
}
for(int j=0;j<D;j++){
for(int k=0;k<D;k++){
sum2[j+1][k] += sum2[j][k+1];
sum2[j+1][k] %= mod;
}
}
//差を別に記録しておく
int sub = Math.abs(p[i]-q[i]);
//遷移
for(int j=0;j<=D;j++){
for(int k=0;k<=D;k++){
//和を取る(上記記事のX、Z部分)
int num = 0;
num += (j-1<0||k-sub-1<0) ? 0 : sum1[j-1][k-sub-1];
num %= mod;
num += (j-sub-1<0||k-1<0) ? 0 : sum1[j-sub-1][k-1];
num %= mod;
//可読性の為に別変数に
int nj = j-sub-1, nk = k+1;
int kk = k<sub ? 0 : k-sub;
int jj = k<sub ? j+k-sub : j;
//上記記事のYの部分の和を取る
num += jj<0 ? 0 : (int)(((long)sum2[jj][kk] - ((0<=nj&&nk<=D) ? sum2[nj][nk] : 0))%mod);
num %= mod;
//dpに記録
dp[j][k] = num;
}
}
}
//dp内の総和が答えになるので全部足す
int ans = 0;
for(int i=0;i<=D;i++){
for(int j=0;j<=D;j++){
ans += dp[i][j];
ans %= mod;
}
}
//遷移中に引き算があって負数になっている場合があるのでそのときはmodを足す
System.out.println(ans<0 ? ans+mod : ans);
System.out.close();
}
}
普通に難しかったです･･･。記事を書いてくださって感謝しかない･･･。