はじめに
今回はコンテスト中にEまで解けたのでそれをそのまま載せようと思います。
では、見ていきましょう。
A - Edge Checker 2
問題文はこちら
子は親の$2$倍か$2$倍+$1$なので、それを判定してあげれば良いと思い実装しました。
A.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//a、bの受け取り
int a = System.in.nextInt();
int b = System.in.nextInt();
//制約上a<bなので大小を気にする必要はない
//bがaの子か判定
System.out.println(a*2==b||a*2+1==b?"Yes":"No");
System.out.close();
}
}
気付くか知っていればなんてことは無いですね。
B - Longest Uncommon Prefix
問題文はこちら
先頭から順に見ていって、一致したところを探せば良いです。予めフラグを立てておいて、一致してるところが見つからなかった時に分岐するようにしてあります。
B.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Sの受け取り
int N = System.in.nextInt();
String S = System.in.next();
//N-1回繰り返す
for(int i=1;i<N;i++){
//一致が見つからなかった時用
boolean flag = true;
for(int l=0;l<N-i;l++){
//一致していればそこまでなのでlを出力し、flagをfalseに
if(S.charAt(l)==S.charAt(l+i)){
System.out.println(l);
flag = false;
break;
}
}
//見つかってなければ最大値を
if(flag)
System.out.println(N-i);
}
System.out.close();
}
}
最初問題文が何言ってるか理解できなくて時間をかけてしまいました。
読解力不足…。
C - abc285_brutmhyhiizp
問題文はこちら
$26$進数と捉えることができるので、それをそのまま実装しました。
C.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Sの受け取り
String S = System.in.next();
//26進数として変換
long ans = 0;
for(char c:S.toCharArray()){
ans = ans*26+c-'A'+1;
}
//出力
System.out.println(ans);
System.out.close();
}
}
これはそこまで難しくなかったですね。
D - Change Usernames
問題文はこちら
考え方は公式解説そのままなので詳細は省きますが、サイクルを検知できれば良いと思ってUnionFindで解きました。文字列はHashMapで座圧して整数に変換してます。なお、UnionFindはアルゴ式のものをそのまま実装したものです。
D.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//Nの受け取り
int N = System.in.nextInt();
//存在し得る文字列の個数分だけ準備(サイクル検知だけなので多くとっても別に良い)
UnionFind uf = new UnionFind(2*N);
//座圧用
HashMap<String,Integer> map = new HashMap<>();
int index = 0;
//ユーザーネームを全て変更できるか
boolean canSet = true;
for(int i=0;i<N;i++){
//S、Tの受け取り
String S = System.in.next();
String T = System.in.next();
//座圧
int indexS;
if(map.containsKey(S)){
indexS = map.get(S);
}else{
map.put(S,index++);
indexS = index-1;
}
int indexT;
if(map.containsKey(T)){
indexT = map.get(T);
}else{
map.put(T,index++);
indexT = index-1;
}
//サイクルが出来た時falseが返ってくるので全ての論理積を取ってやれば良い。
canSet &= uf.unite(indexS,indexT);
}
//変更できそう？
System.out.println(canSet?"Yes":"No");
System.out.close();
}
}
気付くこと自体は早かったので良かったです。
E - Work or Rest
問題文はこちら
動的計画法で解きました。なお、初日は休日と固定して良いのでそれを前提とします。
予め$k$日連続で平日だったときの生産量を$\mathrm{sum}[k]$として計算しておき、$\mathrm{dp}[i][j]$$をi$日目までで、今$j$日連続で平日だったときの最大値として、以下のように遷移しました。
$\mathrm{dp}[i][0] = \mathrm{max}(\mathrm{dp}[i][0],\mathrm{dp}[i-1][j]+\mathrm{sum}[j])$
$\mathrm{dp}[i][j] = \mathrm{dp}[i-1][j-1]$
E.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Aの受け取り
int N = System.in.nextInt();
int[] A = System.in.nextInt(N);
//生産量を予め求めておく
long[] sum = new long[N];
for(int i=1;i<N;i++)
sum[i] = sum[i-1]+A[(i-1)/2];
//dp[i][j]:i日目までで、今j日連続で平日だったときの最大値
long[][] dp = new long[N][N];
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
//不適なところはMIN_VALUEで初期化しておく
dp[i][j] = Long.MIN_VALUE;
}
}
//遷移
for(int i=1;i<N;i++){
for(int j=0;j<=i;j++){
dp[i][0] = Math.max(dp[i][0],dp[i-1][j]+sum[j]);
if(j>0)
dp[i][j] = dp[i-1][j-1];
}
}
//最後の吸湿から初日(休日)まで何日間かで生産量を加算し、maxを取る
long ans = 0;
for(int i=0;i<N;i++)
ans = Math.max(ans,dp[N-1][i]+sum[i]);
//答えの出力
System.out.println(ans);
System.out.close();
}
}
最初遷移のところで$\mathrm{sum}$と書いていたつもりが$A$と書いてしまっていて大きく時間を使ってしまいました…反省…。
感想
A:易しい
B:わかればなんてことはない
C:比較的易しい
D:これも気付いてしまえば早い
E:気付くまで、実装するまでに時間がかかってしまった…
って感じでした。
今回は調子が良かったです。いつか本番中にFレベルの問題も解けるようになりたいなぁ。
追記(F - Substring of Sorted String)
問題文はこちら
公式解説の通りです。
$S$の部分列が昇順かどうかの判定に関しても公式解説の追記の方を見ていただければ良いかと思います。
F.java
class Main{
static final boolean autoFlush = false;
static final Library System = new Library(java.lang.System.in,java.lang.System.out,java.lang.System.err,autoFlush);
public static void main(String[] args){
//N、Sの受け取り
int N = System.in.nextInt();
char[] S = System.in.nextCharArray();
//文字の種類だけSegmentTreeを準備する
ArrayList<SegmentTree<Integer>> segT = new ArrayList<>();
for(int i=0;i<26;i++)
//和を計算するように
segT.add(new SegmentTree<>(N,0,true){
public Integer function(Integer a,Integer b){
return a+b;
}
});
//出現する各文字の数
int[] count = new int[26];
for(int i=0;i<N;i++){
segT.get(S[i]-'a').update(i+1,1);
count[S[i]-'a']++;
}
//Q個クエリを処理する
int Q = System.in.nextInt();
while(Q-->0){
int q = System.in.nextInt();
//1なら対応するSegmentTreeを更新(countも)
if(q==1){
//x、cの受け取り
int x = System.in.nextInt();
char c = System.in.nextChar();
//更新
count[S[x-1]-'a']--;
segT.get(S[x-1]-'a').update(x,0);
S[x-1] = c;
count[S[x-1]-'a']++;
segT.get(S[x-1]-'a').update(x,1);
}else{
//l、rの受け取り
int l = System.in.nextInt();
int r = System.in.nextInt();
//[l,r]の各文字の数え上げ
int[] sum = new int[26];
for(int i=0;i<26;i++)
sum[i] = segT.get(i).query(l,r);
//存在しない文字の分のindexは考えたくないので端を調整
int s = 0;
int t = 25;
while(sum[s]==0)s++;
while(sum[t]==0)t--;
boolean ans = true;
//昇順で並べ替えた文字C1,C2,...Cmのうち、C2,C3,...,C{m-1}の個数が合っているか？
for(int i=s+1;i<t;i++)
ans &= sum[i]==count[i];
//各文字の数はちゃんと合っているか？
for(int i=0;i<26;i++){
ans &= segT.get(i).query(l,l+sum[i]-1)==sum[i];
if(!ans)
break;
l += sum[i];
}
//全部条件満たしてた？
System.out.println(ans?"Yes":"No");
}
}
System.out.close();
}
}
//SegmentTree
abstract class SegmentTree<E>{
int N,size;
E def;
Object[] node;
public SegmentTree(int n,E defa,boolean include){
N = 2;
size = 1;
while(N<n<<1){
N <<= 1;
size <<= 1;
}
size -= include?1:0;
node = new Object[N];
def = defa;
Arrays.fill(node,def);
}
public SegmentTree(int n,E defa){
this(n,defa,false);
}
@SuppressWarnings("unchecked")
public void update(int n,E value){
n += size;
node[n] = value;
n >>= 1;
while(n>0){
node[n] = function((E)node[n<<1],(E)node[(n<<1)+1]);
n >>= 1;
}
}
@SuppressWarnings("unchecked")
public E get(int a){
return (E)node[a+size];
}
@SuppressWarnings("unchecked")
public E answer(int a){
return (E)node[1];
}
@SuppressWarnings("unchecked")
public E query(int l,int r){
l += size;
r += size;
E answer = def;
while(l>0&&r>0&&l<=r){
if(l%2==1)
answer = function((E)node[l++],answer);
l >>= 1;
if(r%2==0)
answer = function(answer,(E)node[r--]);
r >>= 1;
}
return answer;
}
@SuppressWarnings("unchecked")
abstract public E function(E a,E b);
}
いやぁ…気付かなかったなぁ…。これがFの壁か…。