はじめに
今回はコンテスト中にDまで、コンテスト後にGまで解けたのでそこまで載せようと思います。
では、見ていきましょう。
A - Rearranging ABC
問題文はこちら
$S$をchar[]として受け取り、Arrays::sortでソートしたのちString::newで連結することでABCと一致するか調べました。
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){
char[] S = sc.nextCharArray();
Arrays.sort(S);
if("ABC".equals(new String(S)))
out.println("Yes");
else
out.println("No");
out.close();
}
}
B - Avoid Rook Attack
問題文はこちら
コマの置いてあるマスを見つけたらそこを中心として十字型にboolean[][]の中身をtrueにし、後から全マスに対してfalseであるマスを数え上げることで答えを求めました。
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){
boolean[][] flag = new boolean[8][8];
for(int i=0;i<8;i++){
String S = sc.next();
for(int j=0;j<8;j++){
if(S.charAt(j)=='#')
for(int k=0;k<8;k++){
flag[k][j] = true;
flag[i][k] = true;
}
}
}
int ans = 0;
for(boolean[] f:flag)
for(boolean b:f)
if(!b)
ans++;
out.println(ans);
out.close();
}
}
C - Avoid Knight Attack
問題文はこちら
$N$が大きいのに対して置けないマスの候補はそこまで多くないので、置けるマスを数えるのではなく置けないマスの数を全体のマスの数から引くことを考えると、置けないマスをHashSetで重複なく数えることで答えが求められそうだったのでそれを実装しました。
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);
private static final int[] dx = {2,1,-1,-2,-2,-1,1,2};
private static final int[] dy = {1,2,2,1,-1,-2,-2,-1};
public static void main(String[] args){
long N = sc.nextInt();
int M = sc.nextInt();
HashSet<Point> set = new HashSet<>();
while(M-->0){
Point p = sc.nextPoint();
for(int i=0;i<8;i++){
int nx = p.x+dx[i];
int ny = p.y+dy[i];
if(MathFunction.rangeCheckClose(nx,1,N)&&
MathFunction.rangeCheckClose(ny,1,N))
set.add(new Point(nx,ny));
}
set.add(p);
}
out.println(N*N-set.size());
out.close();
}
}
さすがにHashSet<Point>は重かったですね…$2000$msちょいかかりました。
D - Many Segments 2
問題文はこちら
$l$を固定して考えることにします。
もし$[L_i,R_i](1 \le i \le N)$を$[l,r]$が完全に含んでるならば、$l \le L_i$かつ$R_i \le r$を満たしていることになります。したがって、$l$が固定されているならば$l \le L_i$なる$i$の集合$S$についてのみ考えればよく、$r$は$\min_{i \in S}R_i$未満であることが明らかなので、$r$の考えられる通り数は$\min_{i \in S}R_i-l$となります。
以上より、$R$をTreeSetなどで管理し、$l$を$1$から$M$まで順にずらしていきながら、$L_i<l$なる$i$に対応する$R_i$をTreeSetから削除していくことで適切に全通りを数え上げることができます。
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 M = sc.nextInt();
int[][] LR = sc.nextInt(N,2);
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int[] lr:LR)
map.merge(lr[1],1,Integer::sum);
map.put(M+1,0);
Arrays.sort(LR,Arrays::compare);
int index = 0;
long ans = 0;
for(int i=1;i<=M;i++){
int minRight = map.firstKey();
ans += minRight-i;
while(index<N&&LR[index][0]<=i)
map.merge(LR[index++][1],-1,(a,b)->a+b==0?null:a+b);
}
out.println(ans);
out.close();
}
}
E - Permute K times 2
問題文はこちら
公式解説を参考に実装しました。
$P_i=P_{P_i}$で置換するのは$P_i=i$で置換するときのダブリングによるDPの遷移と同じ形になります。
ダブリングの遷移を簡単に説明します(以降、$K$回の置換操作のことを$置換_K$と呼びます)。
$\mathrm{dp}[k][i]$を$i$の$置換_k$操作後の位置とすると、$置換_1$は$\mathrm{dp}[0][i]=P_i$、$置換_2$は$P_i$の$置換_1$操作後に等しいので$\mathrm{dp}[1][i]=P_{P_i} = P_{\mathrm{dp}[0][i]}$、$置換_4$は$P_{P_i}$の$置換_2$操作後に等しいので$\mathrm{dp}[2][i]=P_{P_{P_i}} = P_{\mathrm{dp}[1][i]}$、といった感じで遷移していくので文字だけで表すと$\mathrm{dp}[k+1][i] = P_{\mathrm{dp}[k][i]}$と表せます。これは本問題の置換方法に他なりません。
したがって、本問題は「$P_i=i$を$2^K$回行った後の値を求めよ」と言い換えられます。
この置換操作は$i$から$P_i$へ有向辺を張ったFunctionalグラフと見ることができ、$i$と$P_i$の間に無向辺を張ったグラフを考えると、$P$が$1$から$N$までの順列であることから連結成分同士は必ず環状のサイクルとして見ることができます。よって、$2^K$を要素数の大きさで割ったあまりだけ置換操作を行うことで目的の値を得ることができます。
今回は高速化のためにサイクルの大きさに対する全要素の操作後の位置をHashMapでメモ化しています。
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();
long K = sc.nextLong();
int[] P = sc.nextInt(N);
int[][] dp = new int[60][N];
dp[0] = P.clone();
for(int i=1;i<60;i++)
for(int j=0;j<N;j++)
dp[i][j] = dp[i-1][dp[i-1][j]-1];
UnionFind uf = new UnionFind(N+1);
for(int i=1;i<=N;i++)
uf.unite(i,P[i-1]);
HashMap<Integer,int[]> memo = new HashMap<>();
int[] ans = new int[N];
for(int i=1;i<=N;i++){
int subK = (int)MathFunction.modPow(2,K,uf.size(i));
if(!memo.containsKey(subK)){
int[] subAns = new int[N];
Arrays.setAll(subAns,a->a+1);
for(int j=0;j<30;j++){
if((subK&(1L<<j))>0){
int[] next = new int[N];
for(int k=0;k<N;k++){
next[k] = subAns[dp[j][k]-1];
}
subAns = next;
}
}
memo.put(subK,subAns);
}
ans[i-1] = memo.get(subK)[i-1];
}
out.println(ans);
out.close();
}
}
気づけるわけないじゃん()。
F - Avoid Queen Attack
問題文はこちら
ひたすら場合分けしました。
斜めに対する置けないマスの総数や、縦横に対する置けないマスのうち重複して数えてしまっているマスの工面など、考えることが多いですが、一つ一つ書いていくと整理できるかと思います。
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){
int N = sc.nextInt();
int M = sc.nextInt();
TreeSet<Integer> r = new TreeSet<>();
TreeSet<Integer> c = new TreeSet<>();
TreeSet<Integer> upCross = new TreeSet<>();
TreeSet<Integer> downCross = new TreeSet<>();
for(int i=0;i<M;i++){
int a = sc.nextInt();
int b = sc.nextInt();
r.add(a);
c.add(b);
upCross.add(a-b);
downCross.add(a+b);
}
long sub = (long)N*(r.size()+c.size())-(long)r.size()*c.size();
ArrayList<Integer> rList = new ArrayList<>(r);
ArrayList<Integer> cList = new ArrayList<>(c);
for(int cc:upCross){
int L = Math.max(0,cc);
int R = Math.min(N,N+cc);
sub += R-L;
int indexL = Searcher.overSearch(rList,L);
int indexR = Searcher.overSearch(rList,R);
sub -= Math.max(0,indexR-indexL);
HashSet<Integer> set = new HashSet<>();
for(int i=indexL;i<indexR;i++)
set.add(rList.get(i)-cc);
int subL = Math.max(0,-cc);
int subR = Math.min(N,N-cc);
indexL = Searcher.overSearch(cList,subL);
indexR = Searcher.overSearch(cList,subR);
for(int i=indexL;i<indexR;i++)
if(set.add(cList.get(i)))
sub--;
}
for(int cc:downCross){
int L = Math.max(0,cc-N-1);
int R = Math.min(N,cc-1);
sub += R-L;
int indexL = Searcher.overSearch(rList,L);
int indexR = Searcher.overSearch(rList,R);
sub -= Math.max(0,indexR-indexL);
HashSet<Integer> set = new HashSet<>();
for(int i=indexL;i<indexR;i++)
set.add(cc-rList.get(i));
indexL = Searcher.overSearch(cList,L);
indexR = Searcher.overSearch(cList,R);
for(int i=indexL;i<indexR;i++)
if(set.add(cList.get(i)))
sub--;
}
ArrayList<Integer> downList = new ArrayList<>(downCross);
for(int cc:upCross){
int L = Math.abs(cc)+2;
int R = 2*N-Math.abs(cc);
int indexL = Searcher.upSearch(downList,L);
int indexR = Searcher.overSearch(downList,R);
for(int i=indexL;i<indexR;i++){
int cc2 = downList.get(i);
if(((long)cc+cc2)%2>0)
continue;
int rval = (int)((long)cc+cc2>>1);
if((cc2-cc)%2>0)
continue;
int cval = cc2-cc>>1;
if(!r.contains(rval)&&!c.contains(cval))
sub--;
}
}
out.println((long)N*N-sub);
out.close();
}
}
G - Edit to Match
問題文はこちら
Trie木を用いました。
各ノードに対して、それまでの接頭辞と一致する、最も短い文字列を保持させ、最初の文字から順に、共通な接頭辞の長さを$i$、保持している文字列を$S'$とすると$|S_k|+|S'|-2i$が最も小さい文字列に合わせるのが最善なので、これを探索しました。
なお、実装上楽なので空文字を仮装上の最初のノードに乗せました。
G.java
import java.util.Scanner;
import java.util.ArrayList;
import java.util.HashMap;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
Trie trie = new Trie();
while(N-->0){
String S = sc.next();
String representation = trie.getNearestString(S);
int prefix = 0;
for(;prefix<Math.min(S.length(),representation.length());prefix++)
if(S.charAt(prefix)!=representation.charAt(prefix))
break;
System.out.println(S.length()+representation.length()-prefix*2);
trie.add(S);
}
}
}
class Trie{
private static final String empty = "";
private static class Node{
private HashMap<Character,Node> map;
private String representativeString;
public Node(){
map = new HashMap<>();
representativeString = empty;
}
public boolean contains(Character c){
return map.containsKey(c);
}
public Node get(Character c){
return map.get(c);
}
public Node add(Character c){
Node node = new Node();
map.put(c,node);
return node;
}
public void updateRepresentation(String S){
if(representativeString==empty||representativeString.length()>S.length())
representativeString = S;
}
public String getString(){
return representativeString;
}
public ArrayList<String> getList(){
ArrayList<String> list = new ArrayList<>();
for(var entry:map.entrySet()){
list.add(entry.getKey()+":{");
ArrayList<String> subList = entry.getValue().getList();
for(String s:subList){
list.add("\t"+s);
}
list.add("}");
}
return list;
}
}
private Node root;
public Trie(){
root = new Node();
root.representativeString = empty;
}
public int getLongestCommonPrefix(String S){
Node node = root;
for(int i=0;i<S.length();i++){
if(node.contains(S.charAt(i))){
node = node.get(S.charAt(i));
}
else
return i;
}
return S.length();
}
public String getLongestCommonPrefixString(String S){
Node node = root;
for(int i=0;i<S.length();i++){
if(node.contains(S.charAt(i))){
node = node.get(S.charAt(i));
}
else{
return node.getString();
}
}
return node.getString();
}
public String getNearestString(String S){
Node node = root;
String ans = empty;
int penalty = S.length();
for(int i=0;i<S.length();i++){
if(node.contains(S.charAt(i))){
node = node.get(S.charAt(i));
String representation = node.getString();
if(S.length()+representation.length()-2*(i+1)<penalty){
penalty = S.length()+representation.length()-2*(i+1);
ans = representation;
}
}
else{
return ans;
}
}
return ans;
}
public void add(String S){
Node node = root;
for(int i=0;i<S.length();i++){
Node bef = node;
if(!node.contains(S.charAt(i)))
node = node.add(S.charAt(i));
else
node = node.get(S.charAt(i));
node.updateRepresentation(S);
}
}
public String toString(){
ArrayList<String> list = root.getList();
StringBuilder sb = new StringBuilder();
sb.append("{");
for(String s:list){
sb.append("\n\t");
sb.append(s);
}
sb.append("}");
return sb.toString();
}
}
感想
A,B,C:易しい
D:ちょっと悩んだ
E,F,G:気づけない…
って感じでした。
青維持するならE以上もコンテスト中に解けないとなぁ…。