はじめに
今回はコンテスト中にEまで解けたのでそのコードをそのまま載せようと思います。
なお、自作ライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Potions
問題文はこちら
$P_i \lt P_{i+1}$なので、受け取ってそのまま二分探索して答えを求めました。
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、H、X、Pの受け取り
int N = sc.nextInt();
int H = sc.nextInt();
int X = sc.nextInt();
int[] P = sc.nextInt(N);
//二分探索して1-indexedに直して出力
int index = Searcher.upSearch(P,X-H);
out.println(index+1);
out.close();
}
}
普通に先頭から見ても良いかと思います。
A改.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、H、Xの受け取り
int N = sc.nextInt();
int H = sc.nextInt();
int X = sc.nextInt();
//順にPを受け取って条件を満たす境界を求める
for(int i=1;i<=N;i++){
int P = sc.nextInt();
if(X<=H+P){
System.out.println(i);
break;
}
}
}
}
B - MissingNo.
問題文はこちら
TreeSetに$A$を入れて先頭を取り出しておいて、$A_i+1<A_{i+1}$となるような箇所を探しました。
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();
//AをSetに突っ込む
TreeSet<Integer> set = new TreeSet<>();
while(N-->0){
int A = sc.nextInt();
set.add(A);
}
//不連続な箇所を求める
int ans = set.pollFirst();
while(ans+1==set.first())
ans = set.pollFirst();
//抜けている数字を出力
System.out.println(ans+1);
out.close();
}
}
先頭を取り出して良いのは、「なくした整数は一意に定まる」と制約にあるからで、先頭、末尾のどちらかをなくした場合を考えなくて良いからです(一意に定まらないので)。
C - Remembering the Days
問題文はこちら
DFSで最大値を求めました。
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 );
//最大値と到達済みの頂点を管理するSetはクラス変数に
private static int max = 0;
private static HashSet<Integer> set;
public static void main ( String[] args ) {
//N、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//隣接リストの構築
ArrayList<ArrayList<int[]>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
while(M-->0){
//A、B、Cの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
int C = sc.nextInt();
//[0]に行き先、[1]に長さを記録
list.get(A).add(new int[]{B,C});
list.get(B).add(new int[]{A,C});
}
//各頂点を始点にしてDFS
set = new HashSet<>();
for(int i=1;i<=N;i++){
set.add(i); //探索済みに
dfs(i,0,list); //DFS
set.remove(i); //探索済みを解除
}
//最大値を出力
out.println(max);
out.close();
}
//DFS用メソッド(今いる街がnow、距離の総和がsum、隣接リストがlist)
private static final void dfs(int now,int sum,ArrayList<ArrayList<int[]>> list){
//最高値を記録
max = Math.max(max,sum);
//この街から移動できる街を調べる
for(int[] next:list.get(now)){
//addメソッドがtrueを返すなら
//setの中にnext[0]が無かった=未探索
//なので、next[0]に遷移する
if(set.add(next[0])){
dfs(next[0],sum+next[1],list); //DFS
set.remove(next[0]); //nowに戻ってきたのでnext[0]を未探索に直す
}
}
}
}
ちょっと時間をかけてしまいました…。
D - President
問題文はこちら
DPで解きました。
$\sum^N_{i=1}{Z} \le 10^5$より、$\mathrm{dp}[i]$を$i$議席獲得するのに鞍替えさせる必要がある最小人数としてDPテーブルを埋めて求めました。
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 ) {
//N、X、Y、Zの受け取り
int N = sc.nextInt();
int[][] XYZ = sc.nextInt(N,3);
//sum(Z)を求める
int sum = 0;
for(int i=0;i<N;i++){
sum += XYZ[i][2];
}
//DP
long[] dp = new long[sum+1];
Arrays.fill(dp,Long.MAX_VALUE>>1);
dp[0] = 0;
//遷移
for(int i=0;i<N;i++){
int cost = (XYZ[i][0]+XYZ[i][1]+1)/2-XYZ[i][0];
if(cost<=0){
for(int j=sum;j>=XYZ[i][2];j--)
dp[j] = Math.min(dp[j],dp[j-XYZ[i][2]]);
}
else{
for(int j=sum;j>=XYZ[i][2];j--)
dp[j] = Math.min(dp[j],dp[j-XYZ[i][2]]+cost);
}
}
//過半数以上の議席における最小人数を求める
long min = dp[sum+1>>1];
for(int i=sum+1>>1;i<=sum;i++)
min = Math.min(min,dp[i]);
//答えの出力
out.println(min);
out.close();
}
}
最初嘘貪欲を投げてしまって1ペナ…もっと考えようね…
E - Avoid Eye Contact
問題文はこちら
先に上下左右それぞれを向いている人の視線に入っているマスを求めておいてBFSをしました。
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 ) {
//H、W、Aの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
char[][] A = sc.nextCharArray(H);
//見られているマスと始点、終点を求める
boolean[][] lookUp = new boolean[H][W];
int Sx = -1;
int Sy = -1;
int Gx = -1;
int Gy = -1;
for(int i=0;i<H;i++){
boolean flag = false;
for(int j=0;j<W;j++){
if(A[i][j]=='>')
flag = true;
else if(A[i][j]!='.')
flag = false;
lookUp[i][j] |= flag;
if(A[i][j]=='S'){
Sx = i;
Sy = j;
}
if(A[i][j]=='G'){
Gx = i;
Gy = j;
}
}
}
for(int i=0;i<H;i++){
boolean flag = false;
for(int j=W-1;j>=0;j--){
if(A[i][j]=='<')
flag = true;
else if(A[i][j]!='.')
flag = false;
lookUp[i][j] |= flag;
}
}
for(int i=0;i<W;i++){
boolean flag = false;
for(int j=0;j<H;j++){
if(A[j][i]=='v')
flag = true;
else if(A[j][i]!='.')
flag = false;
lookUp[j][i] |= flag;
}
}
for(int i=0;i<W;i++){
boolean flag = false;
for(int j=H-1;j>=0;j--){
if(A[j][i]=='^')
flag = true;
else if(A[j][i]!='.')
flag = false;
lookUp[j][i] |= flag;
}
}
//BFS
ArrayDeque<Integer> deq = new ArrayDeque<>();
deq.add(Sx);
deq.add(Sy);
int[][] dist = new int[H][W];
for(int i=0;i<H;i++)
Arrays.fill(dist[i],Integer.MAX_VALUE);
dist[Sx][Sy] = 0;
int[] dx = {1,-1,0,0};
int[] dy = {0,0,1,-1};
while(deq.size()>0){
int nowX = deq.pollFirst();
int nowY = deq.pollFirst();
for(int i=0;i<4;i++){
int nx = nowX+dx[i];
int ny = nowY+dy[i];
if(nx<0||ny<0||H<=nx||W<=ny)
continue;
if(A[nx][ny]!='.'&&A[nx][ny]!='G'||lookUp[nx][ny])
continue;
if(dist[nowX][nowY]+1<dist[nx][ny]){
dist[nx][ny] = dist[nowX][nowY]+1;
deq.add(nx);
deq.add(ny);
}
}
}
//到達可能ならそのコストを、無理なら-1を出力
out.println(dist[Gx][Gy]!=Integer.MAX_VALUE?dist[Gx][Gy]:-1);
out.close();
}
}
これは割とすぐ気づけました。
感想
A,B:易しい
C:ちょっと悩んでしまった…不覚！
D:DPであることをもっと早く気づきべきだった…
E:自分にしては早く気づけたので良かった
って感じでした。
楽にやろうとしてペナ出すのが最近増えてしまった気がします…もったいないの極み…。