AtCoder Biginner Contest 185 全完しました!
やったぜ。
A - ABC Preparation
1回のコンテストを開くのに100~400点の各問題が1問ずつ必要なので、入力のうち最も小さい数字を出力すればよいです。配列で受け取って最小値を返す関数を使うのが楽だと思います。
B - Smartphone Addiction
家を出る時をB0、家に帰る時をAM+1として、(現在の容量)-(Ai+1-Bi)>0 のチェックと(現在の容量)=max(N,(現在の容量+(Ai+1-Bi))を繰り返せばいいです。
これがBに置かれるの、令和を感じますね……
C - Duodecim Ferra
なんか最初箱とボールと勘違いしました……
鉄の棒の欠片がL個あると考えると、L-1個の欠片のすき間のうち11個を選ぶ通り数、すなわちL-1C11
オーバーフローしそうだな~と思ってL=200を試すと明らかにオーバーフローしていたので、BigIntegerで殴ると通りました。
D - Stamp
ハンコの使用回数を最小にしたいので、ハンコの幅kをなるべく大きくしたいです。
kの上限は白が連続する区間の最長の長さなので、(それを超えると青に重ならずハンコを押すのが不可能になります)白が連続する部分の長さを数えてNに対して切り上げ除算すればいいです。これはAi+1-Ai-1の最小となります。端っこは別途計算しておきました。0除算とかM=0の場合とかいろいろコーナーもあるので気を付けました。
F - Range Xor Query
Dを解き終わった時点で順位表を見ると茶緑の人達が無限人Fを通していたので、先にFを見ました。問題開きながら「タイトル的にセグ木とかかな~」とか思ってました。そしたら親戚のおじさんの顔より見た貼るだけセグ木だったので、貼ったら通りました。
E - Sequense Matching
これ最初全然わかんね~っつってたんですが、A'i!=B'iであるときにコスト1で両者を取り除く、みたいに考えると、DP[i][j]:=AiとBjまで見たときの最小コスト、みたいに管理できそう、と思いつきました。
こんな感じの漸化式に帰着できます。
このDPなんか名前付いてないのかな~とか思ったけどよく考えたらLCSとやってることほとんど変わらないですね。それぞれi,j文字目まで見たときの状況を2次元テーブルの要素として管理する、みたいな。
感想
50分ノーペナ全完、かなりいい出来だと思ったんだけど黄パフォ取れないんですね。壁が高いぜ……。