AT_xmascon18_e Exclusive☆OR

[problemUrl]: https://atcoder.jp/contests/xmascon18/tasks/xmascon18_e 整数 $ N $ が与えられたとき，以下の仕様を満たすプログラムのうち，プログラム中での NOT の使用回数が最小のものを $ 1 $ つ出力せよ (NOT の使用回数が最小でないときも，後述のように部分点が与えられる場合がある)． プログラムの入力は $ N $ 個のブール変数 $ b_0,\ b_1,\ \ldots,\ b_{N-1} $ であり，これらから $ 2 $ 個を選んで XOR をとった値 $ b_i\ \operatorname{XOR}\ b_j $ をすべて求めたい． プログラムは以下の $ N\ +\ N^2\ +\ 10^5 $ 個のブール変数 (true または false の値をとる) を扱うことができる： - $ \mathrm{in}[i] $ ($ i\ =\ 0,\ 1,\ \ldots,\ N\ -\ 1 $) - $ \mathrm{out}[i][j] $ ($ i\ =\ 0,\ 1,\ \ldots,\ N\ -\ 1 $，$ j\ =\ 0,\ 1,\ \ldots,\ N\ -\ 1 $) - $ \mathrm{a}[k] $ ($ k\ =\ 0,\ 1,\ \ldots,\ 10^5\ -\ 1 $) プログラムは $ 0 $ 行以上 $ 10^5 $ 行以下からなり，上から下へと実行される．各行は - `変数 = 変数 AND 変数` - `変数 = 変数 OR 変数` - `変数 = NOT 変数` のいずれかの形であり，右辺の計算結果を左辺の変数に代入することを表す． 実行開始時に，各 $ \mathrm{in}[i] $ は入力 $ b_i $ で，各 $ \mathrm{out}[i][j] $ および各 $ \mathrm{a}[k] $ は false で初期化される．実行終了時に，各 $ \mathrm{out}[i][j] $ の値は $ b_i\ \operatorname{XOR}\ b_j $ でなければならない．

入力は以下の形式で標準入力から与えられる。 > $ N $

問題文の仕様を満たす，NOT の使用回数が最小のプログラムを $ 1 $ つ出力せよ． 採点結果の `AC` は，問題文の仕様を満たすプログラムを出力したことを表す．

### ストーリー くろうさ「XOR は甘え」 しろうさ「まーた始まった」 くろうさ「AND と OR は許してあげる」 しろうさ「えっとえっと」 くろうさ「否定はよくないよね〜うんうん」 しろうさ「否定ってもしかして NOT のこｔ くろうさ「というわけで今年もがんばってねっ」 ### 制約 - $ 1\ \le\ N\ \le\ 16 $ ### 部分点 - $ N\ \le\ 2 $ を満たすデータセットに正解した場合は，$ 10 $ 点が与えられる． - $ N\ \le\ 3 $ を満たすデータセットに正解した場合は，上記とは別に $ 10 $ 点が与えられる． - $ N\ \le\ 4 $ を満たすデータセットに正解した場合は，上記とは別に $ 20 $ 点が与えられる． - $ N\ \le\ 8 $ を満たすデータセットに正解した場合は，上記とは別に $ 20 $ 点が与えられる． - 追加制約のないデータセットに正解した場合は，上記とは別に $ 40 $ 点が与えられる． - 各データセットについて，正解ではないが，すべての入力について NOT の使用回数が $ N\ -\ 1 $ 以下の正しいプログラムを出力した場合，そのデータセットの配点の $ 20 $ % が与えられる． ### Sample Explanation 1 このプログラムは，$ 3 $ 回の NOT の使用によって XOR をすべて計算している．ただし，NOT の使用回数はこれが最小ではない． $ N\ =\ 3 $ の場合はこちらで手で遊べる． 表示/非表示 AND と OR はふたつ，NOT はひとつ選んでから演算子ボタンを押そう！ (動作確認：Chrome 70, Firefox 60) var numVars = 0; var selectedDiagrams = {}; function init() { initButtons(); initBoard(); } function initButtons() { const buttons = document.getElementById('buttons'); for (op of \['Reset', 'Undo', 'AND', 'OR', 'NOT'\]) { const button = document.createElement('input'); button.type = 'button'; button.id = 'button-' + op; button.value = op; button.addEventListener('click', operate.bind(null, op)); buttons.appendChild(button); } } function initBoard() { const board = document.getElementById('board'); board.appendChild(createDiagram('in\[0\]', 0b10101010)); board.appendChild(createDiagram('in\[1\]', 0b11001100)); board.appendChild(createDiagram('in\[2\]', 0b11110000)); } function resetProgram() { document.getElementById('program').innerHTML = ''; } function addProgram(line) { document.getElementById('program').innerHTML += line + '\\n'; } function undoProgram() { const program = document.getElementById('program'); const str = program.innerHTML; program.innerHTML = str.slice(0, str.lastIndexOf('\\n', str.length - 2) + 1); } function resetBoard() { const board = document.getElementById('board'); for (diagram of board.childNodes) { unselect(diagram); } for (; numVars > 0; --numVars) { const diagram = board.lastChild; board.removeChild(diagram); } } function addDiagram(name, value) { const board = document.getElementById('board'); const diagram = createDiagram(name, value); board.appendChild(diagram); } function operate(op) { const diagrams = Object.values(selectedDiagrams); switch (op) { case 'Reset': resetProgram(); resetBoard(); break; case 'Undo': if (numVars > 0) { undoProgram(); const diagram = board.lastChild; unselect(diagram); board.removeChild(diagram); --numVars; } break; case 'AND': if (diagrams.length == 2) { var resultName = 'a\[' + (numVars++) + '\]'; addProgram(resultName + ' = ' + diagrams\[0\].name + ' AND ' + diagrams\[1\].name); addDiagram(resultName, diagrams\[0\].value & diagrams\[1\].value); unselect(diagrams\[0\]); unselect(diagrams\[1\]); } break; case 'OR': if (diagrams.length == 2) { var resultName = 'a\[' + (numVars++) + '\]'; addProgram(resultName + ' = ' + diagrams\[0\].name + ' OR ' + diagrams\[1\].name); addDiagram(resultName, diagrams\[0\].value | diagrams\[1\].value); unselect(diagrams\[0\]); unselect(diagrams\[1\]); } break; case 'NOT': if (diagrams.length == 1) { var resultName = 'a\[' + (numVars++) + '\]'; addProgram(resultName + ' = ' + 'NOT ' + diagrams\[0\].name); addDiagram(resultName, ((1 << 8) - 1) ^ diagrams\[0\].value); unselect(diagrams\[0\]); } break; } } function toggle(diagram) { (diagram.selected ? unselect : select)(diagram); } function select(diagram) { if (!diagram.selected) { if (Object.keys(selectedDiagrams).length < 2) { diagram.selected = true; diagram.classList.add('selected'); selectedDiagrams\[diagram.name\] = diagram; } } } function unselect(diagram) { if (diagram.selected) { diagram.selected = false; diagram.classList.remove('selected'); delete selectedDiagrams\[diagram.name\]; } } function createDiagram(name, value) { const SIZE = 150; const diagram = document.createElement('canvas'); diagram.name = name; diagram.value = value; diagram.selected = false; diagram.width = SIZE; diagram.height = SIZE; diagram.addEventListener('click', toggle.bind(null, diagram)); var context = diagram.getContext('2d'); context.transform(1, 0, 0, -1, 0, SIZE); const radius = SIZE \* 0.3; const xs = \[SIZE / 2, SIZE / 2 - radius / 2, SIZE / 2 + radius / 2\]; const ys = \[SIZE \* 0.45 + radius / Math.sqrt(3), SIZE \* 0.45 - radius / 2 / Math.sqrt(3), SIZE \* 0.45 - radius / 2 / Math.sqrt(3)\]; for (var t = 0; t < 8; ++t) { context.fillStyle = ((value >> t) & 1) ? 'gold' : 'white'; context.beginPath(); switch (t) { case 0: context.moveTo(0, 0); context.lineTo(SIZE, 0); context.lineTo(SIZE, SIZE); context.lineTo(0, SIZE); context.lineTo(0, 0); break; case 1: context.arc(xs\[0\], ys\[0\], radius, 0, Math.PI \* 2, false); break; case 2: context.arc(xs\[1\], ys\[1\], radius, 0, Math.PI \* 2, false); break; case 3: context.arc(xs\[0\], ys\[0\], radius, Math.PI, Math.PI \* 5 / 3, false); context.arc(xs\[1\], ys\[1\], radius, 0, Math.PI \* 2 / 3, false); break; case 4: context.arc(xs\[2\], ys\[2\], radius, 0, Math.PI \* 2, false); break; case 5: context.arc(xs\[0\], ys\[0\], radius, Math.PI \* 4 / 3, 0, false); context.arc(xs\[2\], ys\[2\], radius, Math.PI / 3, Math.PI, false); break; case 6: context.arc(xs\[1\], ys\[1\], radius, Math.PI \* 5 / 3, Math.PI / 3, false); context.arc(xs\[2\], ys\[2\], radius, Math.PI \* 2 / 3, Math.PI \* 4 / 3, false); break; case 7: context.arc(xs\[0\], ys\[0\], radius, Math.PI \* 4 / 3, Math.PI \* 5 / 3, false); context.arc(xs\[1\], ys\[1\], radius, 0, Math.PI / 3, false); context.arc(xs\[2\], ys\[2\], radius, Math.PI \* 2 / 3, Math.PI, false); break; } context.fill(); } for (var i = 0; i < 3; ++i) { context.beginPath(); context.arc(xs\[i\], ys\[i\], radius, 0, Math.PI \* 2, false); context.stroke(); } context.transform(1, 0, 0, -1, 0, SIZE); context.textAlign = 'left'; context.textBaseline = 'top'; context.fillStyle = 'black'; context.fillText(name, 5, 5); return diagram; } window.addEventListener('load', init); $ (function()\ { $('#game-btn').click(function() { $('#game').slideToggle(); });} );