省エネなコードを書きたい!

競プロについて書いたりします

気ままに考察/CODE FESTIVAL 2014 予選B -C/錬金術士

問題はこちら。
atcoder.jp
【解法】
 ある英大文字Xについて考えられるのは
① S1のみに存在している。
② S2のみに存在している。
③ S1、S2の両方に存在している。
の3通りである。①、②の場合には必ず片方から使う必要があるので厄介なのは③である。ここではS1が使う文字数の上限と下限を考えることで
inf<=N<=supなら構築できる。そうでないならできないと考える。すなわち直接S1から使う文字数を考えていてはキリがないかなぁという思考になるわけである。
 Xについてinf=max(0,S3にある数-S2にある数)、
sup=min(S1にある数,S3にある数)でありこれをA〜Zで纏めればOK。
【コード】
atcoder.jp
【感想】
久しぶりにこんな感じの問題(直接は難しいから上限、下限を考える)。文字列は苦手......

気ままに考察/ABC184-E/Third Avenue

問題はこちら。
atcoder.jp
【初考】
 テレポートでなければ普通に幅優先探索で行けそう。先にテレポート無しを計算しておいて、「aを使う場合」とかで別で計算するのかな〜とか......。二回同じ英文字に対しテレポートをする必要がないことはすぐわかる。うまいことテレポートを扱う方法は結局わからず。
【解答】
 二通りあって01BFSの方がめちゃめちゃ綺麗で感動したので記しておく。
 テレポートを使う場合について各テレポートにcost[t]のような形でコストを持たせておく。通常の幅優先探索に加え、テレポートを使う場合(i,j)からa[i][j]のアルファベットに重さ1の辺を、a[i][j]からテレポート先一覧に重さ0の辺を張ることで01BFSができる(テレポート先一覧は前持って作っておく)。
 特別なノードに対して状態を分ける(今回でいうアルファベット、その座標とアルファベットを別々に独立させてグラフを作るみたいな)っていう考え方はよくある気がする。
【コード】
解説写経しました.....感動しすぎて......
atcoder.jp
【感想】
 Eすら見れずに終わったので次こそは......

気ままに考察/ABC169-E/Count Median

問題はこちら。
atcoder.jp
【初考】
 手の付け所がわからなかった。即解答チェック(方針すら思い浮かばない問題はこれでいい気がする)。
【解答】
 まず中央値として考えられる値の上限、下限を考え範囲を狭める。感覚的に言えば各$ X_{i} $が小さい方が中央値も当然小さくなるし、逆も然りである。よって下限は各範囲が下限$ A_{i} $を取るとき、上限は各範囲が上限$ B_{i} $を取るときである。逆にこの範囲内においてある$ X_{i} $を1増やすと$ N $が奇数なら1、偶数なら$ \frac{1}{2} $だけ中央値は増加することになる。つまり範囲内のすべての可能性を再現できることとなる。後は$ N $の偶奇で分けてコーディングすればOK。
【コード】
atcoder.jp
【後考察】
 上限、下限を考えれば後は再現性云々はすぐ示せた。平均値ならばまだしも中央値で単調性らしきものを考えるのは難しかった。