はじめに
今回はコンテスト中にEまで解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Full Moon
問題文はこちら
一回以上見られるかどうかで場合分けして解きました。
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 ) {
//N、M、Pの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int P = sc.nextInt();
//場合分けして求める
out.println(N>=M?(N-M)/P+1:0);
out.close();
}
}
最初場合分けしなくても良いと思っててサンプル合わなくて混乱してました…。
B - Overlapping sheets
問題文はこちら
愚直に覆われている小領域の座標をHashSetに追加していくことで解きました。
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の受け取り
int N = sc.nextInt();
//小領域列挙用のSet
HashSet<Point> set = new HashSet<>();
//N個読み込む
while(N-->0){
//A、B、C、Dの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
int D = sc.nextInt();
//各座標を列挙してsetに追加する
for(int i=A;i<B;i++){
for(int j=C;j<D;j++){
set.add(new Point(i,j));
}
}
}
//覆われた小領域の個数=面積
out.println(set.size());
out.close();
}
}
これはそこまで躓かなかったですね。
C - Blue Spring
問題文はこちら
購入する1日周遊パスのセット数を全探索することで解きました。
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、D、P、Fの受け取り
int N = sc.nextInt();
int D = sc.nextInt();
int P = sc.nextInt();
int[] F = sc.nextInt(N);
//Fの総和を求めておく
long min = MathFunction.sum(F);
//ソート
Arrays.sort(F);
//購入するセット数の全探索をしながら最小値を求める
long now = min;
int index = N-1; //次周回パスで代替する運賃のインデックス
while(0<=index){
int d = D;
now += P; //1セット購入する
while(0<=index&&d-->0)
now -= F[index--]; //代替できるだけ代替する
min = Math.min(min,now); //今の購入数での金額で最小値を更新
}
//最終的な最小値を出力
out.println(min);
out.close();
}
}
これもそこまで悩まなかったです。
D - General Weighted Max Matching
問題文はこちら
DFSで全組み合わせを試しました。
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 );
private static long max = 0;
private static int[][] list;
public static void main ( String[] args ) {
//Nの受け取り
int N = sc.nextInt();
//隣接行列の生成
list = new int[N][N];
for(int i=0;i<N;i++)
for(int j=i+1;j<N;j++)
list[i][j] = sc.nextInt();
//探索済みか管理する用のboolean配列
boolean[] checked = new boolean[N];
//全探索
dfs(0,0,checked);
//最大値の出力
out.println(max);
out.close();
}
//全探索用メソッド(今いる頂点[now]、重みの総和[sum]、探索済みか格納している配列[checked])
private static void dfs(int now,long sum,boolean[] checked){
//今の総和で最大値を更新しておく
max = Math.max(max,sum);
//もし全部の頂点にたどり着いたなら戻る
if(now==list.length)
return;
//この頂点を通らない時の全探索
dfs(now+1,sum,checked);
//もしこの頂点を既に探索済みならこれで終わり
if(checked[now])
return;
//ここからの移動先を全探索
for(int i=now+1;i<list.length;i++){
if(!checked[i]){
checked[i] = true;
dfs(now+1,sum+list[now][i],checked);
checked[i] = false;
}
}
}
}
最初引数に全部載せたんですが手元で実行した感じ2秒をちょっと超えそうだったのでクラス変数にしてお祈りしたら通りました。
E - Sandwiches
問題文はこちら
同じ値同士の座標をListで管理して、$i$、$k$として用いられる回数を計算する方式で解きました。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//同じ値のインデックスをListに格納したものをvalueとしたmap
HashMap<Integer,ArrayList<Integer>> map = new HashMap<>();
//順に格納していく
for(int i=0;i<N;i++){
final int num = i;
map.compute(A[num],(k,v)->{
if(v==null)
v = new ArrayList<>();
v.add(num);
return v;
});
}
//組み合わせの総和を求める
long ans = 0;
for(ArrayList<Integer> list:map.values()){
for(int i=1;i<list.size();i++){
long sub = list.get(i)-list.get(i-1)-1;
ans += sub*i*(list.size()-i);
}
}
//答えのしゅつりょく
out.println(ans);
out.close();
}
}
なかなか思いつかなくて時間かけちゃいました…無念…。
感想
A,B,C:易しい
D:ちょっと手間取ったけど気付いてしまえば、って感じ
E:気付くまでに時間かけたのが心残り…
って感じでした。
ペース的にはそこまで悪くは無いですけど、もう少しスピード出したいですね…。