はじめに
今回はコンテスト中にEまで、コンテスト後にFまで解けたのでFまで載せようと思います。
では、見ていきましょう。
なお、ライブラリは提出結果よりご覧ください。
A - Water Station
問題文はこちら
前後の地点を求めて近い方を出力しました。
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の受け取り
int N = sc.nextInt();
//前後の地点を求める
int a = N/5*5;
int b = (N+4)/5*5; //雑だったので地点ぴったりの時はa==bになっちゃってる。問題は無いけど
//最寄りの出力
out.println(Math.abs(a-N)<Math.abs(N-b)?a:b);
out.close();
}
}
今思えば普通に(N+2)/5*5で良かったなと思いました。
B - ABCDEFG
問題文はこちら
コンテスト後に書いた物ですが、事前にAから何個目の地点かを求めておいて、Aからの距離を予め求めた配列を使って距離を求めました。
B.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//p,qのAからの距離を求める
int p = sc.next().charAt(0)-'A';
int q = sc.next().charAt(0)-'A';
//Aからの距離を求めておいた配列
int[] point = {0,3,4,8,9,14,23};
//差の出力
System.out.println(Math.abs(point[p]-point[q]));
}
}
コンテスト中は焦って全通り書いてました…。
C - Snuke the Cookie Picker
問題文はこちら
問題文の$a,b,c,d$を求めて、その範囲内で.の座標を求めることで解きました。
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 ) {
//H、W、Sの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
char[][] S = sc.nextCharArray(H);
//a、b、c、dの探索
int a=H,b=0,c=W,d=0;
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
if(S[i][j]=='#'){
a = Math.min(a,i);
c = Math.min(c,j);
b = Math.max(b,i);
d = Math.max(d,j);
}
}
}
//i=a~b、j=c~dで.の地点を探して出力
for(int i=a;i<=b;i++){
for(int j=c;j<=d;j++){
if(S[i][j]=='.')
out.println((i+1)+" "+(j+1));
}
}
out.close();
}
}
比較的早く思いつけたので良かったです。
D - Sleep Log
問題文はこちら
コンテスト後に書いた物ですが、時間$t$に対して、0分から$t$分までで寝た時間を返すメソッドを作って累積和的な要領で解きました。
※下のコードは入出力高速化を行なっていないので結構ギリギリです(提出したら2646msだった)。
D.java
import java.util.Scanner;
import java.util.TreeMap;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、Aの受け取り
int N = sc.nextInt();
int[] A = new int[N];
for(int i=0;i<N;i++)
A[i] = sc.nextInt();
//累積和準備
initialize(A);
//各問いに答える
int Q = sc.nextInt();
while(Q-->0){
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(get(r)-get(l));
}
}
//getメソッド用の事前構築
private static void initialize(int[] A){
sum.put(0,0);
sTime.put(0,0);
int num = 0;
for(int i=1;i<A.length;i+=2){
sum.put(A[i],num);
num += A[i+1]-A[i];
sum.put(A[i+1],num);
sTime.put(A[i],A[i+1]);
sTime.put(A[i+1],A[i+1]);
}
}
//keyまでの累積和をvalueにしたmap
static TreeMap<Integer,Integer> sum = new TreeMap<>();
//寝始めた時間と起きた時間の組になってる(便宜上起きた時間と起きた時間の組も入れてる)
static TreeMap<Integer,Integer> sTime = new TreeMap<>();
//t分までの寝た時間を返すメソッド
private static int get(int t){
//累積和のmapから求める
int ans = sum.get(sum.floorKey(t));
//寝始めた時間と起きた時間の間にtがあるとき用
int last = sTime.floorKey(t);
//端数調整して返す
return ans+Math.min(sTime.get(last),t)-last;
}
}
本番中はごちゃごちゃ書いてバグらせてしまってめちゃくちゃ時間かけてしまいました…。弱さを実感しました…。
E - Art Gallery on Graph
問題文はこちら
ダイクストラ法で解きました。
距離ではなく、今残っている体力を基準に優先度を付けて上げることで適切に処理できます。
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、N、K、グラフの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int K = sc.nextInt();
int[][] graph = sc.nextGraph(N,M); //1-indexedの隣接リスト
//地点iに行ったときの最大残り体力を管理する配列
int[] dist = new int[N+1];
//到達可能かを記録する配列(無くても良い)
boolean[] canGo = new boolean[N+1];
//初期値代入
Arrays.fill(dist,-1);
//警備員の情報の受け取り
int[][] person = sc.nextInt(K,2);
//ダイクストラ用queue
PriorityQueue<Pair<Integer,Integer>> queue = new PriorityQueue<>();
//各警備員をqueueに入れると共に情報の更新
for(int[] p:person){
queue.add(new Pair<>(-p[1],p[0]));
canGo[p[0]] = true;
dist[p[0]] = p[1];
}
//ダイクストラ
while(queue.size()>0){
Pair<Integer,Integer> pair = queue.poll();
int now = pair.getValue();
int h = -pair.getKey();
for(int next:graph[now]){
if(dist[now]-1>dist[next]){
dist[next] = h-1;
canGo[next] = true;
if(h>1)
queue.add(new Pair<>(-h+1,next));
}
}
}
//行ける地点のカウント
int count = 0;
for(boolean flag:canGo)
if(flag)
count++;
//個数の出力
out.println(count);
//行ける地点を配列に入れる
int[] ans = new int[count];
int index = 0;
for(int i=1;i<=N;i++)
if(canGo[i])
ans[index++] = i;
//答えの出力
out.println(ans);
out.close();
}
}
最初hの大きさで降順にソートしてBFSかな～とかいう甘い考えで提出してしまってTLEをいただきました。
F - Dungeon Explore
問題文はこちら
説明は公式解説に任せますが、DFSで解きました。
F.java
final class Main {
private static final boolean autoFlush = true;
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();
//探索済みの管理用配列
boolean[] checked = new boolean[N+1];
//dfs
dfs(1,checked,N);
}
//dfs(今いる頂点,探索済みか管理する配列,ゴール(=N))
private static void dfs(int now,boolean[] checked,int G){
//ゴールにたどり着いたら終了
if(now==G){
System.exit(0);
}
//探索済みに
checked[now] = true;
//今いる頂点から行ける頂点を全て探索済みか管理するフラグ
boolean flag = true;
//全部探索済みになるまで回す
while(flag){
//kと行ける頂点の受け取り
int k = sc.nextInt();
int[] next = sc.nextInt(k);
//forで更新されなかったら抜けるようにfalseに設定
flag = false;
for(int ne:next){
//重複探索は避ける
if(checked[ne])
continue;
//行ける地点があったならフラグを立てて、遷移
flag = true;
out.println(ne);
dfs(ne,checked,G);
out.println(now);
break;//入力を再度受け取る為に一旦forを抜ける
}
}
}
}
最後のOKという入力なんですけど、何故か受け取ると全ケースTLEになるので多分最後に改行が入ってないです(質問がまだ返ってきてないので僕のライブラリがバグってる可能性もまぁまぁありますが、これまでそんな事無かったのであまりそうは考えられないかなと思ってます)(回答が返ってきたら追記します)。
まぁそもそもコンテスト中は戻ってきたときに入力受け取るの忘れてたので改行があっても無くても変わらないですが…。
感想
A:ちゃんと(A+B-1)/Bの意味を理解していますか？という感じの問題だった
B:テンパってクソコードを…うぅ…
C:易しめかも
D:飛ばせば良かったか…
E:気付けばなんてことはないかも
F:DFSってのはすぐ気付けたので、易しめかも(解けなかったですけど…)
って感じでした。
レート下がってしまいましたがこれを糧に精進するしかないですね…。