CODE FESTIVAL 2015 本戦E「ショートコーディング」

Tweet

Pocket

こんばんは。

DDCCの予選通過のメールも無事に届き、2週連続で東京に行くことになりました。

さて、CODE FESTIVAL 2016の本戦が近づいてきたので、本日は去年の本戦の過去問を解いてみました。

その中で、解説スライドの模範解答と異なる方針でACした問題があったので紹介しておきます。

問題はE問題の「ショートコーディング」という問題です。

“!”は0以外を0に、0を1にする単項演算子で、”-“は数を-1倍する単項演算子です。これが後ろから適用されていきます。

たとえば、”-!–!!!-“に5を入力すると、

-!–!!!-(5) → -!–!!!(-5) → -!–!!(0)

→ -!–!(1) → -!–(0) → -!-(0)

→ -!(0) → -(1) → 1

となり、”1″が出力されます。（ちなみに0を入力すると0が返ります）

実は、この”-!–!!!-“は、”-!!”とまったく同じ効果のコードになります。

このように、与えられた演算子列を、（-256から256までのすべての整数入力に対して）同じ効果を持つ演算子列の中で最も短いものに置き換えるのがこの問題です。

以上を理解した上で、考えていきましょう。

出力は5通りだけ

この問題のポイントは、出力が5通りしかないことです。

!演算子は、1以外を0に、0を1にし、-演算子は正負を反転させるので、!演算子が1つでもあれば、出力は0か1か-1しかあり得なくなります。

例えば入力が2のときは、0, 1, -1, 2, -2 の5通りになります。

さらに、一般的に、入力がaなら出力は 0, 1, -1, a, -a の5通りのみになります。

また、ある0,1,-1でないaに対して、上記のどの出力であるかが分かったとき、他の0,1,-1でないbについても、上記の対応する出力が得られます。（2を-2にすれば3を-3にする、4を0にすれば8も0にする、など）

0だけは特殊なので、「0に対する出力」と「2に対する出力」が分かれば、全ての入力に対する出力が分かったのと同じになります（3の場合、-4の場合、などを考える必要が無い）。

このことは、以下の考察を含めてさらによく理解されます。

「0」と「0以外」を行き来する

整数を「0」と「0以外」に分けて考えたとき、”!”演算子は違う方へ移動させ、”-“演算子はこのカテゴリーに影響を与えません。

すなわち、!(0)=0以外、!(0以外)=0、-(0)=0、-(0以外)=0以外、となります。

したがって、「0→0、2→0以外」なら”!”の個数は偶数個、「0→0以外、2→0」なら”!”の個数は奇数個となります。

また、「2→2または2→-2（このとき必ず0→0）」の場合は、コードに”!”は含まれません（これが含まれると出力は0,1,-1に限られるため）。

以上より、以下のように最短コードを得ることができます。

• 0→0なら、”!”は偶数個。入力2の出力で以下のように判断
  • 2→1なら、”!”が2以上の偶数個で”-“が不要なので “!!”
  • 2→-1なら、上記に”-“を付け足した “-!!”
  • 2→2なら、そのままなので “”（空文字列）
  • 2→-2なら、”!”が無くて”-“が奇数個なので “-“
• 0→1なら、”!”は奇数個、必ず2→0なので”-“が不要だから “!”
• 0→-1なら、”!”は奇数個、2→0となるが”-“が奇数個必要で “-!”

与えられた元のコードに対して0, 2を入力したときの結果をシミュレートして、上記の分類で判断すればOKとなります。

以上を実現したのが、この提出コードです→ http://code-festival-2015-final-open.contest.atcoder.jp/submissions/978144

重要箇所を抜き出したのが以下のC#コードです。

Tweet

Pocket