はじめに
今回は、ABDはコンテスト中のものを、CEFはコンテスト後に解き直したものを載せます。
では、見ていきましょう。
A - Find Takahashi
問題文はこちら
普通に先頭から最大のものを探せば良いです。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//Nの受け取り
int N = System.in.nextInt();
//maxは最大値、ansはその位置を記録する
int max = 0;
int ans = 0;
//先頭から最大値を探す
for(int i=1;i<=N;i++){
int H = System.in.nextInt();
//最大値更新
if(max<H){
max = H;
ans = i;
}
}
//答えの出力
System.out.println(ans);
System.out.close();
}
}
まぁ問題はないですね。
B - ABC-DEF
問題文はこちら
それぞれの値が大きいので事前にあまりに変換しておき、計算途中でもあまりに変換していくことで正しく求められます。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//mod
int mod = 998244353;
//A～Fをmodをとりながら受け取り
long A = System.in.nextLong()%mod;
long B = System.in.nextLong()%mod;
long C = System.in.nextLong()%mod;
long D = System.in.nextLong()%mod;
long E = System.in.nextLong()%mod;
long F = System.in.nextLong()%mod;
//こまめにmodをとりながら計算
long temp1 = (A*B%mod)*C%mod;
long temp2 = (D*E%mod)*F%mod;
//差を出力(temp1-temp2が負数になってしまう可能性があるので+modをしている)
System.out.println((temp1-temp2+mod)%mod);
System.out.close();
}
}
これもまぁ大丈夫そうですね。
C - Counting Squares
問題文はこちら
やってることはAngrySadEightさんの解説と同じです。
$d1～d6$の組み合わせを考えるのがめんどうなので配列にまとめてソートしてから比較しています。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//#の位置を記録するList
ArrayList<Point> list = new ArrayList<Point>();
//各マスを見ていく
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char c = System.in.nextChar();
//#なら格納
if(c=='#')
list.add(new Point(i,j));
}
}
//便宜上Nに記録
int N = list.size();
//答えを記録
int count = 0;
//重複しないようにしながら四つの#を選ぶ
for(int i=0;i<N;i++)for(int j=i+1;j<N;j++)for(int k=j+1;k<N;k++)for(int l=k+1;l<N;l++){
//便宜上p1～p4として別変数に
Point p1 = list.get(i);
Point p2 = list.get(j);
Point p3 = list.get(k);
Point p4 = list.get(l);
//各#間の距離を全部計算
int[] d = new int[6];
d[0] = dist(p1,p2);
d[1] = dist(p1,p3);
d[2] = dist(p1,p4);
d[3] = dist(p2,p3);
d[4] = dist(p2,p4);
d[5] = dist(p3,p4);
//ソートして辺と対角線が条件を満たしていたらcountに1を足す
System.sort(d);
if(d[0]==d[3]&&d[4]==d[5]&&2*d[0]==d[5])
count++;
}
//答えの出力
System.out.println(count);
System.out.close();
}
//距離の二乗を返すメソッド
public static int dist(Point p1,Point p2){
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
}
//x、y座標を記録する用の構造体
class Point{
int x;
int y;
public Point(int x,int y){
this.x = x;
this.y = y;
}
}
本番中は焦りに焦って汚いコードを書いてしまった･･･(提出結果)。
図形的な問題は苦手です･･･。
D - Yet Another Recursive Function
問題文はこちら
メモ化再帰で解きました。
HashMapかTreeMapに記録しながら解けば良いかと思います。
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//Nの受け取り
long N = System.in.nextLong();
//再帰して答えを出力
System.out.println(dfs(N));
System.out.close();
}
//メモ用のmap
static HashMap<Long,Long> memo = new HashMap<Long,Long>();
//再帰メソッド
public static long dfs(long n){
//終点判定
if(n==0)
return 1;
//メモにあるならそれを返す
if(memo.containsKey(n))
return memo.get(n);
//メモに無ければ再帰して答えを求める
long ans = dfs(n/2);
ans += dfs(n/3);
//メモに残してから答えを返す
memo.put(n,ans);
return ans;
}
}
比較的簡単な気が･･･？
E - Sugoroku 4
問題文はこちら
マス$N$にたどり着ける通り数で解きました。
そうすれば単純な動的計画法として解くことが出来ます。$dp[i][j]$を$i$回目で$j$にいる通り数として、遷移は以下のようにしました(出目を$k$、今の位置を$j$とします)。
$k+j \gt N$なら
$index = 2 \times N-(k+j)$、
$k+j\le N$なら
$index = k+j$として、
$dp[i][index] = dp[i][index]+dp[i-1][j]$
$(1 \le k \le M,0 \le j \lt N)$
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//mod
int mod = 998244353;
//N、M、Kの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int K = System.in.nextInt();
//dp[i][j]:i回回した時にjにいる通り
int[][] dp = new int[K+1][N+1];
//初期値設定
dp[0][0] = 1;
//遷移
for(int i=1;i<=K;i++){
for(int j=0;j<N;j++){
for(int k=1;k<=M;k++){
int index = k+j>N?2*N-(k+j):k+j;
dp[i][index] += dp[i-1][j];
dp[i][index] %= mod;
}
}
}
//全通り数
long full = System.modPow(M,K,mod);
//Nに到達できる通り数
long count = 0;
//総和を求める
for(int i=1;i<=K;i++){
count *= M;
count %= mod;
count += dp[i][N];
count %= mod;
}
//fullの逆元をかけてmodをとれば求めたい答えになる
System.out.println((count*System.modPow(full,mod-2,mod))%mod);
System.out.close();
}
}
一度でも$N$に到達した通り数、という風に考えれば良いので最後$dp[i][N]$に$M^{N-i}$をかけてから総和をとる必要があります(僕はこれに気付かないでコンテスト中に解けませんでした･･･)。
F - Erase Subarrays
問題文はこちら
動的計画法で解きました。
$dp0[i][j]$を$i$番目までで$j$を作る最小操作回数のうち今の要素を選ばなかった方、
$dp1[i][j]$を$i$番目までで$j$を作る最小操作回数のうち今の要素を選んだ方として以下のように遷移しました。
$dp0[i+1][j] = \mathrm{min}(dp0[i][j],dp1[i][j]+1)$
$dp1[i+1][j] = \mathrm{min}(dp0[i][j-a[i]],dp1[i][j-a[i]])$
class Main{
static Library System = new Library(java.lang.System.in,java.lang.System.out);
public static void main(String[] args){
//N、M、aの受け取り
int N = System.in.nextInt();
int M = System.in.nextInt();
int[] a = System.in.nextInt(N);
//上記参照
int[][] dp0 = new int[N+1][M+1];
int[][] dp1 = new int[N+1][M+1];
//適当に大きな値を
int max = (int)1e6;
//初期値設定
for(int i=0;i<=N;i++){
Arrays.fill(dp0[i],max);
Arrays.fill(dp1[i],max);
}
dp1[0][0] = 0;
//遷移
for(int i=1;i<=N;i++){
for(int j=0;j<=M;j++){
dp0[i][j] = Math.min(dp0[i-1][j],dp1[i-1][j]+1);
if(j>=a[i-1])
dp1[i][j] = Math.min(dp0[i-1][j-a[i-1]],dp1[i-1][j-a[i-1]]);
}
}
//1～Mについて答えを求めて出力
for(int i=1;i<=M;i++){
int ans = Math.min(dp0[N][i],dp1[N][i]);
System.out.println(ans>=max?-1:ans);
}
System.out.close();
}
}
うーん･･･解き直してみればそりゃそうなんですが、やっぱり本番中はなかなか思いつかないですね･･･。
感想
A,B:比較的易しい
C:とてもめんどくさかった
D:ちょっと易しい気がする
E:確率苦手過ぎる･･･
F:動的計画法な気はしたけど、手が付けられなかった･･･
って感じでした。
4完続きでレートのグラフは下り坂を形成し始めております･･･悲しい･･･。