Xmas Contest 2017 C 問題 Revenge of Kurousa 解説

Xmas Contest 2017 の C 問題「Revenge of Kurousa」の解説です。

問題概要

a〜z の 26 個の 8bit 整数型の変数がある。はじめ a に入力の値が入っており、b〜z は 0 である。できる操作は

  • ビットごとの論理演算: 16 種類ある論理演算のうち好きなものを選び、ビットごとの論理演算を行える（実質 Z = X NAND Y ができるのと同じ）。
  • 加算

の計 17 種類。この操作だけを使って a の値をインクリメントする（255 は 0 にする）ようなプログラム（操作の列）を書け。

加算を使う回数が最小に抑えられていれば 100 点、最小の2倍以下に抑えられていれば 30 点が得られる。

解説

最初にネタバレをすると、必要な加算の最小回数は 1 回です。よって、30 点をとるためには 2 回の加算でインクリメントする必要があります。

部分点解法（加算2回）

最初に 1 を作って、それを a に加算することを考えます。よって、1 を加算 1 回で作れれば十分です。

1 を作るには、たとえば以下のようにします。

  • 11111111 を作る（b = b 1111 b など）
  • 11111110 を作る（c = b + b）
  • 00000001 を作る（d = b 0110 c、つまり d = b xor c）
満点解法（加算1回）

以下では整数は全て mod 256 で考えます。要は 255 （2進数で 11111111） のことを -1 とか書きます。

まず、ビットごとの論理演算だけで入力値 A と 0 だけから作れる数はほとんどありません。具体的には以下の 4 種類しか作れません。

  • 0
  • A
  • -1 （b = b 1111 b などとして作る)
  • -A-1 （255-A と同じ、要は not A）

なので、ここで 1 回加算を行う必要があります。0 と何かを足しても意味がなく、A + (-A-1) = -1 はすでに -1 が作れる以上意味がないので、加算した結果として意味があるのは

  • A-1
  • -A-2

のいずれかです。

ここで not X が 255 - X = -X - 1 だったことを思い出せば

  • not (-A-2) = 255 - (-A-2) = A + 1

となりインクリメントができました。