はじめに
今回は用事があって参加できなかったんですが、後からFまで解いたのでそれを載せようと思います。
では、見ていきましょう。
A - 11/22 String
問題文はこちら
問題文の通りに条件を判定しました。
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){
int N = sc.nextInt();
String S = sc.next();
boolean check = N%2==1;
for(int i=0;i<N/2;i++){
check &= S.charAt(i)=='1';
check &= S.charAt(N-1-i)=='2';
}
out.println(check&&S.charAt(N/2)=='/'?"Yes":"No");
out.close();
}
}
B - 1122 String
問題文はこちら
A問題同様、条件式をそのまま実装しました。
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){
String S = sc.next();
HashSet<Character> set = new HashSet<>();
boolean flag = S.length()%2==0;
for(int i=0;i<S.length()/2;i++){
flag &= S.charAt(2*i)==S.charAt(2*i+1);
flag &= set.add(S.charAt(2*i));
}
out.println(flag?"Yes":"No");
out.close();
}
}
C - 11/22 Substring
問題文はこちら
条件を満たす連続部分文字列同士が重複する領域は存在しないので、愚直に/を探して長さを求めても十分高速に処理できます。
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){
int N = sc.nextInt();
String S = sc.next();
int ans = 1;
for(int i=0;i<N;i++){
if(S.charAt(i)=='/'){
for(int j=0;j<N;j++){
if(0<=i-j-1&&i+j+1<N&&S.charAt(i-j-1)=='1'&&S.charAt(i+j+1)=='2')
continue;
else{
ans = Math.max(ans,2*j+1);
break;
}
}
}
}
out.println(ans);
out.close();
}
}
D - 1122 Substring
問題文はこちら
条件を満たす区間を先に求めます。
偶数番目、奇数番目を$1$文字目として判定して前後一致している連続部分列を求めてArrayListに$1$文字目だけ入れておけば、重複した数字が存在しない最長区間を求める問題に帰着でき、これは尺取り法で求めることができます。
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){
int N = sc.nextInt();
int[] A = sc.nextInt(N);
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for(int i=0;i+1<N;i+=2){
if(A[i]==A[i+1]){
ArrayList<Integer> subList = new ArrayList<>();
for(int k=0;i+k+1<N;k+=2){
if(A[i+k]==A[i+k+1])
subList.add(A[i+k]);
else{
i += k;
break;
}
}
if(A[i]==A[i+1])
i = N;
list.add(subList);
}
}
for(int i=1;i+1<N;i+=2){
if(A[i]==A[i+1]){
ArrayList<Integer> subList = new ArrayList<>();
for(int k=0;i+k+1<N;k+=2){
if(A[i+k]==A[i+k+1])
subList.add(A[i+k]);
else{
i += k;
break;
}
}
if(A[i]==A[i+1])
i = N;
list.add(subList);
}
}
int ans = 0;
boolean[] set = new boolean[N+1];
for(ArrayList<Integer> X:list){
int r = 0;
for(int l=0;l<X.size();l++){
while(r<X.size()&&!set[X.get(r)])
set[X.get(r++)] = true;
ans = Math.max(ans,r-l);
set[X.get(l)] = false;
}
}
out.println(ans*2);
out.close();
}
}
E - 11/22 Subsequence
問題文はこちら
連続ではない部分文字列で考えれば良いので、1の個数と2の個数が釣り合うくらいの位置にある/を中心とするのが最適なように見えますし、実際最適です(その位置より左にズレれば1の個数を稼げなくなるし、右にズレれば2の個数を稼げなくなります)。
なので、ぴったり中心となる/が無い場合も考えて前後二つくらいを試せば最適解が求まります。
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);
public static void main(String[] args){
int N = sc.nextInt();
int Q = sc.nextInt();
String S = sc.next();
int[] one = new int[N+1];
int[] two = new int[N+2];
ArrayList<Integer> mid = new ArrayList<>();
for(int i=0;i<N;i++){
one[i+1] = one[i];
if(S.charAt(i)=='1')
one[i+1]++;
two[N-i] = two[N-i+1];
if(S.charAt(N-i-1)=='2')
two[N-i]++;
if(S.charAt(i)=='/')
mid.add(i+1);
}
while(Q-->0){
int L = sc.nextInt();
int R = sc.nextInt();
int ans = 0;
int left = Searcher.upSearch(mid,L);
int right = Searcher.downSearch(mid,R);
if(left>right)
out.println(0);
else{
int mid1 = Searcher.upSearch(left,right,0,
(int m)->(one[mid.get(m)]-one[L-1])-(two[mid.get(m)]-two[R+1]));
int mid2 = Searcher.downSearch(left,right,0,
(int m)->(one[mid.get(m)]-one[L-1])-(two[mid.get(m)]-two[R+1]));
int ans1 = mid1<=right?Math.min(one[mid.get(mid1)]-one[L-1],two[mid.get(mid1)]-two[R+1]):0;
int ans2 = left<=mid2?Math.min(one[mid.get(mid2)]-one[L-1],two[mid.get(mid2)]-two[R+1]):0;
out.println(Math.max(ans1,ans2)*2+1);
}
}
out.close();
}
}
F - 1122 Subsequence
問題文はこちら
公式解説の通りです。
$\mathrm{dp}[S]$を、集合$S$の数字を含んだ1122数列を作るのに何文字目まで使うかを保持するようにしてbitDPの要領で解きました。
なお、都度インデックスを二分探索で求めていては実行時間がかかりすぎてしまうため、先に全位置から見ての最寄りの数字のインデックスを先に求めておいてあります。
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);
private static final int max = 20;
public static void main(String[] args){
int N = sc.nextInt();
int[] A = sc.nextInt(N);
ArrayList<ArrayDeque<Integer>> list = new ArrayList<>();
for(int i=0;i<max;i++)
list.add(new ArrayDeque<>());
for(int i=0;i<N;i++)
list.get(A[i]-1).add(i);
for(int i=0;i<max;i++)
list.get(i).add(N);
int[][] nextIndex = new int[max][N+2];
for(int i=0;i<max;i++){
for(int j=0;j<N;j++){
if(list.get(i).peekFirst()<j)
list.get(i).removeFirst();
nextIndex[i][j] = list.get(i).peekFirst();
}
nextIndex[i][N] = N;
nextIndex[i][N+1] = N;
}
int[] dp = new int[1<<max];
Arrays.fill(dp,N);
dp[0] = 0;
for(int loop=0;loop<max;loop++){
for(int i=0;i<max;i++){
for(int j=0;j<1<<max;j++){
if(((1<<i)&j)==0){
dp[(1<<i)|j] = Math.min(dp[(1<<i)|j],nextIndex[i][nextIndex[i][dp[j]]+1]);
}
}
}
}
int ans = 0;
for(int i=1;i<1<<max;i++){
if(dp[i]<N){
ans = Math.max(ans,Integer.bitCount(i));
}
}
out.println(ans<<1);
out.close();
}
}
はじめに
A,B:易しめ
C,D:この難易度帯にしては易しめ
E:気づいちゃえばサクッといける
F:コンテスト中には気づかなそう…
って感じでした。
これはコンテスト出てもレート下がる回だった気がする…。