はじめに
今回はAからDまで解けたのでそれと、コンテスト後に解いたEを載せようと思います。
では、見ていきましょう。
A - Swap Odd and Even
問題文はこちら
問題文の通りに実装しましょう。
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の受け取り
char[] S = sc.nextCharArray();
//問題文の通り、交換する
for(int i=1;i<=S.length/2;i++){
char c = S[2*i-2];
S[2*i-2] = S[2*i-1];
S[2*i-1] = c;
}
//出力
out.println(S);
out.close();
}
}
特に難しくは無いですね。
B - Call the ID Number
問題文はこちら
これもシミュレーションしていけば良いですね。
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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//呼び出されたか管理する用
boolean[] isCalled = new boolean[N];
//問題文の行動をシミュレーション
for(int i=0;i<N;i++){
if(isCalled[i])
continue;
isCalled[A[i]-1] = true;
}
//呼ばれていない人を数える
int count = 0;
for(int i=0;i<N;i++)
if(!isCalled[i])
count++;
//呼ばれていない人を順に格納する
int[] ans = new int[count];
int index = 0;
for(int i=0;i<N;i++)
if(!isCalled[i])
ans[index++] = i+1;
//人数とそれぞれの番号を出力
out.println(count);
out.println(ans," ");
out.close();
}
}
普段より易しい？
C - Make Takahashi Happy
問題文はこちら
bit全探索で解きました。
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、Aの受け取り
int H = sc.nextInt();
int W = sc.nextInt();
int[][] A = sc.nextInt(H,W);
//答え用変数
int ans = 0;
//bit全探索
for(int i=0;i<1<<(H+W-2);i++){
//1の数がH-1個じゃないなら弾く
if(Integer.bitCount(i)!=H-1)
continue;
//座標
int x = 0;
int y = 0;
//重複管理用Set
HashSet<Integer> set = new HashSet<>();
set.add(A[0][0]);
//重複が無かったか確認するようの変数
boolean isGood = true;
for(int j=1;j<1<<(H+W-2);j<<=1){
//遷移
if((i&j)>0)
x++;
else
y++;
//移動先の数値をsetに追加
isGood &= set.add(A[x][y]);
}
//重複してなかったら加算
if(isGood)
ans++;
}
//答えの出力
out.println(ans);
out.close();
}
}
最初$H$個$1$があると思って実装しちゃって手間取ってしまいました…。
D - Tying Rope
問題文はこちら
ロープ$i$の赤の端を頂点$i$、青の端を頂点$i+N$として、UnionFindを用いて解きました。
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、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//2N個の頂点を持ったUnionFind
UnionFind uf = new UnionFind(N<<1);
//同じロープ同士を繋げる
for(int i=0;i<N;i++)
uf.unite(i,i+N);
//わっかになってる個数を数える変数
int count = 0;
while(M-->0){
//A、Bとそれぞれの色の受け取り
int A = sc.nextInt()-1;
char cA = sc.nextChar();
int B = sc.nextInt()-1;
char cB = sc.nextChar();
//すでに同じ集合に属している=わっかになったので加算
if(!uf.unite(cA=='R'?A:A+N,cB=='R'?B:B+N))
count++;
}
//答えの出力
out.println(count+" "+(uf.groupCount()-count));
out.close();
}
}
今思えばわざわざ色で頂点を分ける必要は無かったですね。
E - Geometric Progression
問題文はこちら
公式解説の通りです。
E.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//A、X、Mの受け取り
int A = sc.nextInt();
long X = sc.nextLong();
int M = sc.nextInt();
long[][] mat = {
{A,1},
{0,1}
};
//行列累乗
mat = modPow(new long[][]{{0},{1}},mat,X,M);
//答えの出力
System.out.println(mat[0][0]);
}
//行列累乗メソッド
private static long[][] modPow(long[][] ans,long[][] mat,long b,long mod){
long[][] a = new long[mat.length][mat[0].length];
for(int i=0;i<mat.length;i++)
System.arraycopy(mat[i],0,a[i],0,mat[i].length);
while(0<b){
if((b&1)==1){
ans = modMultiply(a,ans,mod);
}
a = modMultiply(a,a,mod);
b >>= 1;
}
return ans;
}
//行列乗算メソッド
private static long[][] modMultiply(long[][] mat1,long[][] mat2,long mod){
if(mat1[0].length!=mat2.length)
throw new IllegalArgumentException("can't multiply mat1(len="+mat1[0].length+")by mat2(len="+mat2.length+")");
int H = mat1.length;
int W = mat2[0].length;
int len = mat2.length;
long[][] ans = new long[H][W];
for(int i=0;i<H;i++)
for(int j=0;j<W;j++)
for(int k=0;k<len;k++)
ans[i][j] = (ans[i][j]+mat1[i][k]*mat2[k][j])%mod;
return ans;
}
}
知らなかったので勉強になりました。
感想
A,B:易しい
C:bit全探索でも再帰でもいけそうだな～って思った
D:最近UnionFind使う問題増えた？
E:こんなものが…便利っすねぇ
って感じでした。
レートは上がったけど、やっぱり5完したかったなぁという気持ちが…。