ABC017 C - ハイスコア

問題
提出コード
すんなり考察&実装がいったので結構好きです。

解法

1つも入手しない宝石の種類を1つ決めると、それ以外の全ての宝石は獲得しても問題ありません。これについて考えるとき、2種類目以降の獲得しない宝石が存在しようがしまいが関係ありません。
ということで、
memo[i] = i番目の宝石を獲得しない、と決めたときに得られる得点の最大値
という配列を埋めていくことを考えます。
番目の遺跡を探索すると、からまでの宝石を入手します。得点はです。
ということは、先ほどの配列について考えると、iが
～までと、～
場所に、を追加できますこれは、番目の遺跡を探索しても、上記の区間内の宝石は獲得しないので、配列の条件を満たすからです。
これをすべてのについて行えばいいのですが、配列の要素1つ1つにを追加していると間に合いません。
区間のすべてに要素を追加するので、いもす法を使います。
memo[1]とmemo[ ]にを追加し、memo[ ]とmemo[ ]からを引きます。これをすべてのについて行い、最後にmemo[1]から順番に累積和をとっていくと、配列の計算が完了します。
あとは、これらすべての要素を確認して、その中の最大値をとってくれば答えとなります。

ABC045 D - すぬけ君の塗り絵 / Snuke's Coloring

問題
提出コード
想定解の方がスマートでした。
自分は、mapを使ってごり押しをしました。

解法

素直に全探索することをまず考えてみると、
9マスのうち、左上のマスを決め打ってから9個のマスを確認する、という動作は、左上のマスの候補が

となるので、もちろん間に合いません。
なので、今回は黒いマスの個数がたかだかであることを利用し、
それぞれの黒いマスを含む全ての正方形の取り方について、重複なく数え上げていく
ということを行います。
正方形がすべて白いマスだった場合は、から、黒いマスが1~9個であったパターンの和を引けば求めることができます。
さて、ある黒いマスを1つとってきたときに、その黒いマスを含むような正方形の選び方は9通りです。正方形の上からiマス、左からjマス目の部分にその黒いマスがあったパターン、を考えると自然と9通りになります。
ということで、全ての黒いマスについて、それぞれの9通りのパターンのときに、黒いマスの個数がどうなっているかを調べればいいです。
あとは、これを重複のないよう、そしてマス目がはみ出ることがないように数えていけば、答えが求まります。

ABC016 C - 友達の友達

問題
提出コード

解法

幅優先っぽいことをしようと思いますが、2つ先のみを見ればいいので、そのようにします。
制限もとても小さいので、割と何をしても大丈夫です。
まずは、入力をしていきます。
memo[i][j] = iとjが友達かどうか、としていき、友達なら1、そうでなければ0とでもしておきましょう。
今、ユーザーxについての、友達の友達の人数を調べることにします。
まずは、友達をすべて列挙します。
先ほどのメモをみて、友達だったらvectorに挿入、とでもしておけば十分です。
あとは、そのvectorの要素すべてに対して、n人と友達であるかどうかを調べれば完了です。
そのとき、そもそもxと友達であった場合や、被っているパターンを排除できるようにしましょう。
サイズがnの配列を用意して、xの友達の友達であれば1、そうでなければ0として記録していき、最終的にその要素を確認して和をとっていく、という方法をとると重複せずに数えることができます。
あとは、これを全てのxに対して行っていけばいいです。

ABC044 D - 桁和 / Digit Sum

問題
提出コード
これが500点？という感じの難易度でした。苦手意識があり、全く違うベクトルの考察を始めてしまうので解ける気がしません…

解法

のとき、になります。それ以外でになるようなは存在しません。ということで、の場合は、が答えになります。この場合のみ、先に処理をします。
が間に合うので、どうにかしてかぐらいに計算量を落としたいです。
進数について考えるとき、までは進数になおすと3桁以上ですが、それより大きい数字(ただし以下です)をなおすと2桁になります。
ということで、がにおさまるパターンと、そうでないパターンで場合分けをしていき考えます。

• がにおさまるパターン
  が間に合うため、全探索ができそうです。
  桁和の計算もそこまで時間がかかりません(logにおさまります)。ということで、2から順番に調べていき、条件を満たすが見つかった時点でうちきります。

• がにおさまらないパターン
  先ほど、こちらのパターンは進数に直すと2桁となる、と言いました。
  2桁の数字を、"pq"と表現することにすると、進数の定義から、
  
  という条件が成り立ちます。
  また、問題の条件から、
  を満たすようにしなければなりません。ということで、についての方程式が2つできたので、これを連立します。上の式から、下の式を引くことで、
  
  という条件式になります。""の形に直すと、
  
  となります。
  あとは、細かい条件をすべて満たしつつ、この方程式も満たすようなの中で、最も小さいものを求めれば完了です。
  について探索すればいいのですが、通り試していたのでは間に合いませんので、が割り切れたときに、とおきなおして同時に調べれば、で事足ります。
  あとは、

• 、つまり

• (これは、がにおさまらないということを表しています)

• 
  等の条件を加えて、全て満たすような場合のの最小値を求めれば、答えになります。

ABC044 C - 高橋君とカード / Tak and Cards

問題
提出コード
CはDPのCですね！

解法

動的計画法を利用します。
数列のi番目までのうち、j個の要素を足した結果がkになるようなものの個数
とします。
すると、

右辺の左の項は、を使用しないパターン(1つ前の個数がそのまま引き継がれます)、右の項は、を使用したパターン(使用すると、が1つ増えるので、見るべき場所は1つ前になります)です。
答えがどこにあるかというと、平均がになるので、個数列の要素を選んでいるときは、和がになっていなければなりません。よって、
dp[n][j][j×A]
の和を求めれば、答えになります。

ABC043 D - アンバランス / Unbalanced

問題
提出コード

解法

アンバランスな文字列tには、ある文字xが過半数以上存在しなければなりません。
これにより、tのうち少なくとも2つに1つ(以上)は文字xが存在しています。
なので、文字列tには、どこかに

• "xx"

• "x〇x"

の2種類の並びのうちどちらかが存在していないといけません。これが存在していなかった場合、必ず文字列tに含まれる文字xは半数以下になっています。そして、この2種類の並びは、それ自体もアンバランスな文字列になっていますので、結局この2種類について考えてしまえばいいことになります。
ので、文字列sの部分文字列で、アンバランスなものを探すとき、上の2種類の並びが存在するかどうか調べればよいことになります。
あとは、26種類ある英語小文字全てに対して、上のような文字列を探せば、存在した時点で1つ出力するだけで答えになります。
全ての文字に対して探しても見つからなかった場合は、-1 -1を出力すればいいです。

ABC043 C - いっしょ / Be Together

問題
提出コード

解法

制約がめちゃくちゃ少ないので、愚直にやっていきます。
そろえる数字yを固定し、ひたすら数列すべてについてのコストの和を求めていきます。
1つのyに対し、コスト計算は数列の長さ分だけ時間がかかり、yの選び方は-100~100の200通りなので、余裕で間に合います。
yについて全探索して、最小値を求めたら終了です。