はじめに
今回も4完できたのでDまで書こうと思います。
では見ていきましょう。
A - Saturday
問題文はこちら
if～elseで実装しました。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Sの受け取り
String S = System.in.next();
//全部書く(根性)
if(S.equals("Monday")){
System.out.println(5);
}else if(S.equals("Tuesday")){
System.out.println(4);
}else if(S.equals("Wednesday")){
System.out.println(3);
}else if(S.equals("Thursday")){
System.out.println(2);
}else{
System.out.println(1);
}
System.out.close();
}
}
先頭じゃ判定できないな･･･なんて思ってたんですが、二文字目で判定できましたね。頭が固い･･･。
B - Split?
問題文はこちら
普通に全探索しました。
まずピン1が立ってるならNoで終了します。
次に、列ごとに全部倒れてるか否かをboolean型配列で保持して左端からfor文でスプリットとなる箇所を探します。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Sの受け取り(char型配列で)
char[] S = System.in.next().toCharArray();
//ピン1が倒れていない？
if(S[0]=='1'){
System.out.println("No");
System.out.close();
return;
}
//各列の情報
boolean[] check = new boolean[7];
check[0] = S[6]=='1';
check[1] = S[3]=='1';
check[2] = (S[1]=='1'||S[7]=='1');
check[3] = S[4]=='1';
check[4] = (S[2]=='1'||S[8]=='1');
check[5] = S[5]=='1';
check[6] = S[9]=='1';
//全探索
for(int i=0;i<5;i++){
if(!check[i])continue;
//右隣は倒れてる？
if(!check[i+1]){
//一本以上立っている列が右側にあるか全探索
for(int j=i+2;j<7;j++){
if(check[j]){
System.out.println("Yes");
System.out.close();
return;
}
}
}
}
//スプリットが見つからなかったらNo
System.out.println("No");
System.out.close();
}
}
最初、間にある倒れている列は一つだと勘違いしていたのでペナルティを頂いてしまいました。サンプルにやられた･･･。
C - Index × A(Continuous ver.)
問題文はこちら
累積和っぽいやり方をしました。
まず$A_1～A_M$を選択した場合を二つの変数(以降answerとtemp)、sum=$\sum_{k=1}^{M}{A_k}$とします。
あとは順に全探索するんですが、$A_i～A_{i+M}$から$A_{i+1}～A_{i+1+M}$に遷移するときはtempからsumを引き、$A_{i+1+M}×M$を加算すればtは$A_{i+1}～A_{i+1+M}$に遷移できます。この後sumに$A_i-A_{i+1+M}$を引き算することで次の遷移を行なうことが出来ます。
具体的には、以下のようなことを一番後ろまで繰り返します(簡略化のためにM=3としています)。
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();
int[] A = System.in.nextInt(N);
//初期値を設定
long answer = 0;
long sum = 0;
for(int i=0;i<M;i++){
answer += (long)A[i]*(i+1);
sum += A[i];
}
//今見ている和を記録する変数
long temp = answer;
//全探索
for(int i=M;i<N;i++){
temp -= sum;
temp += (long)A[i]*M;
sum -= A[i-M];
sum += A[i];
//最高値更新？
if(answer<temp){
answer = temp;
}
}
//答えの出力
System.out.println(answer);
System.out.close();
}
}
オーバーフロー考えてなくてペナルティを頂いてしまいました。
D - Index × A(Not Continuous ver.)
問題文はこちら
動的計画法で解きました。
i番目までにj個選んだ時の最大値をdp[i][j]として記録して以下のように遷移していきました。
$dp[i][j] = \mathrm{max}(dp[i-1][j],dp[i-1][j-1]+A[i]×j)$
iが1～Mのときはいろいろ分岐が必要になってめんどくさかったんで別々に書きました。
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();
int[] A = System.in.nextInt(N);
//dp[i][j]:i番目までにj個選んだ時の最大値
long[][] dp = new long[N+1][M+1];
//iが1～Mの時のやつ
for(int i=1;i<=M;i++){
dp[i][1] = Math.max(dp[i-1][1],A[i-1]);
for(int j=2;j<i;j++){
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]+A[i-1]*j);
}
dp[i][i] = dp[i-1][i-1]+A[i-1]*i;
}
//i>Mの時のやつ
for(int i=M+1;i<=N;i++){
dp[i][1] = Math.max(dp[i-1][1],A[i-1]);
for(int j=2;j<=M;j++){
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]+A[i-1]*j);
}
}
//N個まででM個選んだ時の最大値を出力
System.out.println(dp[N][M]);
System.out.close();
}
}
思っていたよりサクッと解けたので良かったです。
感想
A:ちょっとめんどくさいけど易しい。
B:超めんどくさい。
C:最初わからなかった。ちょっと苦手かも･･･。
D:DPなんだろうなって思ったらやっぱりDPだった。典型っぽい？
って感じでした。
Eも解きたかったんですが、グラフってワードが出るとまだ拒絶反応が･･･。精進しなくては･･･。