はじめに
今回はコンテスト中にFまで解けたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Takahashi san
問題文はこちら
$S$を受け取って sanを付けて出力すれば良いです。
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 ) {
//Sを受け取ってsanを付けて出力
out.println(sc.next()+" san");
out.close();
}
}
久々にやるだけな問題が来たような気がします。
B - World Meeting
問題文はこちら
$N$が小さめなので開始時刻を全探索して解きました。
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、W、Xの受け取り
int N = sc.nextInt();
int[] W = new int[N];
int[] X = new int[N];
for(int i=0;i<N;i++){
W[i] = sc.nextInt();
X[i] = sc.nextInt();
}
//最大値を記録する用の変数
int max = 0;
//開始時刻全探索
for(int i=0;i<24;i++){
//総社員数を記録する用の変数
int sum = 0;
//各拠点で参加できるかを判定する
for(int j=0;j<N;j++){
if(MathFunction.rangeCheck((X[j]+i)%24,9,18))
sum += W[j];
}
//最大値の更新
max = Math.max(sum,max);
}
//答えの出力
out.println(max);
out.close();
}
}
TLで見かけましたが、確かに一日を24時間とは定義してないですね。
C - Sensors
問題文はこちら
順にマスを見ていって、#のマスで未探索ならDFSで連動しているセンサを全部探索済みにすることで重複を防ぎながら数え上げました。
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 ) {
//H、W、Sの受け取り
H = sc.nextInt();
W = sc.nextInt();
S = sc.nextCharArray(H);
//探索済みか管理する配列
boolean[][] checked = new boolean[H][W];
//個数記録用
int sum = 0;
//全マス見ていく
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
//未探索のセンサならDFSで連動しているものをチェック
if(S[i][j]=='#'&&!checked[i][j]){
sum++;
dfs(i,j,checked);
}
}
}
//答えの出力
out.println(sum);
out.close();
}
//遷移用の配列
static int[] dx = {1,1,1,-1,-1,-1,0,0};
static int[] dy = {0,-1,1,0,-1,1,-1,1};
//引数にしたくないのでここに
static int H,W;
static char[][] S;
//DFS用メソッド
private static void dfs(int x,int y,boolean[][] checked){
checked[x][y] = true;
for(int i=0;i<8;i++){
int nx = x+dx[i];
int ny = y+dy[i];
if(MathFunction.rangeCheck(nx,0,H)&&MathFunction.rangeCheck(ny,0,W)&&S[nx][ny]=='#'&&!checked[nx][ny])
dfs(nx,ny,checked);
}
}
}
なんというか…もうちょっと綺麗に書けるよう努めたいです…(一度実装してミスに気付いて全部書き直すとかやっていたのでこの有様に…)。
D - Printing Machine
問題文はこちら
$T$毎にArrayListで印字機の範囲から出る時刻を記録し、PriotityQueueに入れながら貪欲に印字することで処理しました。
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 );
public static void main ( String[] args ) {
//Nの受け取り
int N = sc.nextInt();
//T毎に記録
TreeMap<Long,ArrayList<Long>> map = new TreeMap<>();
while(N-->0){
long T = sc.nextLong();
long D = T+sc.nextLong();
if(!map.containsKey(T)){
map.put(T,new ArrayList<>());
}
map.get(T).add(D);
}
//答え用変数
int ans = 0;
//貪欲用PriorityQueue
PriorityQueue<Long> queue = new PriorityQueue<>();
//Tの小さい方から見ていく
for(Long T:map.keySet()){
//印字機の範囲に入ったので全部queueに入れる
queue.addAll(map.get(T));
//次のTになるまでは貪欲したいので次のTを求めておく(便宜上最後はLong.MAX_VALUE)
Long nextT = map.ceilingKey(T+1);
if(nextT==null)
nextT = Long.MAX_VALUE;
//時刻Tから貪欲
long bef = T;
while(queue.size()>0&&bef<nextT){
if(bef<=queue.peek()){
bef++;
ans++;
}
queue.poll();
}
}
//答えの出力
out.println(ans);
out.close();
}
}
かなり実装手こずって時間をかけてしまいました…。
E - Our clients, please wait a moment
問題文はこちら
「社用車から電車に乗り換えることはできますが、電車から社用車に乗り換えることはできません。」とあるので、社用車から電車に乗り換えるタイミングのみを考えれば良く、各都市への、都市$1$から社用車で向かった時の所要時間と都市$N$へ電車で向かった時の所要時間をダイクストラ法を用いて求めておけば答えが出せます。
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、A、B、C、Dの受け取り
int N = sc.nextInt();
long A = sc.nextInt();
long B = sc.nextInt();
long C = sc.nextInt();
int[][] D = sc.nextInt(N,N);
//都市1からかかる時間を記録する配列
long[] dist = new long[N];
//初期値代入
Arrays.fill(dist,Long.MAX_VALUE>>1);
dist[0] = 0;
//ダイクストラ用クラスとPriorityQueue
class Data{
int now;
long cost;
public Data(int n,long d){
now = n;
cost = d;
}
}
PriorityQueue<Data> queue = new PriorityQueue<>((a,b)->Long.compare(a.cost,b.cost));
//初期値代入
queue.add(new Data(0,0));
//ダイクストラ
while(queue.size()>0){
Data d = queue.poll();
int now = d.now;
long cost = d.cost;
if(dist[now]<cost)
continue;
for(int i=0;i<N;i++){
long next = D[now][i]*A+cost;
if(next<dist[i]){
dist[i] = next;
queue.add(new Data(i,next));
}
}
}
//都市Nからかかる時間を記録する配列
long[] rDist = new long[N];
//初期値代入
Arrays.fill(rDist,Long.MAX_VALUE>>1);
rDist[N-1] = 0;
queue.add(new Data(N-1,0));
//ダイクストラ
while(queue.size()>0){
Data d = queue.poll();
int now = d.now;
long cost = d.cost;
if(rDist[now]<cost)
continue;
for(int i=0;i<N;i++){
long next = D[now][i]*B+C+cost;
if(next<rDist[i]){
rDist[i] = next;
queue.add(new Data(i,next));
}
}
}
//どこで乗り換えるかを全探索
long min = Long.MAX_VALUE;
for(int i=0;i<N;i++){
min = Math.min(min,dist[i]+rDist[i]);
}
//答えの出力
out.println(min);
out.close();
}
}
これは割と早く気づけました。
F - Sensor Optimization Dilemma
問題文はこちら
動的計画法のような要領で解きました。
HashSetに、これまでの区間を監視するのに使ったセンサーの数の組み合わせを記録しておいて、次の区間に対して使うセンサーの数の組み合わせを求めてHashSetの組み合わせと合わせることで全通りを求め、最後に一番費用の少ない組み合わせを求めることで答えを求めました。
F.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、D、L1、C1、K1、L2、C2、L2の受け取り
int N = sc.nextInt();
int[] D = sc.nextInt(N);
int L1 = sc.nextInt();
int C1 = sc.nextInt();
int K1 = sc.nextInt();
int L2 = sc.nextInt();
int C2 = sc.nextInt();
int K2 = sc.nextInt();
//現在の使用した数の組み合わせを記録する用のSet
HashSet<Point> set = new HashSet<>();
//初期値を入れる
set.add(new Point(0,0));
//遷移
for(int d:D){
//この区間で使用する数の組み合わせをlistに記録
ArrayList<Point> list = new ArrayList<>();
for(int j=0;j<=K2;j++){
int i = Math.max((d+L1-1-L2*j)/L1,0);
if(MathFunction.rangeCheck(i,0,K1+1))
list.add(new Point(i,j));
if(d<=j*L2)
break;
}
//この区間までを監視できるようになるのに考えられる組み合わせをnextに入れる
HashSet<Point> next = new HashSet<>();
for(Point p:set){
for(Point np:list){
int x = p.x+np.x;
int y = p.y+np.y;
if(MathFunction.rangeCheck(x,0,K1+1)&&MathFunction.rangeCheck(y,0,K2+1))
next.add(new Point(x,y));
}
}
//setを上書き
set = next;
}
//全組み合わせで一番費用の少ない組み合わせの費用を求める
long ans = Long.MAX_VALUE;
for(Point p:set)
ans = Math.min(ans,(long)p.x*C1+(long)p.y*C2);
//答えの出力
out.println(ans==Long.MAX_VALUE?-1:ans);
out.close();
}
}
このコードだと1483msだったんですが、java.awt.Pointを使わずにx*10000+yとしたint型で処理するようにしたり自作のint用HashSetなどを用いたら440msまで高速化できました。
感想
A,B:易しい
C:ちょっと手間取った
D:かなり実装に時間をかけてしまった…
E:典型っぽい
F:イマイチわからないまま解いたような気分
って感じでした。
今回のコンテストのおかげでやっと入青です…長かった…。