はじめに
SimpleScannerによろしくない部分があったので書き換えました。もしコピペして使ってた人がいたら注意してください(そもそもそんな人がいるのか疑問ですが)。
今回もDまで解けたので(コンテスト中はCまで)、そこまで解説できたらなと思います。
それでは見ていきましょう。
A - Intersection
問題文はこちら
仮にL1<L2<R1<R2だとすると、L1～L2は赤、L2～R1は二色、R1～R2は青で塗られていることになります。これをより一般的に考えていきましょう。
とりあえず、どこかは二色で塗られている場合を考えてみると、そのときのmax(L1,L2)はmin(R1,R2)よりも小さい、つまり求めたい長さ = min(R1,R2) - max(L1,L2) > 0であることがわかるかと思います(赤の範囲と青の範囲のうちより原点から遠い左端から、より原点に近い右端の範囲が二色で塗られている)。ということで、このとき出力するべき数値はmin(R1,R2) - max(L1,L2)です(以下式Aとします)。
次に、どこも二色では塗られていないときを考えてみましょう。このときのそれぞれの座標を考えると、R1≦L2かR2≦L1である(つまり一方の右端が他方の左端よりも左側)と考えられます。その時の式Aは0以下だと計算できるので、その時は0を出力するようにすれば良いです。
以上をサクッと記述するにはMath.max()とMath.min()を駆使すればまぁまぁ短く書けます。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//入力受け取り
int L1 = ss.nextInt();
int R1 = ss.nextInt();
int L2 = ss.nextInt();
int R2 = ss.nextInt();
int L = Math.max(L1,L2); //二色で塗られているであろう領域の左端
int R = Math.min(R1,R2); //二色で塗られているであろう領域の右端
Sys.out.println(Math.max(0,R-L)); //0以上にするためにMath.maxを使用
Sys.out.close();
}
}
ちなみに、BitSetやBooleanを用いた解法もあります(どっちもtrueなら+1してるだけなので本質的には何も変わらないですが)
・BitSetによる解法
・Booleanの数値変換による解法
どちらも「赤で塗られている」かつ「青で塗られている」を条件にしています。
B - Tournament Result
問題文はこちら
普通に二重for文で実装しました。
A[a][b]と対になる結果が記録されている場所はA[b][a]にあるので、そこを参照するようにしました。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//Nと結果の取得
int N = ss.nextInt();
char[][] result = new char[N][N]; //char型で受け取ってみた
for(int i=0;i<N;i++){
result[i] = ss.next().toCharArray();
}
//とりあえずNまで(N-1まででも良い)
for(int i=0;i<N;i++){
//対になっているか見るべきは左上側だけなのでjはi+1から
for(int j=i+1;j<N;j++){
//それぞれを条件分岐して書く(別にテーブルを作っても良いと思う)
if(result[i][j]=='W'){
if(result[j][i]!='L'){
System.out.println("incorrect");
System.exit(0);
}
}
else if(result[i][j]=='L'){
if(result[j][i]!='W'){
System.out.println("incorrect");
System.exit(0);
}
}
else{
if(result[j][i]!='D'){
System.out.println("incorrect");
System.exit(0);
}
}
}
}
//forを抜けた=全部合っていたのでcorrect
Sys.out.println("correct");
Sys.out.close();
}
}
文字の判定方法は他にもあります(cirno3153さんの解説にある、文字コードを3で割ったあまりを使った方法など)。
C - NewFolder(1)
問題文はこちら
これまでに出てきた文字かを記録する必要があり、更にその文字が過去に何回出現したかを記録する必要があるので、Mapの使用を考えました。
TreeMapでもHashMapでも良いですが、とりあえず過去に出ているならその数を()で括って出力し、出てきていないなら新しくMapに記録するように実装してやりましょう。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//Nの取得
int N = ss.nextInt();
//記録用HashMap
HashMap<String,Integer> list = new HashMap<String,Integer>();
//順に受け取っていく
for(int i=0;i<N;i++){
//文字の取得
String temp = ss.next();
//受け取った文字をKeyに値を受け取る(新種の時にnullが返ってくるのでIntegerで)
Integer num = list.get(temp);
//過去に出てきているなら()で出現回数を括って出力
if(num!=null){
Sys.out.println(temp+"("+num+")");
list.replace(temp,num+1); //記録を更新
}
//新種ならそのまま出力して記録
else{
Sys.out.println(temp);
list.put(temp,1);
}
}
Sys.out.close();
}
}
SimpleScannerのまずいところもこの問題で気付きました。レートがかなり下がりましたが、気付けた代償と思えば…。
D - Flipping and Bonus
問題文はこちら
解説を見て「そうなのか…」と思いながら書いたコードなので、汚い点以外は多分解説と一緒です。
i回目にカウンタがjになるのはルール上、i-1回目にカウンタがj-1の時に表を出すときしかあり得ません。
ですので、そのような箇所を参照し、更にi回目に貰える金額とカウンタがjの時のボーナスを加えればi回目にカウンタがjになるときの金額が求められます。
これを二次元配列に記録しながら行なう、いわゆるDPを使って解きました。
class Main{
static Library Sys = new Library();
static SimpleScanner ss = new SimpleScanner();
public static void main(String[] args)throws IOException{
//情報の受け取り
int N = ss.nextInt();
int M = ss.nextInt();
long[] X = new long[N+1]; //オーバーフロー避けのためにlongで
for(int i=0;i<N;i++){
X[i] = ss.nextLong();
}
long[] bonus = new long[N+1]; //オーバーフロー避けのためにlongで
for(int i=0;i<M;i++){
bonus[ss.nextInt()] = ss.nextLong();
}
//dp用の配列
long[][] dp = new long[N+1][N+1];
Arrays.fill(dp[0],Long.MIN_VALUE); //事前に全部低い値に
dp[0][0] = 0; //初期状態は0で
//N回コインを投げる
for(int i=1;i<=N;i++){
//今までに投げた中で一番多くお金がもらえた金額を記録する変数
long max = dp[i-1][0];
//+1回表が出た時にカウントがjになるものにX回目の時の金額とカウントがjの時のボーナスを加算して格納
for(int j=1;j<=N;j++){
max = Math.max(max,dp[i-1][j]); //max値を更新しておく
dp[i][j] = dp[i-1][j-1] + X[i-1] + bonus[j];
}
//i回投げて今カウントが0の時の最高額は直前の最高額の時に裏を出した時だと考えられるので、maxを代入
dp[i][0] = max;
}
//答え用
long max = 0;
//N回投げたときの各記録で最高額を探す
for(int i=0;i<=N;i++){
max = Math.max(max,dp[N][i]);
}
//答えの出力
Sys.out.println(max);
Sys.out.close();
}
}
うーん…これは今の私の実力的に思いつかないでしょうね。慣れが必要そうです。
感想
A:普段通りの難易度
B:ちょっとめんどくさいけど普段通りの難易度かな
C:慣れてきたのか解法はすぐ思いついた(AtCoder Problemsの難易度的に時間をかければみんな解けてるのかな)
D:何も思いつかなかった…これが緑の壁か…。
って感じでした。
忘れっぽいからわからないけど、DP久しぶり？じゃないすかね。ちょっと他の問題も解いて慣れておきたいですね。