tinumu's reminder

競技プログラミングについて書いてあります。

AGC036~040 - A 埋めメモ

競技プログラミング AGC

AGC043でA問題が解ける気がしなくなってきました…
not-522.appspot.com

AGC036 - A - Triangle

$x_1=0,y_1=0$ と置いてみる。ここで三角形の面積を外積を用いて求めて $S$ に対して方程式を立てると、
$\frac{x_2y_3-x_3y_2}{2} = \frac{S}{2}$ より
$x_2y_3-x_3y_2=S$ となる。
ここでさらに仮定を置いて、 $x_2=10^9, y_2=1$ と置くと、
$10^9y_3-x_3=S$ となるので、 $y_3$ で大まかな値を決めて、 $x_3$ で数値を $1$ ずつ調整できることに気がつく。
そのため、 $y_3=\lceil \frac{S}{10^9} \rceil$ と置いて、あとは $x_3=10^9y_3 - S$ とおくと、 $x_3, y_3$ について制約から漏れず解くことが出来る。

仮定を置きすぎてこれ思いつくか？(AGCやばいなって無限に言ってる)

AGC037 - A - Dividing a String

貪欲法で解いた。 (後でDPもやってみた)
できるだけ前になるように切り分けると、 $n$ 回切り分けた時に一番左が取れることは言える。しかし、末尾において、正当性がない場合がある。このときは、同じ文字が末尾に $3m+2$ 個あるので、切り分け方を 1 2 1 2 ではなくて、 2 1 2 1 みたいにすると、整合性が保てているので、そういうことにするとACする(は？)。

AGC038 - A - 01 Matrix

f:id:tinumukiti631:20200320184541j:plain

終(あ間違えた $W-B$ じゃなくて $H-B$ です)

AGC039 - A - Connection and Disconnection

想定解だと普通に個々の $S$ が独立したものと考えて $S$ について求めて $K$ 回掛けることをする
末尾と先頭の部分だけ再計算して( $S_n=S_1$ の時はそれで連続している同じ文字すべて) 置き換えることで答えにしているみたい
重なった部分を消すとかそういう処理をしたほうがプログラムが単純になる

AGC040 - A - ><

各位置 $i$ において <が左に連続する数と >が右に連続する数の $\mathrm{max}$ を取ればおわり
なんでこれ解けなかったんや

感想

やっぱり考察力落ちてるのかなあ(なんかAGC-AがABCと違うだけとはいえなさそう)