AtCoder Beginner Contest 266

AtCoder Beginner Contest 266 - AtCoder

結果

A - Middle Letter:AC(3:56)
B - Modulo Number:AC(86:15)(2ペナ)
C - Convex Quadrilateral:提出無し
D - Snuke Panic (1D):提出無し

A - Middle Letter

長さが奇数の英小文字の文字列$${S}$$が与えられ、その中央の文字を出力する問題

自分の回答

int main() {
  string S;
  cin >> S;
 
  int s = S.length() / 2;
 
  printf("%c\n", S[s]);
}

与えられる文字列が奇数文字数に限られるため例外なく中央が存在し、中央が何文字目かは文字数を$${T}$$とすると$${\frac{T+1}{2}}$$、しかしC++において1文字目は0番目なことと割り算で小数点以下切り捨てなことを合わせればS[$${\frac{T}{2}}$$]でおｋ

公式解説

基本同じなため省略

B - Modulo Number

整数$${N}$$が与えられ、$${N-x}$$が998244353の倍数となる$${x}$$を求める問題

自分の回答

int main() {
  int64_t N;
  cin >> N;
  int64_t x = 0;
  while(true){
    if((N - x) % 998244353 == 0){
      printf("%ld\n", x);
      break;
    }
    x++;
  }
}

$${x}$$を0から全探索するごり押し
$${x}$$が1以上と勘違いしていてそれに気付かず2回WA

今考えると$${N}$$ % 998244353が答えだったのでは？

あとごり押しとはいえこの方法を思いついていながら次の問題をやりに行ったのはなんで？
次からは思いついたら書こう

公式解説

const int mod = 998244353;

int main() {
    long long n;
    cin >> n;
    n %= mod;
    if(n < 0) n += mod;
    cout << n << endl;
}

https://atcoder.jp/contests/abc266/editorial/4665より

やっぱりそうか
C++だと負の数を割った余は負として帰ってくるからそこを修正して出力か
なるほど

C - Convex Quadrilateral

$${xy}$$平面上にある四角形の頂点の座標$${(A_{x},A_{y}),(B_{x},B_{y}),(C_{x},C_{y}),(D_{x},D_{y})}$$が与えられ、その四角形が凸かを判定する問題

自分の回答

各頂点は反時計回りで入力されるから、それがどう移動するかの順番で考えたが$${x}$$軸、$${y}$$軸に平行な辺があるときの処理が大変そうだった
ならば対角線を考えて、対角線を延長した直線で平面を2つの領域に分け、対角線に関わってない頂点がそれぞれの領域に1つづつ存在する、それが2本の対角線において言えたら凸である、とも考えたがこれはプログラムに落とし込めなかった

公式解説

int X[4], Y[4];

int f0(int x, int y){
  return (X[2] - X[0]) * (y - Y[0]) - (Y[2] - Y[0]) * (x - X[0]);
}

int f1(int x, int y){
  return (X[3] - X[1]) * (y - Y[1]) - (Y[3] - Y[1]) * (x - X[1]);
}

int sgn(int x){
  if(x < 0){
    return -1;
  }
  else if(x > 0){
    return 1;
  }
}

int main() {
  for(int i = 0; i < 4; i++){
    cin >> X[i] >> Y[i];
  }

  if(sgn(f0(X[1], Y[1])) != sgn(f0(X[3], Y[3])) && sgn(f1(X[0], Y[0])) != sgn(f1(X[2], Y[2]))){
    printf("Yes\n");
  }
  else{
    printf("No");
  }
}

https://atcoder.jp/contests/abc266/editorial/4723より
実装例がPythonだったため、それを基にC++に書き換えたもの
自分の考えに近かったもの

まず、2点$${(x_{1},y_{1}),(x_{2},y_{2})}$$を通る直線の方程式$${(x_{2}-x{1})(y-y_{1})-(y_{2}-y_{1})(x-x_{1})=0}$$を用意し、そこに任意の座標$${(a,b)}$$を入れて
$${(x_{2}-x{1})(y-y_{1})-(y_{2}-y_{1})(x-x_{1})<0}$$ならば直線より下の領域
$${(x_{2}-x{1})(y-y_{1})-(y_{2}-y_{1})(x-x_{1})>0}$$ならば直線より上の領域に$${(a,b)}$$が存在することになるため、対角線に関わらない2つの頂点を対角線の式に入れた値の符号が異なるかで判定できる

f0,f1が値を求める関数、対角線2本とも判定するため2つ用意
sgnで正負のみに変換、値が0となる座標は存在するが、それは対角線上に頂点がある、すなわち四角形にはならないためこの問題においては現れない
そしてそれぞれの対角線において値の正負が違う時にYesを出力、違うならNoを出力

なるほど

D - Snuke Panic (1D)

ざっくりまとめようとしてもあまり変わらないため省略

自分の回答

動的計画法っぽいなとは思った
しかし時間が足りなかった

公式解説

#define ll long long
#define max(p,q)((p)>(q)?(p):(q))
 
ll dp[5][100010];
ll x[100010],a[100010];
 
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int t,xx,aa;
		scanf("%d%d%d",&t,&xx,&aa);
		x[t]=xx;
		a[t]=aa;
	}
	
	for(int i=1;i<5;i++)dp[i][0]=-1e18;
	
	for(int t=1;t<=100000;t++){
		for(int i=0;i<5;i++){
			dp[i][t]=dp[i][t-1];
			if(i!=0)dp[i][t]=max(dp[i][t],dp[i-1][t-1]);
			if(i!=4)dp[i][t]=max(dp[i][t],dp[i+1][t-1]);
		}
		dp[x[t]][t]+=a[t];
	}
	
	ll ans=0;
	for(int i=0;i<5;i++)ans=max(ans,dp[i][100000]);
	printf("%lld\n",ans);
}

https://atcoder.jp/contests/abc266/editorial/4661より
(C言語)

位置と時間の２次元配列で動的計画法か

なるほど