// Competitive Programming (2) Advent Calendar 2019 の 15 日目の記事です。
競技プログラミングの AtCoder というものを今年の8月に始めて、3～4か月をかけて水色に到達しました。
スピード勝負は得意ではないのですが、難しめの問題を少し時間をかけて解くのが向いているようです。
また、簡潔なコードを書くことを心掛けていて、ショートコード C# 部門があるとしたらだいたい優勝していると思います。
(スペースを切り詰めたりはしません。むしろ Visual Studio で既定のフォーマットをしてから提出しています。)
さて、12月1日に実施された 三井住友信託銀行プログラミングコンテスト2019 では、別解が多くあり考察を楽しめる問題セットでした。
全体的にだいぶ簡潔に書ける回だったので、その中から問題 B, C, D を解説してみたいと思います。
B – Tax Rate
税込価格で N 円となるときの税抜価格はいくらか。
小数を考慮しなければならないため、第一感ではどんな値が適合するのかもやっとしますが、
そんなときは 1 から N までの全探索でも正解できます。LINQ を使って次のように書けます。
しっかり考察してみると実は、税抜価格が1だけ離れると税込価格も1以上離れることから税抜価格と税込価格は1対1に対応し、
税込価格 N に対する税抜価格はたかだか1個存在することがわかります。
また、 1.08X ≥ N つまり X ≥ N / 1.08 であることから、X の候補は N / 1.08 の天井 (ceiling) に限られます。
(これより 1 以上大きい整数の税込価格は N+1 以上になってしまう。)
あとはこれの税込価格が実際に N に一致するかどうかを確かめれば OK です。
C – 100 to 105
合計価格がちょうど X 円となるような買い物ができるか。
商品の価格の差が1円単位なので、商品の個数が N のとき、合計価格の候補は 100N ≤ X ≤ 105N の範囲の整数値となります。
そこでこの問題も、やはり安全策の全探索で通ります。
では今度もまたしっかり考察してみます。
商品の個数 N が [X / 100] より大きい場合は、合計価格は X を超えてしまいます。
また、N が [X / 100] より小さい場合に 100N ≤ X ≤ 105N を満たしているとすると、N+1 もこれを満たしているはずです。
したがって N = [X / 100] の場合のみを調べればよく、次のようなコードで書けます。
D – Lucky PIN
半角数字からなる文字列 S から3文字を取り出してその順に並べたものは何種類あるか。
例によって 000 から 999 までを全探索します。
たぶんこれが一番短いと思います (当社比)
いちおう次に計算量を考慮して別解を考えてみましょう。
まず前処理として、どの文字がどのインデックスに現れるかを取得できるように辞書を作っておきます。
この辞書のキーはたかだか10種類です。
そして1文字目から順に、選択可能なインデックスの範囲から文字を選択していきます。
3文字目を選ぶときは、候補のうち最後のインデックスが2文字目のインデックスより大きければ成立します。
多重の foreach 文を使って探索してもよいのですが、今回は C# のクエリ式を使ってみます。
クエリ式は普段はそれほど使わないのですが、このようにコレクションの入れ子構造を平坦化 (flatten) するときは見やすくなると思います。通常の LINQ では SelectMany メソッドに相当します。
計算量は、1文字目が10、2文字目が N (たかだか N 文字しかない)、3文字目が10のため、全体で O(100・N) です。
また、2文字目のインデックスを探索するところを二分探索にすれば O(1000・logN) となります。
ただし、前処理が少なくとも O(N) であるためそちらのほうが影響するかもしれません。
次回: 二分探索のライブラリ化
