はじめに
今回はコンテスト中にEまで、コンテスト後にFまで解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認ください。
では、見ていきましょう。
A - 2UP3DOWN
問題文はこちら
問題文で指定されている範囲か判定して解きました。
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 ) {
//X、Yの受け取り
int X = sc.nextInt();
int Y = sc.nextInt();
//階段で行ける範囲か調べる
out.println(X-3<=Y&&Y<=X+2?"Yes":"No");
out.close();
}
}
B - 326-like Numbers
問題文はこちら
愚直に求めても十分間に合うので順に調べて解きました。
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 ) {
//Nの受け取り
int N = sc.nextInt();
//愚直に調べる
for(int i=N;;i++){
//問題文の通りの条件を満たしているなら出力して終了
int a = i/100;
int b = i/10%10;
if(a*b==i%10){
out.println(i);
break;
}
}
out.close();
}
}
最初$N$以下の326-like numberを数える問題だと思ってしまって時間をかけてしまいました…。
ちゃんと読もう…。
C - Peak
問題文はこちら
$x=A_i$とするのが最適なので、$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、M、Aの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
int[] A = sc.nextInt(N);
//ソート
Arrays.sort(A);
//尺取りで最大区間を求める
int ans = 0;
int index = 0;
for(int i=0;i<N;i++){
while(index<N&&A[index]-A[i]<M)
index++;
ans = Math.max(ans,index-i);
}
//答えの出力
out.println(ans);
out.close();
}
}
D - ABC Puzzle
問題文はこちら
各行の左端は$R$と一致させないといけないので、$i$行目のどの位置を$R$の$i$文字目と一致させるかを全探索し、それより右側は順列全探索し、$C$に対する条件も満たしている並び方があるか探索しました。
最大ケースの$N=5$について考えると、$1$文字目を$R$と一致させると$\frac{4!}{2!}=12$通り(BC..の並べ替え)、$2$文字目を$R$と一致させると$3!=6$通り、$3$文字目を$R$と一致させると$2!=2$通りで、各行における探索回数は計$20$通りなので、$20^5=3.2 \times 10^6$通り探索し、それぞれの盤面で$O(N^2)$で判定しているのでなんとか間に合います。
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 );
//再帰軽量化の為にクラス変数に
private static char[][] ans;
private static char[] R,C;
private static int N;
public static void main ( String[] args ) {
//N、R、Cの受け取り
N = sc.nextInt();
R = sc.nextCharArray();
C = sc.nextCharArray();
ans = new char[N][N];
//再帰全探索
dfs(0);
//再帰を抜けたら解無しなのでNo
out.println("No");
out.close();
}
//再帰用メソッド(今見ている行が引数)
private static final void dfs(int now){
//全部見終わった？
if(now==N){
//条件満たしてる？
if(check(ans)){
//出力して終了
out.println("Yes");
out.println(ans);
out.close();
System.exit(0);
}
}
else{
//Rと一致させる位置を全探索
for(int i=0;i<N-2;i++){
//記録して自分より右側の文字を別変数に記録
ans[now][i] = R[now];
char[] sub = new char[N-i-1];
sub[0] = (char)((R[now]+1-'A')%3+'A');
sub[1] = (char)((R[now]+2-'A')%3+'A');
for(int j=2;j<sub.length;j++)
sub[j] = '.';
//順列全探索
Arrays.sort(sub);
do{
for(int j=0;j<sub.length;j++)
ans[now][i+j+1] = sub[j];
dfs(now+1);
}while(ArrayFunction.nextPermutation(sub));
//とりあえず全部.で上書きしておく
for(int j=i;j<N;j++)
ans[now][i] = '.';
}
}
}
//判定メソッド
private static final boolean check(){
//列単位でABCがちゃんと出現してるか判定する用の配列
boolean[][] checkedC = new boolean[N][3];
//各列を見ていく
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
if('A'<=ans[i][j]){
//既に出現済みの文字なら条件を満たさないのでfalse
if(checkedC[j][ans[i][j]-'A'])
return false;
//記録
checkedC[j][ans[i][j]-'A'] = true;
}
}
}
//条件を満たしているかチェック
for(int i=0;i<N;i++){
//全列で全文字が出現しているか確認
for(int j=0;j<3;j++)
if(!checkedC[i][j])
return false;
//一番上の文字がCを形成しているか調べる
for(int j=0;;j++){
if(ans[j][i]>='A'){
if(ans[j][i]!=C[i])
return false;
break;
}
}
}
return true;
}
}
バグりまくってかなり時間をかけてしまいました…。悲しい…。
Revenge of "The Salary of AtCoder Inc."
問題文はこちら
$x \lt y$の時のみ支給されるので、今$x$であるとすると$x+1$以降になったときの期待値だけ考えれば良く、各状態へは確率$\frac{1}{N}$で遷移できるので、動的計画法を用いれば$dp[x] = \frac{1}{N} \sum^{N}_{i=x+1}{dp[i]}$と遷移すれば良さそうと考えてこれを実装しました。
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 );
//mod
private static final int MOD = 998244353;
public static void main ( String[] args ) {
//N、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//DPテーブル
long[] dp = new long[N+1];
dp[N] = A[N-1];
//累積和用変数
long sum = A[N-1];
//1/N mod 99844353を求めておく
long odd = MathFunction.modPow(N,MOD-2,MOD);
//遷移
for(int i=N-1;i>0;i--){
dp[i] = (A[i-1]+sum*odd)%MOD;
sum += dp[i];
if(sum>=MOD)
sum -= MOD;
}
//答えの出力
out.println(sum*odd%MOD);
out.close();
}
}
総和がsumに代入されているので、各状態への遷移確率である$\frac{1}{N}$をかけてあげれば答えとなります。
これは結構早く気付きました。
F - Robot Rotation
問題文はこちら
※実装が汚いです()
公式解説の通りのはずです。
最初MapのvalueをStringにしていたんですがなんか重めだったのでLongで管理することにしたら通りました。
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、X、Y、Aの受け取り
int N = sc.nextInt();
long X = sc.nextLong();
long Y = sc.nextLong();
long[] A = sc.nextLong(N);
//半分全探索パート(i mod 4毎に探索している
HashMap<Long,Long> mapY1 = new HashMap<>();
mapY1.put(0L,0L);
for(int i=0;i<N;i+=4){
HashMap<Long,Long> nextY = new HashMap<>(mapY1.size()<<1);
for(Entry<Long,Long> subY:mapY1.entrySet()){
long key = subY.getKey();
long val = subY.getValue();
nextY.putIfAbsent(key+A[i],(val<<2)|1);
nextY.putIfAbsent(key-A[i],val<<2);
}
mapY1 = nextY;
}
HashMap<Long,Long> mapX1 = new HashMap<>();
mapX1.put(0L,0L);
for(int i=1;i<N;i+=4){
HashMap<Long,Long> nextX = new HashMap<>(mapX1.size()<<1);
for(Entry<Long,Long> subX:mapX1.entrySet()){
long key = subX.getKey();
long val = subX.getValue();
nextX.putIfAbsent(key+A[i],(val<<2)|1);
nextX.putIfAbsent(key-A[i],val<<2);
}
mapX1 = nextX;
}
HashMap<Long,Long> mapY2 = new HashMap<>();
mapY2.put(0L,0L);
for(int i=2;i<N;i+=4){
HashMap<Long,Long> nextY = new HashMap<>(mapY2.size()<<1);
for(Entry<Long,Long> subY:mapY2.entrySet()){
long key = subY.getKey();
long val = subY.getValue();
nextY.putIfAbsent(key+A[i],(val<<2)|1);
nextY.putIfAbsent(key-A[i],val<<2);
}
mapY2 = nextY;
}
HashMap<Long,Long> mapX2 = new HashMap<>();
mapX2.put(0L,0L);
for(int i=3;i<N;i+=4){
HashMap<Long,Long> nextX = new HashMap<>(mapX2.size()<<1);
for(Entry<Long,Long> subX:mapX2.entrySet()){
long key = subX.getKey();
long val = subX.getValue();
nextX.putIfAbsent(key+A[i],(val<<2)|1);
nextX.putIfAbsent(key-A[i],val<<2);
}
mapX2 = nextX;
}
//x座標側の答えが存在するか調べる
String SX = null;
for(long num:mapX1.keySet()){
if(mapX2.containsKey(X-num)){
//二進数を文字列に変換
StringBuilder sb = new StringBuilder();
long subX = (N>>1)%2==0?
(mapX1.get(num)<<1)|mapX2.get(X-num):
mapX1.get(num)|(mapX2.get(X-num)<<1);
for(int i=1;i<N;i+=2){
sb.append((subX&1)>0?'U':'D');
subX >>>= 1;
}
SX = sb.reverse().toString();
break;
}
}
//見つからなかったらNo
if(SX==null){
System.out.println("No");
return;
}
//y座標側の答えが存在するか調べる
String SY = null;
for(long num:mapY1.keySet()){
if(mapY2.containsKey(Y-num)){
//二進数を文字列に変換
StringBuilder sb = new StringBuilder();
long subY = (N+1>>1)%2==0?
(mapY1.get(num)<<1)|mapY2.get(Y-num):
mapY1.get(num)|(mapY2.get(Y-num)<<1);
for(int i=0;i<N;i+=2){
sb.append((subY&1)>0?'U':'D');
subY >>>= 1;
}
SY = sb.reverse().toString();
break;
}
}
//見つからなかったらNo
if(SY==null){
System.out.println("No");
return;
}
//復元パート
StringBuilder ans = new StringBuilder();
char bef = 'U';
for(int i=0;i<N;i++){
if(i%2==1){
ans.append(SX.charAt(i>>1)!=bef?'L':'R');
bef = SX.charAt(i>>1);
}
else{
ans.append(SY.charAt(i>>1)==bef?'L':'R');
bef = SY.charAt(i>>1);
}
}
//答えの出力
out.println("Yes");
out.println(ans.toString());
out.close();
}
}
全然気付けなかった…。仮に気付いたとして正しい解法と思えたかは謎ですが…。
感想
A,B:易しい
C:尺取り久々に書いた気がする
D:めちゃくちゃ難しかった
E:気付けばそんなに難しくない
F:何も思いつけなかった…
って感じでした。
青には留まれているけど、やっぱり維持キツいですね…次回取り返さなきゃ。