はじめに
Dはコンテスト後に解いたものですが、実行時間的にもメモリ的にもあまりよろしくないのでそのうち追記しようかなと思います(反面教師的な感じで解説はしておく)。
なお、LibraryクラスのBufferedReaderをSimpleScannerにしたのでご注意ください。
では見ていきましょう。
A - World Cup
問題文はこちら
4で割ったあまりが2であることと現在が1月で大会は6月に開催されることを考えると、
・Y%4=0の時、Y/4×4=Yなので、Y+2=Y/4×4+2に開催される。
・Y%4=1の時、Y/4×4=Y-1なので、Y+1=Y/4×4+2に開催される。
・Y%4=2の時、Y/4×4=Y-2なので、Y=Y/4×4+2に開催される。
・Y%4=3の時、Y/4×4=Y-3なので、Y+3=Y/4×4+6に開催される。
の四種類を考える必要があります。ここで、Y%4=3の時だけ6=4+2加算する必要があることに着目すると、事前にYに1を加算することで(以降Y+1=y)、y/4×4=Y+1にすることが出来るのでY+3=y/4×4+2で計算出来ます。
さらに、0≦Y%4≦2ならばY/4=y/4なのでどの値でもy/4×4+2で計算が出来ます。ということで、それを実装してやりましょう。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nを受け取って1加算
int N = System.in.nextInt()+1;
//上記の式の計算結果を出力
System.out.println((N/4)*4+2);
System.out.close();
}
}
ちょっと悩んでしまいましたが、まぁ問題はなさそうです。
B - Triangle (Easier)
問題文はこちら
全探索しました。
3重forですべての組合せを探しましたが、この場合(a,b,c)の組合せを6回重複して数えてしまうので最後に/6をしています。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、Mの取得
int N = System.in.nextInt();
int M = System.in.nextInt();
//辺をboolean型で管理
boolean[][] route = new boolean[N][N];
while(M-->0){
int temp1 = System.in.nextInt()-1;
int temp2 = System.in.nextInt()-1;
route[temp1][temp2] = route[temp2][temp1] = true;
}
//数え上げ
long answer = 0;
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){ //j=i+1でも良かったか･･･？
if(i==j)continue; //同じ頂点ははじく
if(route[i][j]){
for(int k=0;k<N;k++){ //k=j+1でも良かったか･･･？
if(i==k||j==k)continue; //同じ頂点ははじく
if(route[j][k]&&route[k][i])answer++;
}
}
}
}
//同じ組合せ分をはじいて出力(j、kを工夫すれば必要ない)
System.out.println(answer/6);
System.out.close();
}
}
コメントでも書きましたが、jとkの初期値変えれば/6はいらなくなります(本番だと何故か気付かない･･･なんで･･･)。
C - Min Max Pair
問題文はこちら
添え字と要素が同じものを数えつつ、A[i]とA[A[i]-1]を比べることでサクッと数えられます。for文で探しましょう。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、Aの取得
int N = System.in.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++)A[i] = System.in.nextInt();
//答え用変数と、添え字と要素が同じものを数える変数
long answer = 0;
long count = 0;
//先頭から見ていく
for(int i=0;i<N;i++){
//添え字と要素が同じ？
if(A[i]==i+1){
count++;
continue;
}
//条件に見合っているか？
if(Math.min(A[i],A[A[i]-1])==i+1&&Math.max(A[i],A[A[i]-1])==A[i]){
answer++;
}
}
//添え字と要素が同じものの組合せ分をanswerに加算して出力
System.out.println(answer+count*(count-1)/2);
System.out.close();
}
}
最初添え字と要素が同じものを数えるのを忘れてしまい、全然答えが合わなくて焦ってしまいました。しっかり考えて実装しないといけないですね･･･。
D - I Hate Non-integer Number
問題文はこちら
dpで実装しました。
i番目までにj個選んだときのmod kがlの個数をdp[i][j][k][l]として保持し、dp[i][j][k][l]とdp[i][j+1][k][(l+A[i-1])%k]にdp[i-1][j][k][l]を加算し続けることで答えを求めることが出来ます。
class Main{
static long mod = 998244353;
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、Aの取得
int N = System.in.nextInt();
int[] A = System.in.nextInt(N); //N個要素を取得している
//[i][j][k][l]:i番目までにj個選んだときのmod kがlの個数
int[][][][] dp = new int[N+1][N+2][N+1][N+1]; //ちょっと多めに取っといた
//0個選ぶのは1個だけあるので全部1にしておく
for(int i=1;i<=N;i++){
dp[0][0][i][0] = 1;
}
//iを順に大きくしていってdpに記録していく
for(int i=1;i<N+1;i++){
for(int j=0;j<=i;j++){
for(int k=1;k<=N;k++){
for(int l=0;l<k;l++){
dp[i][j][k][l] += dp[i-1][j][k][l];
dp[i][j][k][l] %= mod;
dp[i][j+1][k][(l+A[i-1])%k] += dp[i-1][j][k][l];
dp[i][j+1][k][(l+A[i-1])%k] %= mod;
}
}
}
}
//条件文通りの組合せの数の総和を記録
long answer = 0;
for(int i=1;i<=N;i++){
answer += dp[N][i][i][0];
}
//最後modを取って出力
System.out.println(answer%mod);
System.out.close();
}
}
あんまり高速ではないです(1514ms)。全部保持せずに3次元に落とすなどすれば高速化できるっぽいですがまた書くのがめんどくさいので何かの機会に書きます。
感想
A:易しい。
B:グラフと言われて身構えてしまったが全探索でどうにかなった
C:ちょっと悩んでしまったが、気付けば問題ない。
D:難しい･･･全然思いつかなかった･･･。
って感じでした。
DP難しいですね･･･すらっと解ける人めちゃくちゃかっこいいなと思います。