はじめに
今回はコンテスト中にDまでとFを、コンテスト後にEを解いたのでFまで載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - Chord
問題文はこちら
特に何も考えずにequalsで全部比較しました。
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 ) {
//Sの受け取り
String S = sc.next();
//一致してるならYes、違うならNo
if(S.equals("ACE")||S.equals("BDF")||S.equals("CEG")||S.equals("DFA")||S.equals("EGB")||S.equals("FAC")||S.equals("GBD")){
out.println("Yes");
}
else
out.println("No");
out.close();
}
}
ダイアトニックコードとか言うんでしたっけ？一つ飛ばしの三和音だなぁって考えると以下のようにも実装できますね。
A改.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String chord = "ABCDEFGABCDEFG"; //予め生成しておく
//Sの受け取り
String S = sc.next();
//先頭を探す
Search:for(int i=0;i<7;i++){
//一つ飛ばしで一致してるか調べる
for(int j=0;j<3;j++){
if(S.charAt(j)!=chord.charAt(i+2*j)){
continue Search;
}
}
//ループを抜けた=一致しているのでYesを出力して終了
System.out.println("Yes");
return;
}
//一致しなかったらNo
System.out.println("No");
}
}
この方が楽だったかも？
B - TaK Code
問題文はこちら
問題文の通りになっているかを全探索しました。
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の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
char[][] S = sc.nextCharArray(N);
//全探索
for(int i=0;i+8<N;i++){
Loop:for(int j=0;j+8<M;j++){
//#のマスを調べる
for(int k=0;k<3;k++){
for(int l=0;l<3;l++){
if(S[i+k][j+l]!='#'||S[i+k+6][j+l+6]!='#')
continue Loop;
}
}
//.のマスを調べる
for(int k=0;k<4;k++){
for(int l=0;l<4;l++){
if(S[i+k][j+3]!='.'||S[i+3][j+l]!='.'||S[i+k+5][j+5]!='.'||S[i+5][j+l+5]!='.')
continue Loop;
}
}
//条件を満たしているなら出力
out.println((i+1)+" "+(j+1));
}
}
out.close();
}
}
これもそこまで難しくないですね。
C - Invisible Hand
問題文はこちら
二分探索で解きました。
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、M、A、Bの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(M);
//探索範囲[a:b]
int a = 0;
int b = 1_000_000_001;
int X = 1_000_000_001;
//二分探索
while(a-b<1){
int c = a+b>>1;
int buy = 0;
int sell = 0;
for(int num:A)
if(c>=num)
sell++;
for(int num:B)
if(c<=num)
buy++;
if(sell>=buy)
b = (X=c)-1;
else
a = c+1;
}
//答えの出力
out.println(X);
out.close();
}
}
最初探索範囲の上限を$10^9$にしてしまって1ペナ出してしまいました…。
D - Count Bracket Sequences
問題文はこちら
DPで解きました。
$\mathrm{dp}[i][j]:$$i$文字目までで(の数が)の数より$j$個だけ大きくなる?の決め方
という感じで組み合わせを保持して遷移しました。
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 ) {
//Sの受け取り
String S = sc.next();
int N = S.length(); //便宜上長さをNとおく
//DPテーブル
long[][] dp = new long[N+1][N+1];
dp[0][0] = 1;
final int mod = 998244353;
//遷移
for(int i=0;i<N;i++){
if(S.charAt(i)=='('){
for(int j=0;j<N;j++){
dp[i+1][j+1] = dp[i][j];
}
}
else if(S.charAt(i)==')'){
for(int j=0;j<N;j++){
dp[i+1][j] = dp[i][j+1];
}
}
else{
for(int j=0;j<N;j++){
dp[i+1][j+1] = dp[i][j];
}
for(int j=0;j<N;j++){
dp[i+1][j] += dp[i][j+1];
dp[i+1][j] %= 998244353;
}
}
}
//最終的に(と)の個数が一致している組み合わせを答える
out.println(dp[N][0]);
out.close();
}
}
DPに見えてからはそんなに詰まることなく解けました。
E - Tangency of Cuboids
問題文はこちら
公式解説の通りに実装しました。
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、座標の受け取り
int N = sc.nextInt();
int[][] p = sc.nextInt(N,6);
//各小立方体がどの直方体に属するか記録する(何にも属していないなら-1)
int[][][] grid = new int[101][101][101];
for(int[][] temp:grid)
for(int[] sub:temp)
Arrays.fill(sub,-1);
for(int num=0;num<N;num++)
for(int i=p[num][0];i<p[num][3];i++)
for(int j=p[num][1];j<p[num][4];j++)
for(int k=p[num][2];k<p[num][5];k++)
grid[i][j][k] = num;
//隣り合っているものを記録
ArrayList<HashSet<Integer>> ans = new ArrayList<>();
for(int i=0;i<N;i++)
ans.add(new HashSet<>());
for(int i=0;i<101;i++){
for(int j=0;j<101;j++){
for(int k=0;k<101;k++){
if(grid[i][j][k]==-1)
continue;
if(i<100&&grid[i][j][k]!=grid[i+1][j][k]&&grid[i+1][j][k]>-1){
ans.get(grid[i][j][k]).add(grid[i+1][j][k]);
ans.get(grid[i+1][j][k]).add(grid[i][j][k]);
}
if(j<100&&grid[i][j][k]!=grid[i][j+1][k]&&grid[i][j+1][k]>-1){
ans.get(grid[i][j][k]).add(grid[i][j+1][k]);
ans.get(grid[i][j+1][k]).add(grid[i][j][k]);
}
if(k<100&&grid[i][j][k]!=grid[i][j][k+1]&&grid[i][j][k+1]>-1){
ans.get(grid[i][j][k]).add(grid[i][j][k+1]);
ans.get(grid[i][j][k+1]).add(grid[i][j][k]);
}
}
}
}
//隣り合っている直方体の種類数を答える
for(HashSet<Integer> set:ans)
out.println(set.size());
out.close();
}
}
言われれば確かにそうなんですけど、気付かなかったな…。
F - Cans and Openers
問題文はこちら
最初缶切りを使わないでの最大値を求め、一番有用な缶切りを一つ使っては缶切りを使わないといけない缶で、缶切りを使わなくても良いものを置き換えることを繰り返して、最大値を求めました。
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の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//缶切りを使わないもの、使うもの、缶切りを別々に記録
ArrayList<Long> goodCan = new ArrayList<>();
ArrayList<Long> badCan = new ArrayList<>();
ArrayList<Long> tool = new ArrayList<>();
for(int i=0;i<N;i++){
int T = sc.nextInt();
long X = sc.nextInt();
if(T==0)
goodCan.add(X);
if(T==1)
badCan.add(X);
if(T==2)
tool.add(X);
}
//ソート
Collections.sort(goodCan);
Collections.sort(badCan);
Collections.sort(tool);
//現状の満足度
long ans = 0;
//今選んでいる個数
int now = 0;
//現状開封可能な個数
long canOpen = 0;
//便宜上今見ているもののインデックスを別変数に
int indexG = goodCan.size()-1;
int indexB = badCan.size()-1;
int indexT = tool.size()-1;
//缶切りを使わなくて良い物を開けられるだけ開ける
while(now<M&&0<=indexG){
ans += goodCan.get(indexG--);
now++;
}
//もしまだ選べるなら缶切り一個とそれで空けられる缶を選べるだけ選ぶ
while(now<M&&0<=indexT){
canOpen += tool.get(indexT--);
now++;
while(now<M&&0<=indexB&&0<canOpen){
ans += badCan.get(indexB--);
now++;
canOpen--;
}
}
indexG++;
long max = ans; //今を最大値として記録
while(true){
//今缶を開けられる状態で、缶切りが必要なものの方が良いなら必要無いもので一番満足度が低いものを入れ替え
while(0<canOpen&&indexG<goodCan.size()&&0<=indexB){
ans += badCan.get(indexB--)-goodCan.get(indexG++);
max = Math.max(ans,max);
canOpen--;
}
//もし缶切りが必要無いものをもう選んでいないなら探索してもしょうがないので抜ける
if(indexG>=goodCan.size())
break;
//缶切りが必要無いもので一番満足度が低いものと缶切りを交換
ans -= goodCan.get(indexG++);
if(indexT<0)
break; //缶切りの残量が無いならどうしようもないので抜ける
canOpen += tool.get(indexT--);
}
//探索して最大だったものを答える
out.println(max);
out.close();
}
}
缶切りを使ってるのにその個数を足し忘れたり使えないのに間違って足したりしてペナ出したのが悲しい…。
感想
A,B:ちょっとめんどくさいけど易しい
C:探索範囲を間違ったのが心残り…
D:サクッとできた
E:何もわからなかった…
F:貪欲で良いのはすぐ気付いたけど実装に手こずった…
って感じでした。
ちょっとずつ青に近づいているものの、なんかもったいないペナを出しまくってる気がします…。