はじめに
今回はコンテスト中にDまで解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - Leftrightarrow
問題文はこちら
先頭が<か、末尾が>か、=を取り除くと$2$文字になるかで判定しました。
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();
//判定
if(S.charAt(0)=='<'&&S.charAt(S.length()-1)=='>'&&S.replace("=","").length()==2)
out.println("Yes");
else
out.println("No");
out.close();
}
}
B - Integer Division Returns
問題文はこちら
Javaだと割り切れないときは0に近い方に丸められるので、正なら$9$足してから除算、負ならそのまま除算してあげれば答えが出ます。
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){
//Xの受け取り
long X = sc.nextLong();
//負だったら引きたくないので辻褄会わせをしておく
if(X<0)
X -= 9;
//切りあげ除算
out.println((X+9)/10);
out.close();
}
}
C - One Time Swap
問題文はこちら
自身と同じ文字とのswapは変化しないので、そのような組み合わせが存在するか場合分けして解きました。
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){
//Sの受け取り
String S = sc.next();
//各文字の数え上げ
HashMap<Character,Integer> map = new HashMap<>();
for(char c :S.toCharArray())
map.merge(c,1,Integer::sum);
//答えの数え上げ
long ans = 0;
boolean flag = false; //変化しない組み合わせがあったか
for(int i=0;i<S.length();i++){
int sum = map.merge(S.charAt(i),-1,Integer::sum);
ans += S.length()-i-1-sum;
flag |= sum>0;
}
//変化しない組み合わせが1つ以上あったら1追加
if(flag)
ans += 1;
//答えの出力
out.println(ans);
out.close();
}
}
D - Tiling
問題文はこちら
制約が小さいのと、タイルが長方形なので縦向きと横向きの$2$種のみ考えれば良いことから、横向きかどうかをbit全探索で、どの順番で置けば良いかを順列全探索で解きました。これは、二重forの要領で見ていって、まだ何も置かれていないマスが見つかったら貪欲に置く必要があり、正解があるなら上記の探索で正解の置き方を網羅できるので正しいです(公式解説のを平たく言い換えただけです)。
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、H、Wの受け取り
int N = sc.nextInt();
int H = sc.nextInt();
int W = sc.nextInt();
//タイルの情報を保持するクラス
class Tile{
int h,w,id;
Tile(int h,int w,int i){
this.h = h;
this.w = w;
id = i;
}
}
//タイルの情報の受け取り
Tile[] t = new Tile[N];
for(int i=0;i<N;i++)
t[i] = new Tile(sc.nextInt(),sc.nextInt(),i);
//順列全探索用
int[] mapping = new int[N];
Arrays.setAll(mapping,i->i);
//答えがあるか管理する変数
boolean check = false;
//順列全探索
do{
//bit全探索
Loop:for(int i=0;i<1<<N;i++){
boolean[][] map = new boolean[H][W];
int index = 0;
for(int j=0;j<H;j++){
for(int k=0;k<W;k++){
if(!map[j][k]){
if(index==N)
continue Loop;
int h = (i&(1<<index))>0?t[mapping[index]].h:t[mapping[index]].w;
int w = (i&(1<<index))>0?t[mapping[index]].w:t[mapping[index]].h;
if(j+h>H||k+w>W)
continue Loop;
for(int l=0;l<h;l++){
for(int m=0;m<w;m++){
if(map[j+l][k+m])
continue Loop;
map[j+l][k+m] = true;
}
}
index++;
}
}
}
check = true;
}
}while(ArrayFunction.nextPermutation(mapping));
//答えの出力
out.println(check?"Yes":"No");
out.close();
}
}
自作ライブラリのArrayFunction::nextPermutationがバグってて大変焦りました()。
感想
A:易しい
B:1ペナ出して悲しい…
C:雑に実装したせいで1ペナ出しちゃった…
D:解法に至るまでかなり時間使っちゃった…
って感じでした。
Eは動的計画法であること以外何もわからなかった…。圧倒的実力不足…。