はじめに
今回はコンテスト中にFまで解けたのでそれを載せようと思います。
なお、僕のライブラリはGitHubをご確認ください。
では、見てきましょう。
A - Count Takahashi
問題文はこちら
TakahashiかAokiの$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){
//Nの受け取り
int N = sc.nextInt();
//数え上げ
int ans = 0;
while(N-->0){
String S = sc.next();
if(S.charAt(0)=='T')
ans++;
}
//答えの出力
out.println(ans);
out.close();
}
}
B - Couples
問題文はこちら
隣接する$3$人にのみ着目すれば良いので、直前の$2$人を保持しながら順に見ていくことで答えを数え上げることができます。
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();
//直前の2つを記録
int A1 = sc.nextInt();
int A2 = sc.nextInt();
//数え上げ
int ans = 0;
for(int i=2;i<N<<1;i++){
int A3 = sc.nextInt();
if(A1==A3)
ans++;
A1 = A2;
A2 = A3;
}
//答えの出力
out.println(ans);
out.close();
}
}
C - Tile Distance 2
問題文はこちら
$y$軸方向への移動にはどうしても$|S_y-T_y|$だけ通行料を払う必要があります。ここで、1マスずらしでタイルが敷き詰められていると考えれば、今いるタイルから$|S_y-T_y|$だけ左右にずれることは追加で通行料を払うことなくできると考えることができます。これによって、移動可能な$(T_x,T_y)$に最も近いタイルが求まり、そこからの移動に必要な通行料を加算してあげることで解を求めることができます。
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){
//Sx、Sy、Tx、Tyの受け取り
long Sx = sc.nextLong();
long Sy = sc.nextLong();
long Tx = sc.nextLong();
long Ty = sc.nextLong();
//答えの構築
long ans = Math.abs(Sy-Ty);
long L = Sx-ans-(Sx+Sy)%2;
long R = Sx+ans+1-(Sx+Sy)%2;
if(!MathFunction.rangeCheckClose(Tx,L,R))
ans += (Math.min(Math.abs(Tx-L),Math.abs(Tx-R))+1)/2;
//答えの出力
out.println(ans);
out.close();
}
}
Cにしてはやけに数学チックで面食らいました…。
D - Avoid K Palindrome
問題文はこちら
注目するべき区間は$K$文字だけなことに着目すると、直前$K-1$文字をkeyに、その文字列になる組み合わせの個数をvalueにしたHashMap<String,Integer>を構築することで、DPを用いて解を求めることができると考え、実装しました。
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、K、Sの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
char[] S = sc.nextCharArray();
//DP用のMap
HashMap<String,Integer> map = new HashMap<>();
//初期値構築
map.put("",1);
for(int i=0;i<K-1;i++){
HashMap<String,Integer> next = new HashMap<>();
for(Entry<String,Integer> entry:map.entrySet()){
if(S[i]=='?'){
next.merge(entry.getKey()+"A",entry.getValue(),Main::merge);
next.merge(entry.getKey()+"B",entry.getValue(),Main::merge);
}
else
next.merge(entry.getKey()+S[i],entry.getValue(),Main::merge);
}
map = next;
}
//遷移
for(int i=K-1;i<N;i++){
HashMap<String,Integer> next = new HashMap<>();
for(Entry<String,Integer> entry:map.entrySet()){
if(S[i]=='A'||S[i]=='?'){
String nextS = entry.getKey()+"A";
if(isGoodString(nextS))
next.merge(nextS.substring(1),entry.getValue(),Main::merge);
}
if(S[i]=='B'||S[i]=='?'){
String nextS = entry.getKey()+"B";
if(isGoodString(nextS))
next.merge(nextS.substring(1),entry.getValue(),Main::merge);
}
}
map = next;
}
//数え上げて出力
int sum = 0;
for(int num:map.values())
sum = merge(sum,num);
out.println(sum);
out.close();
}
//処理が面倒なのであまり取った足し算をメソッド化
private static final int MOD = 998244353;
private static int merge(int a,int b){
int ans = a+b;
if(MOD<=ans)
ans -= MOD;
return ans;
}
//回文でないならtrue、回文ならfalseを返すメソッド
private static boolean isGoodString(String S){
for(int i=0;i<S.length();i++)
if(S.charAt(i)!=S.charAt(S.length()-1-i))
return true;
return false;
}
}
E - Water Tank
問題文はこちら
ある壁を越えるまでに必要な水を考えた時、それまで超えた壁のうち、直近である壁よりも高い壁までの区間全体に水を満たす必要があると考えられます。例えば、$H=(4,1,2,3)$であるとき、$3$番目の壁を越えてから$4$番目の壁を越えるまでに必要な水の量を考える時、$1$番目の壁から$4$番目の壁までの区間を高さ3になるまで水を加える必要があります。これは、予めStackなどで$H$の狭義単調減少列と各要素毎の距離を構築することで必要な水の量を高速に求めることができるようになります。
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){
//Nの受け取り
int N = sc.nextInt();
//狭義単調減少列構築用のDeque
ArrayDeque<Long> deq = new ArrayDeque<>();
//番兵(区間の幅と壁の高さ)
deq.add(0L);
deq.add(Long.MAX_VALUE);
//現在の操作回数
long sum = 0;
//答えを記録する用の配列
long[] answer = new long[N];
//各壁を順に処理
for(int i=0;i<N;i++){
//Hの受け取り
long H = sc.nextLong();
//区間の幅
long base = 1;
//必要な操作回数
long ans = H;
//直前の壁が水没するならその分だけ補正
while(deq.peekLast()<=H){
long subH = deq.pollLast();
long subB = deq.pollLast();
base += subB;
ans += (H-subH)*subB;
}
//総操作回数に加算
sum += ans;
//記録(超えたタイミングなので+1)
answer[i] = sum+1;
//今処理した幅と壁の高さを記録
deq.add(base);
deq.add(H);
}
//答えの出力
out.println(answer);
out.close();
}
}
F - Tree Degree Optimization
問題文はこちら
不安なので証明は省略しますが()、次数を増やすときの差分をPriorityQueueに入れて貪欲に選ぶことで解きました。
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);
//PriorityQueueの処理用のクラス
static class Node{
long d;
long A;
public Node(long d,long a){
this.d = d;
A = a;
}
//次数を増やすときの差分を返すメソッド
public long getValue(){
return d*A;
}
}
public static void main(String[] args){
//Nの受け取り
int N = sc.nextInt();
//次数は必ず1以上なのでとりあえずAの総和を取り、ついでにPriorityQueueに追加しておく
long ans = 0;
PriorityQueue<Node> queue = new PriorityQueue<Node>((a,b)->Long.compare(a.getValue(),b.getValue()));
for(int i=0;i<N;i++){
int A = sc.nextInt();
queue.add(new Node(3,A));
ans += A;
}
//最小値を貪欲に取りながらPriorityQueueを更新
for(int i=2;i<N;i++){
Node node = queue.poll();
ans += node.getValue();
node.d += 2;
queue.add(node);
}
//答えのしゅつりょく
out.println(ans);
out.close();
}
}
なんかいけそう！って思って投げたら通って大歓喜でした。
感想
A,B:易しい
C:難しい…
D:比較的易しい
E:考え方にちょっと苦戦したけど、比較的速く解けた
F:Fにしては易しめ？
って感じでした。
今回は自分に合った問題セットで良かったです。
毎度これくらいのパフォーマンスが出せれば苦労しないんですけどねぇ…。