AGC-A 13-18

を解いた。やはり、300点と200点の間には難易度に大きな壁があるように感じる。まあさすがに300も安定して解けるようにはなってきているが。

昨日から体調が悪い。そのクセそこそこ長期の旅行に出発してしまったので時間があまりとれない。

AGC 13

 

言われたとおり書くだけ

 

 

AGC 14

 

もらってくるクッキーが偶数 & 奇数という組み合わせが発生したら奇数になるので終わる。

 

今持っている枚数が4の倍数でなければ、渡すクッキーは奇数になる。

2つ偶数の和が4の倍数になるには、 両方が0 mod 4 or 2 mod 4である必要がある。

 

3人が同時に奇数となるパターンは、最初からそうなっているときのみ。

2人が同時に奇数になるパターンは、3人のうち一人が4の倍数、もう二人が2の倍数のとき。

1人だけが奇数になるのは、3人のうち二人が4の倍数、もう一人が2の倍数のとき。

 

クッキーの枚数の推移を見ると

A, B, C

B/2 + C/2, A/2+C/2, A/2 + B/2

A/2+B/4+C/4, B/2+C/4+A/4, A/4+B/4+C/2

 

2ターン経つと、自分がもともと持っていたクッキー/2 + 他の二人のクッキーの和/4が手元に入るという流れ。

無限ループになるa==b==c以外では、大した回数続かないように見えるので、実際にシミュレートして答えを出す。

 

 

AGC 15

 

基本的には、B-A+1個の可能な数字からA, B以外の未確定なN-2個を選べばいいが、和が等しい組み合わせを処理する必要がある。

和の大きい方から見ていくことにする。

A, B B B B …..が最大。

A, B-1, B B B B …がその次、

….

A, A, B B B … B まで続く。

途中でA, A+i, B-1, B…のような和を考えると重複が出る。

 

結局、未確定のうちで最小の値だけを減らしてAまで持っていくことを繰り返せばいいので、

1+(B-A) * (N-2)

 

入力例に a>bがあったりするの何がしたいんだ。

 

 

AGC 16

 

毎回、末尾かその手前の文字が消える。

後方の文字を前方にコピーしてくることはできるが、逆は不可能。

 

高々100文字で、26文字しか候補が無いのだから全て試せばいい。

100^2*26しかかからないはず。

 

文字を指定すれば、取るべき操作は明らか。

 

 

AGC 17

 

ビスケットが奇数個の袋と偶数個の袋がそれぞれいくつかを数える。

最初、それぞれの袋から好きな数だけ取っていい問題と勘違いしていた。

200点にしてはややこしすぎると気づくべき。

 

 

AGC 18

 

箱に入ったボールは増えていく。

箱に1が入っていれば、Aの最大値>=kで自明に作れる。

 

箱に1が入らないパターンとは何か。

Aの最小値での他のAのmodを考えると、その値までは少なくとも作ることができる。

さらにそれらの差を、と考えていくと、結局最大公約数？

 

 

ABC-C118も似ているが、絶対値を取って値を更新して、というタイプの問題は最大公約数ではという気付きにどれだけ早く到れるかが重要。

 

差を取っていって最大公約数というのは、ユークリッドの互除法がどのようなアルゴリズムかをちゃんと理解していれば自然な発想のはず。