はじめに
今回はA～EとGをコンテスト中に解けたので、それをそのまま載せようと思います。
なお、僕のライブラリはGitHubよりご確認下さい。
では、見ていきましょう。
A - A Healthy Breakfast
問題文はこちら
StringのindexOfメソッドを用いるとインデックスを得ることができるので、これを使って位置の判定を行ないました。
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){
//Sの受け取り
String S = sc.next();
//インデックスの取得
int indexR = S.indexOf("R");
int indexM = S.indexOf("M");
//条件判定
out.println(indexR<indexM?"Yes":"No");
out.close();
}
}
B - Vertical Reading
問題文はこちら
問題文の通りに実際に構築して判定しました。
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){
//S、Tの受け取り
String S = sc.next();
String T = sc.next();
//シミュレーション
for(int i=1;i<S.length();i++){
ArrayList<String> list = new ArrayList<>();
for(int j=0;j<S.length();j+=i)
list.add(S.substring(j,Math.min(j+i,S.length())));
for(int j=0;j<i;j++){
String subS = "";
for(String s:list)
if(j<s.length())
subS += s.charAt(j);
//構築できたらさっさと終わらせてしまう
if(T.equals(subS)){
System.out.println("Yes");
return;
}
}
}
//ループを抜けた=条件を満たさなかったのでNo
out.println("No");
out.close();
}
}
C - Move It
問題文はこちら
ある箱に荷物が複数入っている場合、一番重いものを残して他のものを動かした方が得なので、残り一個になるまで軽いものから順に取り出して、その総和を求めて上げれば答えが求まります。
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、A、Wの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
int[] W = sc.nextInt(N);
//箱毎に記録
HashMap<Integer,PriorityQueue<Integer>> map = new HashMap<>();
for(int i=0;i<N;i++){
if(!map.containsKey(A[i]))
map.put(A[i],new PriorityQueue<>());
map.get(A[i]).add(W[i]);
}
//貪欲法により最適解を求める
int ans = 0;
for(PriorityQueue<Integer> q:map.values())
while(q.size()>1)
ans += q.poll();
//出力
out.println(ans);
out.close();
}
}
D - Ghost Ants
問題文はこちら
同じ向きを向いている蟻同士は永遠にすれ違うことはないので、同じ向き同士で二グループに分けておきます。すると、片方のある蟻がすれ違う蟻は他方のグループの蟻のうち、自分との距離が$1$以上$2T$以下である蟻だとわかります。条件を満たす蟻が何匹いるかは事前に位置でソートしておけば二分探索で求まるのでこれで解きました。
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、S、Xの受け取り
int N = sc.nextInt();
long T = sc.nextInt();
char[] S = sc.nextCharArray();
long[] X = sc.nextLong(N);
//右向き左向きごとに記録
ArrayList<Long> L = new ArrayList<>();
ArrayList<Long> R = new ArrayList<>();
for(int i=0;i<N;i++){
if(S[i]=='0')
L.add(X[i]);
else
R.add(X[i]);
}
//位置でソート
Collections.sort(L);
Collections.sort(R);
//左向きの蟻を基準に数え上げ
long ans = 0;
for(long x:L){
int index1 = Searcher.upSearch(R,x);
int index2 = Searcher.upSearch(R,x-T*2);
ans += index1-index2;
}
//答えの出力
out.println(ans);
out.close();
}
}
E - Random Swaps of Balls
問題文はこちら
最初に黒いボールは先頭にあるという条件から、二番目以降に黒いボールがある確率がどのマスも全て等しいです。これを利用すると、先頭に黒いボールがあるときの確率、二番目以降にボールがある確率の$2$つを保持しておけば適切に計算ができます。あとはDPの要領で各操作による確率の変化を計算すれば良いです。
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);
private static final int MOD = 998244353;
public static void main(String[] args){
//N、Kの受け取り
int N = sc.nextInt();
int K = sc.nextInt();
//先頭とそれ以外に黒いボールがある確率
long main = 1;
long sub = 0;
//高速化のために1/N^2 mod MODを前計算
long div = MathFunction.modPow((long)N*N%MOD,MOD-2,MOD);
//K回操作
while(K-->0){
//遷移
long nm = (main*(N-1)%MOD*(N-1)+main)%MOD*div%MOD;
nm += sub*2%MOD*(N-1)%MOD*div%MOD;
long ns = sub*MathFunction.remainder((long)N*N%MOD-2,MOD)%MOD*div%MOD;
ns += main*2%MOD*div%MOD;
main = nm;
sub = ns;
if(MOD<=main)
main -= MOD;
if(MOD<=sub)
sub -= MOD;
}
//それぞれの確率を足す
long ans = main+((long)N*(N+1)/2-1)%MOD*sub%MOD;
//答えの出力
out.println(ans%MOD);
out.close();
}
}
かなり遷移書くのに手間取りました…
G - Suitable Edit for LIS
問題文はこちら
初期状態でのLISを求めてあげると(以降$L$)、LIS構築にどの要素を使う必要があるのかが求まります。あとは、$L_i$として採用可能な一番先頭の要素と$L_{i+1}$として採用可能な一番後ろの要素の間の要素に対して操作をすることでLISが大きくなりそうか判定すれば答えが求まります。
G.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、Aの受け取り
int N = sc.nextInt();
int[] A = sc.nextInt(N);
//普通にLISを求める(構築に使用可能な一番先頭の要素を求めるため)
int[] list = new int[N];
int[] indexList = new int[N];
Arrays.fill(list,Integer.MAX_VALUE);
for(int i=0;i<N;i++){
int index = Searcher.upSearch(list,A[i]);
list[index] = Math.min(list[index],A[i]);
indexList[i] = index;
}
int len = Searcher.upSearch(list,Integer.MAX_VALUE);
ArrayList<Integer> lastIndex = new ArrayList<>();
int index = N-1;
for(int i=len-1;i>=0;i--){
while(i!=indexList[index])
index--;
lastIndex.add(index);
}
//正負を入れ替えて逆順にして再度LIS(構築に使用可能な一番末尾の要素を求めるため)
ArrayUtil.mapping(A,i->-i);
ArrayUtil.reverseRange(A,0,N);
Arrays.fill(list,Integer.MAX_VALUE);
for(int i=0;i<N;i++){
index = Searcher.upSearch(list,A[i]);
list[index] = Math.min(list[index],A[i]);
indexList[i] = index;
}
ArrayList<Integer> firstIndex = new ArrayList<>();
index = N-1;
for(int i=len-1;i>=0;i--){
while(i!=indexList[index])
index--;
firstIndex.add(N-index-1);
}
//Aを元に戻す
ArrayUtil.mapping(A,i->-i);
ArrayUtil.reverseRange(A,0,N);
//高速化のためにint[]に変換
int[] fi = Converter.toIntArray(firstIndex);
int[] li = Converter.toIntArray(lastIndex);
//末尾の要素が逆順になったまんまなので元に戻す
ArrayUtil.reverseRange(li,0,len);
//現時点でのLISの答え
int ans = len;
//LISを+1できるかどうか調べる
for(int i=1;i<len;i++){
if(fi[i-1]+1<li[i]&&A[li[i]]-A[fi[i-1]]>1)
ans = len+1;
}
//先頭、末尾に適当な値を追加できるか判定
if(0<li[0])
ans = len+1;
if(fi[len-1]+1<N)
ans = len+1;
//答えの出力
out.println(ans);
out.close();
}
}
なんとか解けて良かった…。
感想
A,B,C:易しい
D:Dにしては易しい？
E:かなり手こずった…
G:勘が当たって良かった！
って感じでした。
かなり調子が良かったです。いつもこうなら文句無いんですがねぇ…。