はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでFまで載せようと思います。
なお、僕のライブラリについては提出結果をご確認ください。
では、見ていきましょう。
A - Capitalized?
問題文はこちら
char型では'Z'<'a'なので、一文字目はこの判定で、以降はtoLowerCaseメソッドを用いて比較しました。
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の受け取り
String S = sc.next();
//チェック
out.println(S.charAt(0)<'a'&&S.substring(1).equals(S.substring(1).toLowerCase())?"Yes":"No");
out.close();
}
}
B - Frequency
問題文はこちら
HashMap<Character,Integer>を用いて各文字の個数を数えて、答えを全探索しました。
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){
//各文字の出現回数を調べる
HashMap<Character,Integer> map = new HashMap<>();
for(char c:sc.nextCharArray())
map.merge(c,1,Integer::sum);
//一番多いアルファベット順で一番先のものを探す
int max = 0;
char c = 0;
for(int i=0;i<26;i++)
if(max<map.getOrDefault((char)(i+'a'),0)){
c = (char)(i+'a');
max = map.getOrDefault(c,0);
}
//出力
out.println(c);
out.close();
}
}
C - Leftover Recipes
問題文はこちら
制約から、料理Aは最大でも$10^6$個しか作れないので、料理Aを何人分作るかを全探索することで求めることができます。
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、Q、A、Bの受け取り
int N = sc.nextInt();
int[] Q = sc.nextInt(N);
int[] A = sc.nextInt(N);
int[] B = sc.nextInt(N);
//全探索
int ans = 0;
int now = 0;
Loop:while(true){
int min = Integer.MAX_VALUE;
//Bを最大何人分作れるか調べる
for(int i=0;i<N;i++){
if(Q[i]<A[i]*now) //Aをnow人分作れないならループを抜ける
break Loop;
min = Math.min(B[i]>0?(Q[i]-A[i]*now)/B[i]:min,min);
}
ans = Math.max(now+min,ans);
now++;
}
//最大値を出力
out.println(ans);
out.close();
}
}
D - Island Tour
問題文はこちら
先に島$1$と島$N$を結ぶ橋を封鎖した時の解を求めておき、$1$本目の橋を封鎖したとき、$2$本目の橋を封鎖したとき、のように封鎖する橋をずらしていくと解は全体として$O(M)$で求まるので、十分高速に全探索が行えます。
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、M、Xの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] X = sc.nextInt(M);
//どの島からどの島へ移動しているか記録
ArrayList<ArrayList<Integer>> path = new ArrayList<>();
for(int i=0;i<=N;i++)
path.add(new ArrayList<>());
for(int i=1;i<M;i++){
path.get(X[i]).add(X[i-1]);
path.get(X[i-1]).add(X[i]);
}
//N本目の橋を封鎖した答えを求める
long ans = 0;
for(int i=1;i<M;i++)
ans += Math.abs(X[i-1]-X[i]);
//封鎖する橋をずらしながら調べる
long now = ans;
for(int i=1;i<=N;i++){
for(int p:path.get(i)){
if(p<i)
now += (i-p)-(N-i+p);
else
now += (N-p+i)-(p-i);
}
ans = Math.min(ans,now);
}
//出力
out.println(ans);
out.close();
}
}
実装に時間かけてしまいました…。
E - Chords
問題文はこちら
便宜上$A<B$とします。
着目している点から伸びている弦を考えた時(以降接続先を$B$とします)、その点よりも番号が小さい点から$B$よりも小さい番号の点に伸びていれば、これは交差していると考えることができます。ですので、点$1$から順に見ていき、これまで見てきた接続先で一番小さい番号よりも、今見ている点の接続先の中で一番番号が大きい点の方が番号が大きければYesを出力するように実装すれば良いです。
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の受け取り
int N = sc.nextInt();
//A<Bとして、どの点と結ばれているかを記録する
ArrayList<TreeSet<Integer>> list = new ArrayList<>();
for(int i=0;i<=2*N;i++)
list.add(new TreeSet<>());
for(int i=0;i<N;i++){
int A = sc.nextInt();
int B = sc.nextInt();
if(A>B){ //xor swap
A ^= B;
B ^= A;
A ^= B;
}
list.get(A).add(B);
}
//これまで見てきた点の接続先を記録するSet
TreeSet<Integer> set = new TreeSet<>(list.get(1));
for(int i=2;i<=2*N;i++){
set.remove(i); //自分が接続先だった弦は省く
//交差判定
if(set.size()>0&&list.get(i).size()>0&&set.first()<list.get(i).last()){
System.out.println("Yes");
return;
}
//自分の接続先を記録
set.addAll(list.get(i));
}
//ここまできた=交差してなかったのでNo
out.println("No");
out.close();
}
}
F - Negative Traveling Salesman
問題文はこちら
公式解説の通りです。
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、M、辺の受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[][] path = sc.nextInt(M,3);
//全頂点を始点としたベルマンフォード法
long[][] cost = new long[N][N];
long MAX = 1_000_000_000_000_000_000L;
for(int i=0;i<N;i++){
Arrays.fill(cost[i],MAX);
cost[i][i] = 0;
for(int j=0;j<N;j++)
for(int k=0;k<M;k++)
if(cost[i][path[k][0]-1]<MAX)
cost[i][path[k][1]-1] = Math.min(
cost[i][path[k][1]-1],
cost[i][path[k][0]-1]+path[k][2]);
}
//全頂点を始点とした巡回セールスマン問題へ帰着
long[][] dp = new long[1<<N][N];
for(long[] temp:dp)
Arrays.fill(temp,MAX);
for(int i=0;i<N;i++)
dp[1<<i][i] = 0;
for(int j=0;j<1<<N;j++){
for(int k=0;k<N;k++){
for(int l=0;l<N;l++){
if((j&(1<<k))>0 && (j&(1<<l))==0 && dp[j][k]<MAX && cost[k][l]<MAX){
int next = j|(1<<l);
dp[next][l] = Math.min(dp[next][l],dp[j][k]+cost[k][l]);
}
}
}
}
//最小のものを探す
long ans = MAX;
for(int j=0;j<N;j++)
ans = Math.min(ans,dp[(1<<N)-1][j]);
//答えの出力
out.println(ans==MAX?"No":ans);
out.close();
}
}
dp[1<<i][i] = 0を最初に一括でやって良いと気付かなくて、開始位置毎にDPをしたためにTLEしてそれ以上考察が進むこともなく終わってしまった…。
感想
A,B,C:易しい
D:ちょっと実装に手間取った
E:Dよりは速く書けた
F:もっとしっかり詰めて考えるべきだった…
って感じでした。
青には戻って来れましたが、維持出来るかどうか…。