はじめに
今回はFまでコンテスト中に解けたので提出コードをそのまま載せようと思います。
では、見ていきましょう。
A - camel Case
問題文はこちら
A-Zは'a'よりも小さいので、aとの比較によって大文字を検出しました。
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 ) {
//Sの受け取り
String S = sc.next();
//大文字を探して添え字+1を出力
for(int i=0;i<S.length();i++)
if(S.charAt(i)<'a'){
out.println(i+1);
break;
}
out.close();
}
}
特に難しくはないですね。
B - Trimmed Mean
問題文はこちら
大きい方から、小さい方から$N$個を考える必要があるので予め$X$をソートしておいて、$N+1$から$4N$までを足して$3N$で割れば良いと思い、それを実装しました。小数で出力したいのでdoubleにキャストしました。
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、Xの受け取り
int N = sc.nextInt();
int[] X = sc.nextInt(N*5);
//Xのソート
ArrayFunction.sort(X);
//[N,4N)を加算
int sum = 0;
for(int i=N;i<4*N;i++)
sum += X[i];
//平均を取って出力
System.out.println((double)sum/(3*N));
out.close();
}
}
これもそこまで難しくはないですね。
C - LRUD Instructions 2
問題文はこちら
HashSetで一度通った場所かを管理しました。座標はPointクラスで扱ってます。
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、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//座標
int x = 0;
int y = 0;
//到達済みか管理する用のset
HashSet<Point> set = new HashSet<>();
set.add(new Point(0,0));
//被ったか確認するやつ
boolean flag = true;
//順に遷移
for(int i=0;i<N;i++){
if(S.charAt(i)=='L')
y--;
if(S.charAt(i)=='R')
y++;
if(S.charAt(i)=='U')
x++;
if(S.charAt(i)=='D')
x--;
//到達済みか確認
flag &= set.add(new Point(x,y));
}
//一回も被らなかった？
out.println(flag?"No":"Yes");
out.close();
}
}
これも思っていたよりサクッと解けました。
D - Flip Cards
問題文はこちら
動的計画法で解きました。
$\mathrm{dp}[i][j]:i$番目(0-indexed)までのカードで、$i$番目のカードが$j$が$0$なら表、$1$なら裏である時の組み合わせの数
という感じで保持し、以下のように遷移しました。
$\mathrm{dp}[i][0] += \mathrm{dp}[i-1][0]\ \ (A[i]!=A[i-1])$
$\mathrm{dp}[i][0] += \mathrm{dp}[i-1][1]\ \ (A[i]!=B[i-1])$
$\mathrm{dp}[i][1] += \mathrm{dp}[i-1][0]\ \ (B[i]!=A[i-1])$
$\mathrm{dp}[i][1] += \mathrm{dp}[i-1][1]\ \ (B[i]!=B[i-1])$
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、カードの情報の受け取り
int N = sc.nextInt();
int[][] cards = sc.nextInt(N,2);
//dp
int[][] dp = new int[N][2];
final int mod = 998244353;
dp[0][0] = dp[0][1] = 1;
//遷移
for(int i=1;i<N;i++){
dp[i][0] += cards[i][0]!=cards[i-1][0]?dp[i-1][0]:0;
dp[i][0] += cards[i][0]!=cards[i-1][1]?dp[i-1][1]:0;
dp[i][0] %= mod;
dp[i][1] += cards[i][1]!=cards[i-1][0]?dp[i-1][0]:0;
dp[i][1] += cards[i][1]!=cards[i-1][1]?dp[i-1][1]:0;
dp[i][1] %= mod;
}
//答えの出力
out.println((dp[N-1][0]+dp[N-1][1])%mod);
out.close();
}
}
思ったより発想が速くて良かったです。
E - Find Permutation
問題文はこちら
説明は公式解説に任せますが、トポロジカルソート中に入次数が$0$の頂点が$2$個以上になっていないかを確認することで一意に定まるかを確認できます。あとはソート後の順序で番号を振っていけば良いです。
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,Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//辺の受け取り
ArrayList<HashSet<Integer>> route = new ArrayList<>();
for(int i=0;i<=N;i++)
route.add(new HashSet<>());
while(M-->0){
int X = sc.nextInt();
int Y = sc.nextInt();
route.get(X).add(Y);
}
//トポロジカルソート
int[] count = new int[N+1];
int pathCount = 0;
for ( HashSet<Integer> path: route ) {
for ( int point: path ) {
pathCount++;
count[point]++;
}
}
ArrayDeque<Integer> deq = new ArrayDeque<>();
for ( int i = 1; i < count.length; i++ ) {
if ( count[i] == 0 ) {
deq.add( i );
}
}
//入次数が0のものが複数あるならNo
if(deq.size()>1){
System.out.println("No");
return;
}
//答えを管理する配列
int[] ans = new int[N+1];
//1の決定
ans[deq.getFirst()] = 1;
//次の値を管理する変数
int index = 2;
while ( deq.size() > 0 ) {
int nowP = deq.pollFirst();
for ( int nextP: route.get(nowP) ) {
if ( --count[nextP] == 0 ) {
deq.add( nextP );
ans[nextP] = index++;
}
}
//入次数が0のものが2以上ならNo
if(deq.size()>1){
System.out.println("No");
return;
}
}
//最後まで出来たならYes
out.println("Yes");
//答えの出力
for(int i=1;i<=N;i++)
out.print(ans[i]+" ");
out.println();
out.close();
}
}
トポロジカルソートはこの前ライブラリに書いたばっかりだったので助かりました。
F - Teleporter and Closed off
問題文はこちら
都市$k$を通らないような最短を求めるのに、$k$の前後の両端までの最短距離さえわかっていれば良さそうだと思い、両端からの距離を先に求めて、あとは各$k$に対して$k$近傍を調べることで答えを求めました。
F.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、Sの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
char[][] S = sc.nextCharArray(N);
//Nまでの距離
int[] minDist1 = new int[N+1];
final int max = N<<1;
Arrays.fill(minDist1,max);
minDist1[N] = 0;
for(int i=N-1;i>0;i--){
for(int j=0;j<M;j++){
if(S[i-1][j]=='1'){
minDist1[i] = Math.min(minDist1[i],minDist1[i+j+1]+1);
}
}
}
//1からの距離
int[] minDist2 = new int[N+1];
Arrays.fill(minDist2,max);
minDist2[1] = 0;
for(int i=1;i<N;i++){
for(int j=0;j<M;j++){
if(S[i-1][j]=='1'){
minDist2[i+j+1] = Math.min(minDist2[i+j+1],minDist2[i]+1);
}
}
}
//各kを通らないときの最短を求める
for(int i=2;i<N;i++){
int ans = max;
for(int j=Math.max(i-M+1,1);j<i;j++){
for(int k=Math.max(1,i-j+1);k<=M;k++){
if(S[j-1][k-1]=='1'){
ans = Math.min(ans,minDist2[j]+minDist1[j+k]+1);
}
}
}
//答えの出力(max以上ならkを通らないといけないので-1)
out.print(ans>=max?-1:ans);
out.print(" ");
}
out.println();
out.close();
}
}
気づけるまで時間かかっちゃいましたけど、なんとか解けました。
感想
A,B,C:易しい
D:典型っぽい？
E:最近やったばかりなので割と速く気づけた
F:典型らしい…気づくのにかなり時間かかってしまった…
って感じでした。
初めて6完できて良かったです。水にも戻れて良かったです。