ABC116

こどふぉがあって参加者が少なかったらしい。

A - Right Triangle

どれか2つを掛けて2で割ればいい。斜辺が2の二等辺三角形みたいなのを一瞬考えたが、入力は整数なので関係ない。どの2つかを図で確認したが、サンプル1で3*4/2=6を確認してもよかった。最初の2つを使えばいい。残りのサンプルは読まずに、サンプルが合ったので提出。

B - Collatz Problem

わりと見た瞬間解法がわかるのだが、やはりこういう問題は慣れないので細部を詰めるのに時間がかかる。都合のいい制約になっていることは推測できるが、それをちゃんと確認しないといけない。m>nが直観に反していて、サンプルが合わなかったときに時間を食った。

C - Grand Garden

できるだけ広く取っていけばいいという予想はすぐにできる。Nとhが小さいので何も工夫せずに通りそうだ。しかし証明ができない。実装も地味にめんどい。その両方を同時に解決する何かがあるんじゃないかとしばらく考えたが、できなかった。時間が過ぎていくので実装する。無限ループっぽいのは、削り切ったときにループを抜けてなかった（ループを抜ける方法がないコードだった）。そしてサンプルが合ったので提出。結局証明せずにACを取ってしまった。

D - Various Sushi

種類数で二分探索を思いついたが、できない。逆においしさでとか色々考えたができない。かなり考えても解けないので、けっこうな状況だと気づく。1個ずつ貪欲に取っていくのが成立してるんじゃないかと予想を立てる。C問題と同じような感じで未証明実装しようとするが、priority_queueを使っても種類数の変化に対応できないことに実装して初めて気づく。むっず！貪欲からの連想で、最初においしさだけで貪欲に取り、その後入れ替えていくのは？これは正しい解法っぽい！使っていない種類のものは、1個しか取る意味がない（既に選んだものよりおいしさが小さいものしかないから）。つまり、使ってない種類それぞれの一番おいしいものをおいしい順に並べておけばいい。順に、現在の種類数*2+1を2ずつ増やしていったものを足しておく。それによって満足ポイントへの寄与が順番通りにならなくなるが、おいしい順に並べるのが最善なのでそれでいい。もう片方の入れ替え対象は、おいしさが小さい順だけど、種類数を減らすことがないように注意が必要だった。単独で残ってる種類や、おいしさが同じで運よく残っただけのものがあっても、自分よりおいしいものと入れ替えることはないのだから大丈夫そう。実装。ここで、1個入れ替えて満足ポイントが減っても、2個入れ替えて増えることがありそうだと気づく。ヤバそうだが、順に求めていって最大値を更新していくだけだと気づく。さらに実装。多少のバグは出したが、この複雑な処理を書き切ったのはすごい。