はじめに
今回も4完で、Eはコンテスト後に解いた物です。
では、見ていきましょう。
A - Middle Letter
問題文はこちら
真ん中を出力する問題ですね。
たとえば5文字の時は3文字目なわけですが、3文字目のindexに着目しましょう。
先頭から0、1、･･･と数えるので、3文字目は2です。
ではN文字のときはどうでしょうか。文字列の長さは奇数だと制約にあるので、(N+1)/2文字目だとわかります。さらにindexは(N-1)/2になります。ということで、Sをchar型配列として受け取ってS[(S.length-1)/2]を出力すれば良いです。
なお、S.lengthは奇数なので、(S.length-1)/2もS.length/2も同じ値になります(小数点以下は切り捨てられるので)。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Sをchar型配列で受け取る
char[] S = System.in.next().toCharArray();
//中間の文字を出力
System.out.println(S[S.length/2]);
System.out.close();
}
}
特に問題はないですね。
B - Modulo Number
問題文はこちら
ちょっとめんどくさい実装をしました。
998244353は書きにくいのでnumとします。
N%numを考えるとき、一度Nを-num+1～num-1の範囲までずらしたいので(N+a≡N mod aみたいな感じ)、N-N/num*numを計算します。次に、-num+1～-1の範囲だと困るので+numをします(これでNは0～2numに収まってるはず)。
あとは%numを行なえば1～numでの求めたい値が出ます。ということでそれを実装しましょう。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
long N = System.in.nextLong();
long num = 998244353;
//上記式の実装
System.out.println((N-N/num*num+num)%num);
System.out.close();
}
}
もっとサクッと実装する方法で、BigIntegerを使う方法があります。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//NをBigIntegerとして受け取り
BigInteger N = BigInteger.valueOf(System.in.nextLong());
BigInteger num = BigInteger.valueOf(998244353);
//あまりを出力(負の場合も正になって返ってくる)
System.out.println(N.mod(num));
System.out.close();
}
}
こっちの方がサクッと解けますね(記述量は増えるけど)。
C - Convex Quadrilateral
問題文はこちら
対角線に着目して解きました。
詳しい説明は上記の記事に任せますが、四角形が凸でない時の対角線同士は交差することも接することもないので、線分AC、BDが交差している(接している)か判定すれば良いです。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//各座標の受け取り
int[] A = System.in.nextInt(2);
int[] B = System.in.nextInt(2);
int[] C = System.in.nextInt(2);
int[] D = System.in.nextInt(2);
//対角線が交差しているか判定(s*t>0なら交差してない)
int s = (A[0]-C[0])*(B[1]-A[1])-(A[1]-C[1])*(B[0]-A[0]);
int t = (A[0]-C[0])*(D[1]-A[1])-(A[1]-C[1])*(D[0]-A[0]);
if(s*t>0){
System.out.println("No");
System.out.close();
return;
}
s = (B[0]-D[0])*(A[1]-B[1])-(B[1]-D[1])*(A[0]-B[0]);
t = (B[0]-D[0])*(C[1]-B[1])-(B[1]-D[1])*(C[0]-B[0]);
if(s*t>0){
System.out.println("No");
System.out.close();
return;
}
//交差していたらYes
System.out.println("Yes");
System.out.close();
}
}
早めに気づけて良かったです。
D - Snuke Panic (1D)
問題文はこちら
動的計画法で解きました。
時刻iでjにいるときの、合計の最大値をdp[i][j]としました。
はじめに、各T、X、Aでdp[T][X]にAを加算して得られるすぬけ君の大きさを記録します。
次に、dp[1][2]～dp[1][4]、、dp[2][3]～dp[2][4]、dp[3][4]は移動不可の領域なので全て0にします。
あとはi=2～100000で以下のように遷移していけば良いです。
$dp[i][j] = dp[i][j] + \mathrm{max}(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])$
j=0、4の時はj-1、j+1が範囲外参照になってしまうので別々に書きました。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//N、TXAの取得
int N = System.in.nextInt();
int[][] snukes = new int[N][3];
for(int i=0;i<N;i++){
snukes[i] = System.in.nextInt(3);
}
//dp[i][j]:時刻iでjにいるときの総和
long[][] dp = new long[100001][5];
//各すぬけ君が捕獲できる場所に大きさを記録
for(int i=0;i<N;i++){
dp[snukes[i][0]][snukes[i][1]] += snukes[i][2];
}
//絶対に行けない場所は0に
for(int i=1;i<5;i++){
for(int j=i+1;j<5;j++){
dp[i][j] = 0;
}
}
//時刻100000まで遷移してみる
for(int i=2;i<100001;i++){
dp[i][0] += Math.max(dp[i-1][0],dp[i-1][1]);
for(int j=1;j<4;j++){
long num = dp[i-1][j-1];
num = Math.max(num,dp[i-1][j]);
num = Math.max(num,dp[i-1][j+1]);
dp[i][j] += num;
}
dp[i][4] += Math.max(dp[i-1][3],dp[i-1][4]);
}
//最大値を求める
long answer = 0;
for(int i=0;i<5;i++){
answer = Math.max(answer,dp[100000][i]);
}
//答えの出力
System.out.println(answer);
System.out.close();
}
}
ちょっと実装に手間取ってしまいました。もうちょっと早く解きたいな･･･。
E - Throwing the Die
問題文はこちら
公式解説通りかと思います。
N=iのときの期待値をdp[i]に記録しておき、以下のように遷移することで実装しました。
$dp[i] = \sum\limits_{k=0}^{5}\mathrm{max}(dp[i-1],k+1)/6$
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args)throws IOException{
//Nの受け取り
int N = System.in.nextInt();
//dp[i]:N=iでの答え
double[] dp = new double[N];
//N=1のときの答えを初期値として入れておく
dp[0] = 3.5;
//Nの答えが出るまで続ける
for(int i=1;i<N;i++){
double sum = 0;
for(int j=1;j<7;j++){
sum += Math.max(dp[i-1],j);
}
dp[i] = sum/6;
}
//答えを出力
System.out.println(dp[N-1]);
System.out.close();
}
}
実装してみると簡単なんですがね･･･思いつかないや･･･。
感想
A:簡単。
B:ちょっと理解するのに時間がかかってしまった。
C:たまたま書いたことがあったのでコピペでサクッと解けた。
D:ちょっとしたミスを多発してしまった･･･。
E:いけそうとは思ったけど･･･うーん･･･。
って感じでした。
ちょっと数学チックな感じでしたね。期待値を求める問題を解いたことが無かったから反射的に身構えてしまいました。無念･･･。