AtCoder Beginner Contest 266 メモ(A-D)

今回の結果

2AC

C問題は数学の知識がいるのがきつかった。
飛ばしてD問題に時間をかけたらACできてたかも。

A - Middle Letter

https://atcoder.jp/contests/abc266/tasks/abc266_a

Difficulty: 9

問題文

英小文字からなる長さが奇数の文字列 $S$ が与えられます。
$S$ の中央の文字を出力してください。

中央の文字とは

ある長さが奇数の文字列 $T$ について、 $T$ の長さを $|T|$ として、$T$ の前から $\frac{|T|+1}{2}$ 番目の文字を中央の文字とします。

制約

• $S$ は英小文字からなる長さが奇数の文字列
• $S$ の長さは $1$ 以上 $99$ 以下

入力

入力は以下の形式で標準入力から与えられる。

$S$

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

o

入力例 2

a

出力例 2

a

参加中に考えたこと

文字列を読み込んで真ん中の文字を出力するだけ。
制約で $S$ の長さは奇数と定められているので偶奇で分岐を入れる必要はなく、 $N \div 2$ 番目の文字を出力すればよい。

B - Modulo Number

https://atcoder.jp/contests/abc266/tasks/abc266_b

Difficulty: 95

問題文

$-10^{18}$ 以上 $10^{18}$ 以下の整数 $N$ が与えられます。
以下の条件を満たす $0$ 以上 $998244353$ 未満の整数 $x$ を求めてください。なお、答えが一意に定まることが証明できます。

• $N-x$ は $998244353$ の倍数

制約

• $N$ は $-10^{18}$ 以上 $10^{18}$ 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

答えを出力せよ。

入力例 1

998244354

出力例 1

1

入力例 2

-9982443534

出力例 2

998244349

参加中に考えたこと

入力の値が大きいのはループをさせたくない考えがあるのだろうか。
この問題で厄介なのは負の数の扱い方のところかな。
まず負の倍数ってどういう定義かよく分かってないので念のため確認するが、$\ldots -2a,-a,0,a,2a \ldots$ 倍でよかった。
例2を見ると、負の場合は $N$ より小さい値の倍数が答えになっている。
数値が大きいと考えにくいので数直線を用いて、小さい値で必要なケースを洗い出す。

1. $N \ge 0$ の時、条件を満たす倍数は $N$ 以上 $N+998244353$ 未満の中にある
2. $N < 0$ の時、条件を満たす倍数は $N - 998244353$ より大きく、 $N$ 未満の中にある

この2通りでよさそう。
$N$が0以上か0未満かで分岐して、それぞれ計算すればACできると思ったらWAした。。

どんなケースが漏れてるのかいろいろな数字で試すと $-2 \times 998244353$ の時に $998244353$ が返ってきた。
Nがちょうど-a倍の考慮が漏れてた。ここを直してACできた。

C - Convex Quadrilateral

https://atcoder.jp/contests/abc266/tasks/abc266_c

Difficulty: 516

問題文

$2$ 次元座標平面があります。$x$ 軸正方向を右向き、$y$ 軸正方向を上向きとします。
この平面上に自己交差のない四角形があります。
$4$ つの頂点の座標は反時計回りに $(A_x,A_y),(B_x,B_y),(C_x,C_y),(D_x,D_y)$ です。
この四角形が凸であるか判定してください。
なお、四角形の $4$ つの内角が全て $180$ 度未満であるとき、かつ、その時に限り、その四角形は凸であるといいます。

制約

• $-100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100$
• 入力に含まれる値は全て整数である
• 与えられる $4$ 点は四角形の $4$ 頂点を反時計回りに並べたものである
  与えられる $4$ 点のなす四角形は自己交差がなく退化していない。すなわち
  • どの $2$ 頂点も同じ座標にない
  • どの $3$ 頂点も同一直線上にない
  • 隣接しない $2$ 辺は共有点を持たない

入力

入力は以下の形式で標準入力から与えられる。

$A_x$ $A_y$
$B_x$ $B_y$
$C_x$ $C_y$
$D_x$ $D_y$

出力

与えられる四角形が凸なら Yes、凸でないなら No を出力せよ。

入力例 1

0 0
1 0
1 1
0 1

出力例 1

Yes

入力例 2

0 0
1 1
-1 0
1 -1

出力例 2

No

参加中に考えたこと

初めて聞くことばがいっぱい出てくる。。
まず調べるところからで時間を消費。で、凸四角形の定義は分かったと。

図形問題だと図を見ていろんなアプローチをしたくなるが、
問題文に書かれている通り、全ての内角の角度が180度未満であるかで判定すればいいのだろうか？
4つの辺の座標があるから4辺の長さは分かる。だけどそこから角度って求められるのか？

三角形2つに分けることで余弦定理を使えば角度は求められそうと思った。
ただこの方法はかなり手間がかかり、解き方としては間違ってる気がする。
それでも他に方法が浮かばないのでコードを書くが時間がかかった上にWA。

他の方法は、対角線の交点が四角形の中にあるかないかという方法もありそうだけどその判定も難しそう。
やりたいことは一般的なアルゴリズムがありそうだと思って、更に調べているうちにタイムアップ。

考察・感想

解き方が思いつかないので調べて見つけた方法は２つあった。
１つは公式解説と同じで外積を使う方法。
ベクトルとか外積とか覚えてないのでサンプルのコードをほぼ真似して書いてACした。
もう１つは、ユーザ解説の2つ目に近い感じのもので、対角線の線分を使って交差するかどうかを判定する方法。
数式がすこし複雑だけど大体理解してコードを書けた。
この問題では角度を計算する必要はなく、点ないし線の位置関係が分かれば凸か凹かが変わる。

D - Snuke Panic (1D)

https://atcoder.jp/contests/abc266/tasks/abc266_d

Difficulty: 840

問題文

高橋君はすぬけ君たちを捕まえようとしています。
数直線上の座標 $0,1,2,3,4$ の $5$ 箇所に穴があり、すぬけ君たちの巣につながっています。
これから $N$ 匹のすぬけ君が穴から出てきます。$i$ 番目のすぬけ君は時刻 $T_i$ に座標 $X_i$ の穴から出てきて、大きさは $A_i$ であることがわかっています。
高橋君は時刻 $0$ に座標 $0$ におり、数直線上を単位時間あたり $1$ 以下の速さで移動することができます。
すぬけ君が穴から出てきたのと同じ時刻に同じ座標に高橋君がいるとき、かつ、そのときに限り、高橋君はすぬけ君を捕まえることができます。
すぬけ君を捕まえるのにかかる時間は無視できます。
高橋君が適切に行動したとき、捕まえることができるすぬけ君の大きさの合計の最大値を求めてください。

制約

• $1 \leq N \leq 10^5$
• $0 < T_1 < T_2 < \ldots < T_N \leq 10^5$
• $0 \leq X_i \leq 4$
• $1 \leq A_i \leq 10^9$
• 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$
$T_1$ $X_1$ $A_1$
$T_2$ $X_2$ $A_2$
$\vdots$
$T_N$ $X_N$ $A_N$

出力

答えを整数として出力せよ。

入力例 1

3
1 0 100
3 3 10
5 4 1

出力例 1

101

次のように行動するのが最適です。

• 座標 $0$ で待機し、時刻 $1$ に $1$ 番目のすぬけ君を捕まえる
• 座標 $4$ へ移動し、時刻 $5$ に $3$ 番目のすぬけ君を捕まえる

$1$ 番目と $2$ 番目のすぬけ君を両方とも捕まえることはできないので、これが最大です。

入力例 2

3
1 4 1
2 4 1
3 4 1

出力例 2

0

高橋君はすぬけ君を $1$ 匹も捕まえることができません。

入力例 3

10
1 4 602436426
2 1 623690081
3 3 262703497
4 4 628894325
5 3 450968417
6 1 161735902
7 1 707723857
8 2 802329211
9 0 317063340
10 2 125660016

出力例 3

2978279323

参加中に考えたこと

C問題が解けず、少しD問題をのぞいてみたが問題文と入出力例がぱっと結びつかなかったのでこの問題を解くのは諦めた。

考察・感想

入力例3をしばらく見て、ようやく問題文の意味が分かった。
使うのはDPだとすぐわかるし、コードはさらさらとかけてACできた。