yukicoder No.353 ヘイトプラス:プラス記号なしで足し算を行う複数の方法
昨夜、yukicoderにて開催されたyukicoder April Contestに私は参加しました。この記事では、コンテスト中に私が解けた問題の一つである、No.353 ヘイトプラス - yukicoderという問題について、備忘録を兼ねていくつかの解き方を示します。なお、この中には私が自ら思いついたものだけではなく、コンテスト後に調べて知ったものもあります。また、これら以外の解き方も存在するかもしれません。
問題の趣旨
非負整数 ()が与えられるので、を出力せよ。ただし、ソースコードに+
を含めてはならない。
解き方と解答例
どうにかして+
を使わずに加算を行う必要があります。たとえば以下のような方法が考えられます。ただし、言語によってはとりにくい方法があるかもしれません。
被演算子を要素に持つ配列/リストの総和を求める方法
を配列やリストに入れ、その総和を求めれば、を求めたことになります。これは私がコンテスト中に思いついた方法です。配列/リストの総和を求める関数の例としては、C++のstd::accumulate
*1、HaskellやPythonなどのsum
が挙げられます。
C++のstd::accumulate
を用いた例を以下に示します。
#include <cstdlib> #include <iostream> #include <numeric> #include <vector> template <typename T> T add(T a, T b) { std::vector<T> v = {a, b}; return std::accumulate(v.begin(), v.end(), 0); } int main(){ int a, b; std::cin >> a >> b; std::cout << add(a, b) << std::endl; return EXIT_SUCCESS; }
コンテスト中に私が提出したHaskellコードを以下に示します。大まかには、標準入力からgetLine
で1行読み取り、空白区切りの文字列をwords
で文字列のリストにし、map read
でそれぞれの文字列を整数にし、sum
で総和を求め、print
で出力しています。
main :: IO () main = print . sum . map read . words =<< getLine
引き算を用いる方法
を利用するという方法もあります。この方法にはコンテスト後の生放送を通じて気づきました。これはさまざまな言語で使えるであろう方法です。次に示すのはC#による解答例です。
using System; using System.Linq; namespace yukicoder { class yukicoder0353 { static int Add(int a, int b) { return a - (-b); } static void Main(string[] args) { var xs = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray(); Console.WriteLine(Add(xs[0], xs[1])); } } }
また、次のコードはSchemeによる解答例です。
#!/usr/bin/env gosh (let* ((a (read)) (b (read))) (print (- a (- b))))
関数形式の演算子を用いる方法
言語によっては、+
のような基本的な演算子と同じ働きをする関数を標準で利用できます。この方法にはコンテスト後に気づきました。以下に、Pythonのoperator.add
を使ったコードを示します。
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import operator def main(): print(operator.add(*map(int, input().split()))) if __name__ == '__main__': main()
ビット演算による方法:全加算器
以下に示すGoコードのように、ビット演算を用いて足し算を実現することもできます。これは足し算を使わずに足し算する — KaoriYaを参考にしたものです。同記事にあるように、これは全加算器(cf. wikipedia:加算器)と呼ばれる論理回路をコードに直したものです。
package main import "fmt" func main() { // Based on http://www.kaoriya.net/blog/2013/02/04/ var a, b, c int fmt.Scan(&a, &b) for b != 0 { c = (a & b) << 1 a ^= b b = c } fmt.Println(a) }
ポインタを用いた方法
主婦でも出来る!? 算術演算子を使わない算術演算 - Folioscopeで詳しく書かれているように、ポインタや配列参照演算子[]
を駆使して整数の足し算を行うこともできます。