はじめに
今回はコンテスト中にEまで、コンテスト後にFを解いたのでそれを載せようと思います。
なお、僕のライブラリは提出結果よりご確認下さい。
では、見ていきましょう。
A - Yay!
問題文はこちら
一文字目が先頭以外に見つからなかったら$1$を、見つかったら先頭と異なる文字の位置を出力しました。
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();
//先頭の文字と同じ文字を消してみる
String subS = S.replace(S.charAt(0)+"","");
//1文字にならなかった=先頭の文字が他と異なるので1番目が答え
if(subS.length()!=1){
out.println(1);
}
else{
//2番目以降に答えがあるのでループで探す
for(int i=1;;i++)
if(S.charAt(0)!=S.charAt(i)){
out.println(i+1);
break;
}
}
out.close();
}
}
B - Which is ahead?
問題文はこちら
各人が何番目かを保持した配列を作成し、各クエリに答えました。
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();
//誰がどこにいるか記録
int[] index = new int[N+1];
for(int i=1;i<=N;i++)
index[sc.nextInt()] = i;
//Qの受け取り
int Q = sc.nextInt();
while(Q-->0){
//A、Bの受け取り
int A = sc.nextInt();
int B = sc.nextInt();
//どっちが前に近いか判定
out.println(index[A]<index[B]?A:B);
}
out.close();
}
}
C - Many Replacement
問題文はこちら
文字をkeyに、keyの文字に変換された文字のArrayListをkeyに保持したHashMapを使って変換を記録し、最後に対応する文字をHashMap<Character,Character>に記録して答えを構築しました。
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、Sの受け取り
int N = sc.nextInt();
String S = sc.next();
//各文字のマッピングを記録
HashMap<Character,ArrayList<Character>> map = new HashMap<>();
for(char c='a';c<='z';c++){
map.put(c,new ArrayList<>());
map.get(c).add(c);
}
//Qの受け取り
int Q = sc.nextInt();
while(Q-->0){
//c、dの受け取り
char c = sc.nextChar();
char d = sc.nextChar();
//文字のマッピングを変更する
ArrayList<Character> list = map.remove(c);
map.put(c,new ArrayList<>());
map.get(d).addAll(list);
}
//各文字に対応する文字を記録
HashMap<Character,Character> mapping = new HashMap<>();
for(Entry<Character,ArrayList<Character>> entry:map.entrySet())
for(Character c:entry.getValue())
mapping.put(c,entry.getKey());
//答えの構築
StringBuilder ans = new StringBuilder();
for(char c:S.toCharArray())
ans.append(mapping.get(c));
//答えの出力
out.println(ans.toString());
out.close();
}
}
ちょっと実装汚くなっちゃった…。
D - Square Pair
問題文はこちら
平方数になるには各素因数の指数部が偶数である必要があるので、各値を素因数分解して、奇数だったものだけを奇数個含む数字を順に見ていけば十分間に合います(語彙力さん…)。
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、Aの受け取り(Aは各文字の個数として保持)
int N = sc.nextInt();
int[] A = new int[200_001];
for(int a:sc.nextInt(N))
A[a]++;
//答え用変数
long count = 0;
//先に0との積の分を記録(今思えばO(1)で求められた…)
for(int i=1;i<=200_000;i++)
count += (long)A[0]*A[i];
count += (long)A[0]*(A[0]-1)/2;
//1から順に見ていく
for(int i=1;i<=200_000;i++){
//平方数を取り除いた値を求める
int mult = removeSquare(i);
//自身との積が平方数になる値との組み合わせを数え上げ
for(int j=1;mult*j*j<=200_000;j++)
if(i<mult*j*j)
count += (long)A[i]*A[mult*j*j];
else if(i==mult*j*j)
count += (long)A[i]*(A[i]-1)/2;
}
//答えの出力
out.println(count);
out.close();
}
//平方数を取り除く用のメソッド
private static int removeSquare(int num){
//素因数分解
HashSet<Integer> set = new HashSet<>();
for(int i=2;i*i<=num;i++){
int count = 0;
while(num%i==0){
num /= i;
count++;
}
if((count&1)==1)
set.add(i);
}
if(num>1)
set.add(num);
//奇数のものだけかける
int ans = 1;
for(int n:set)
ans *= n;
return ans;
}
}
実装に手こずって時間かけちゃった…。
E - Last Train
問題文はこちら
駅$N$に最終電車で行くのが最適なのでそれに間に合うように乗ることを考えた時、駅$N$からダイクストラ法を用いてその駅にいられる最終時刻を求めていけば各駅の$f(i)$が求まると思ったのでそれを実装しました。
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、Mの受け取り
int N = sc.nextInt();
int M = sc.nextInt();
//隣接リストの構築
ArrayList<ArrayList<int[]>> list = new ArrayList<>();
for(int i=0;i<=N;i++)
list.add(new ArrayList<>());
while(M-->0){
int l = sc.nextInt();
int d = sc.nextInt();
int k = sc.nextInt();
int c = sc.nextInt();
int A = sc.nextInt();
int B = sc.nextInt();
list.get(B).add(new int[]{A,l,d,k,c});
}
//ダイクストラ用クラス
class Node{
int now;
long time;
Node(int n,long t){
now = n;
time = t;
}
}
//初期値設定
PriorityQueue<Node> queue = new PriorityQueue<>((a,b)->Long.compare(b.time,a.time));
long[] ans = new long[N+1];
for(int i=1;i<=N;i++){
ans[i] = Long.MIN_VALUE;
}
ans[N] = 2_000_000_000_000_000_000L;
queue.add(new Node(N,ans[N]));
//ダイクストラ
while(queue.size()>0){
Node n = queue.poll();
if(n.time==ans[n.now]){
for(int[] p:list.get(n.now)){
long max = (n.time-p[4]-p[1])/p[2];
if(0<=max){
max = p[1]+Math.min(max,p[3]-1)*p[2];
if(ans[p[0]]<max){
ans[p[0]] = max;
queue.add(new Node(p[0],max));
}
}
}
}
}
//答えの出力
for(int i=1;i<N;i++)
out.println(ans[i]==Long.MIN_VALUE?"Unreachable":ans[i]);
out.close();
}
}
最初駅$N$への到着時刻を問う問題だと勘違いして実装を一度書き換えました…。
F - Black Jack
問題文はこちら
公式解説の通りです。
解説の$q$は$r$を求める時に同時に計算しています。
F.java
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//N、L、Dの受け取り
int N = sc.nextInt();
int L = sc.nextInt();
int D = sc.nextInt();
//とりあえず大きめに配列作るために最大値取っておく
int len = Math.max(L+D,N);
//解説のpの累積和に相当する配列の構築
double[] sum = new double[len+1];
sum[0] = 1.0;
for(int i=1;i<=len;i++){
if(i<=L){
sum[i] = (sum[i-1]-(i<=D?0:sum[i-D-1]))/D+sum[i-1];
}
else{
sum[i] = (sum[L-1]-(i<=D?0:sum[Math.min(i-D,L)-1]))/D+sum[i-1];
}
}
//解説のrの累積和に相当する配列の構築
double[] dp = new double[len+2];
for(int i=N;i>=0;i--){
dp[i] = Math.max(
sum[L+D]-sum[N]+Math.max(0.0,0<i?sum[i-1]-sum[L-1]:0.0),
(dp[i+1]-(i+D<=N?dp[i+D+1]:0.0))/D)+dp[i+1];
}
//答えの出力
System.out.println(dp[0]-dp[1]);
}
}
DPかなとは思いましたが、遷移が思いつかず…精進不足ですね…。
感想
A,B:易しい
C:もう少し綺麗に実装したい…
D:数学苦手過ぎる～…
E:誤読悲しい
F:難しい…
って感じでした。
青には戻りましたが、なんとも言えない結果…。