はじめに
今回はコンテスト中にEまで解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - First ABC 2
問題文はこちら
StringのindexOfメソッドを使って解きました。
戻り値をそのまま答えに使いたかったので先頭に適当な文字を追加してます。
A.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、Sの受け取り(便宜上'?'を先頭に挿入)
int N = sc.nextInt();
String S = "?"+sc.next();
//"ABC"の位置を出力
out.println(S.indexOf("ABC"));
out.close();
}
}
B - Prefix and Suffix
問題文はこちら
startsWith、endsWithメソッドを使って問題文の通りに実装しました。
B.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、S、Tの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
String S = sc.next();
String T = sc.next();
boolean flag1 = T.startsWith(S); //接頭辞？
boolean flag2 = T.endsWith(S); //接尾辞？
//問題文通りに分岐
out.println(flag1&&flag2?0:flag1?1:flag2?2:3);
out.close();
}
}
C - Festival
問題文はこちら
二分探索で$i$日目以降で花火が上がる一番最寄りの日を求めました。
C.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(M);
//各日付の答えを求める
for(int i=1;i<=N;i++){
int index = Searcher.upSearch(A,i); //i以上で最小のA_indexを求める
//答えの出力
out.println(A[index]-i);
}
out.close();
}
}
普通に尺取りみたいな要領で求めることもできましたね。
C改.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(M);
//今見ているインデックス
int index = 0;
//各日付の答えを求める
for(int i=1;i<=N;i++){
//ifで良いけど念のためwhileで
while(A[index]<i)
index++;
//答えの出力
out.println(A[index]-i);
}
out.close();
}
}
D - Polyomino
問題文はこちら
再帰させながらポリオミノを置けるか全探索して調べました。
D.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );
private static boolean[][] grid = new boolean[4][4];
public static void main ( String[] args ) {
//P1、P2、P3の受け取り
char[][] P1 = sc.nextCharArray(4);
char[][] P2 = sc.nextCharArray(4);
char[][] P3 = sc.nextCharArray(4);
//再帰させてぴったりハマる置き方があるか調べる
out.println(dfs(0,P1,P2,P3)?"Yes":"No");
out.close();
}
//再帰用メソッド
private static boolean dfs(int now,char[][] P1,char[][] P2,char[][] P3){
//全部置けたら隙間が無いか調べる
if(now==3){
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(!grid[i][j])
return false;
return true;
}
//便宜上今置きたいポリオミノを別変数へ
char[][] P = now==0?P1:now==1?P2:P3;
//今のグリッドの状態を別変数に保存
final boolean[][] subGrid = new boolean[4][4];
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
subGrid[i][j] = grid[i][j];
//回転させる回数
for(int s=0;s<4;s++){
//上から何マス目か
for(int i=-3;i<4;i++){
//左から何マス目か
Loop:for(int j=-3;j<4;j++){
//グリッドを初期状態にリセットしておく
for(int k=0;k<4;k++)
for(int l=0;l<4;l++)
grid[k][l] = subGrid[k][l];
//ポリオミノが置けるか調べる
for(int k=0;k<4;k++){
for(int l=0;l<4;l++){
//今見ている箇所がグリッド外の場合
if((!MathFunction.rangeCheck(i+k,0,4)||!MathFunction.rangeCheck(j+l,0,4))){
//もしグリッド外に#が来てしまったら置けないので探索し直し
if(P[k][l]=='#')
continue Loop;
//.ならばスルー
continue;
}
//この位置のグリッドにすでに#が置かれている場合
if(grid[i+k][j+l]){
//もしこのポリオミノと重なってしまうなら探索し直し
if(P[k][l]=='#')
continue Loop;
}
//置けそうで、かつ見ている位置が#ならばそれで更新しておく
else if(P[k][l]=='#')
grid[i+k][j+l] = true;
}
}
//上記の二重forを抜けた=置くことができたので次のポリオミノを置けるか調べる
if(dfs(now+1,P1,P2,P3))
return true; //もし置けたらさっさと再帰を抜ける
}
}
//90度回転させる
P = ArrayFunction.rotateR(P);
}
//ここまで来てしまったら置けなかったということなので、falseを返す
return false;
}
}
gridの初期化位置をforの外側に書いてしまってペナルティを頂いてしまいました…。ほんと詰めが甘い…。
E - Product Development
問題文はこちら
各パラメーターを保持したクラスをkey、そのパラメータになるのにかかる最小コストをvalueとして遷移させました。
E.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、K、P、C、Aの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
int P = sc.nextInt();
int[][] A = new int[N][];
int[] C = new int[N];
for(int i=0;i<N;i++){
C[i] = sc.nextInt();
A[i] = sc.nextInt(K);
}
//パラメーターを管理するクラスの定義
class Param{
int[] p;
Param(int k){
p = new int[k];
}
//ハッシュ値はパラメーターをP+1進数として解釈した値にする
//制約上、これで同一パラメーター以外は一致しなくなる
public int hashCode(){
int sum = 0;
for(int num:p)
sum = sum*(P+1)+num;
return sum;
}
//HashMapでこれが呼び出されるのはハッシュ値が一致したときだけなのでtrueをさっさと返してしまう
@Override
public boolean equals(Object o){
if(o instanceof Param pr)
return true;
return false;
}
}
//パラメーターをkey、コストをvalueとしたMap
HashMap<Param,Long> map = new HashMap<>();
//初期値をput
map.put(new Param(K),0L);
//遷移
for(int i=0;i<N;i++){
//次の状態を保持する用のMap
HashMap<Param,Long> next = new HashMap<>(map);
for(Map.Entry<Param,Long> entry:map.entrySet()){
//i番目の開発案を選択したときのパラメーター値とコストでMapを更新
Param p = new Param(K);
Param bef = entry.getKey();
long cost = entry.getValue();
for(int j=0;j<K;j++)
p.p[j] = Math.min(P,bef.p[j]+A[i][j]);
next.merge(p,cost+C[i],Long::min);
}
map = next;
}
//目標となるパラメーターになっているもののコストを取り出す(無ければ-1を)
Param ans = new Param(K);
Arrays.fill(ans.p,P);
out.println(map.getOrDefault(ans,-1L));
out.close();
}
}
hashCodeメソッドで使った値をインデックスとした配列を用いればもう少し処理が軽くなります。
E改.java
final class Main {
private static final boolean autoFlush = false;
private static final SimpleScanner sc = new SimpleScanner( System.in );
private static final SimpleWriter out = new SimpleWriter( System.out, autoFlush );
public static void main ( String[] args ) {
//N、K、Pの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
int P = sc.nextInt();
//パラメーターの状態数を求めておく
int len = (int)MathFunction.pow(P+1,K);
//最大値(念のため半分にしておく)
long max = Long.MAX_VALUE>>1;
//コストを保持する配列
long[] dp = new long[len];
//遷移のための別配列
long[] next = new long[len];
//初期化
Arrays.fill(dp,max);
dp[0] = 0;
//現在到達済みの状態を表すintを管理するSet
IntegerSet set = new IntegerSet();
set.add(0);
//遷移
while(N-->0){
//C、Aの受け取り
int C = sc.nextInt();
int[] A = sc.nextInt(K);
//遷移先を予め初期化
Arrays.fill(next,max);
for(int num:set.toArray()){
//遷移後の状態を表すintを求める
int nextNum = 0;
int mult = 1;
int bef = num;
for(int i=K-1;i>=0;i--){
int m = num%(P+1);
num /= P+1;
nextNum += mult*Math.min(P,m+A[i]);
mult *= P+1;
}
//setに入れる
set.add(nextNum);
//コストの最小値の更新
next[nextNum] = MathFunction.min(next[nextNum],dp[nextNum],dp[bef]+C);
next[bef] = Math.min(next[bef],dp[bef]);
}
//配列を使い回すために交換する
var temp = dp;
dp = next;
next = temp;
}
//答えとなる状態のコストを答える(到達できてなかったら-1)
out.println(dp[len-1]==max?-1:dp[len-1]);
out.close();
}
}
最初このhashCodeメソッドを雑にパラメーターの和にしてしまったせいで衝突しまくってTLEしてしまいました…。ちゃんと考えて実装しようね…。
感想
A,B,C:易しい
D:ちょっとめんどくさい
E:比較的簡単め？
って感じでした。
なんというか、全体的に詰めが甘いというか…そんな感じでした…。