ブログのとさか

技術的な話をしたりしなかったり

#MakeGirlsMoe でもっと遊べるプログラムを書いた(実質百合画像生成)

MakeGirls.moe

二次元キャラを自動生成してくれるMakeGirls.moeが今話題になっています。
f:id:tosaka2:20170815164557p:plain

make.girls.moe

今までの画像生成手法と比べてもかなり綺麗な画像が出力されるので驚きました。
PFNでアルバイトしている方が作ったそうです。流石…

ネットの評判(ニコニコの某動画)を見てみると、「ただパーツを組み合わせただけだろ」とか、「データベースからランダムに選んでるだけでしょ」といったコメントをしている人がいて、 いかに高度な画像生成ができているかがわかります。
技術的な詳細は公式ブログにまとまっています。

MakeGirls.moe Official Blog

ここでGANとは~~みたいな話をしてもいいのですが、今回はこのWebサービスでもっと遊ぶためのプログラムを書いたので導入方法と使い方を紹介します。

このプログラムを導入すると「2つのイラストの中間のイラスト」を出力することができます。
イメージとしては以下のツイートの通り。(実質百合では?)

導入方法

画像で説明していきますが、この画像を作ったときより少しアップデートされていて微妙に差があります。
Google Chromeでしか動作確認していません。MakeGirls.moeのアップデートですぐに動かなくなるかもしれないので注意してください。

工程1

※同じ階層にあるmain(なんちゃら).jsを開けばOKです。
f:id:tosaka2:20170815165154p:plain

工程2 (8/16 編集)

プログラムを更新したので画像と説明が少し異なります。

24661行目ではなく、return t.generate()から始まる行の左の数字をクリックしたください。(2017/8/16 現在 25066行目)
Ctrl+Fを押してreturn t.generate()で検索すれば一箇所だけヒットすると思います。
また、Consoleが表示されてない人は一度Consoleタブに切り替えても良いです。(Consoleタブの場所は工程3の画像に書いてあります。)
f:id:tosaka2:20170815165201p:plain
以下のプログラムをコピペしてください。

// return t.generate()の行にブレークポイント
var getObject = () => t;

var getState = () => getObject().state;
var getOption = () => getState().options;
var getNoise = () => getState().gan.noise;
var getNoiseOrigin = () => getState().gan.noiseOrigin;
var isRunning = () => getState().gan.isRunning;

// NoiseをFixedに
var fixNoise = () => getOption().noise = 1;
// NoiseをRandomに
var randomNoise = () => getOption().noise = 0;

// Noiseを出力
var printNoise = () => "[" + getNoise().join(',') + "]";
// Noiseを設定
var setNoise = a => { 
    if (isRunning()) return; 
    cn = getNoise(); 
    for (let i = 0; i < a.length; i++) {
        cn[i] = a[i];
    }
};

var setNoiseOrigin = a => {
    if (isRunning()) return; 
    getObject().setNoiseOrigin(a);
}

// 中断フラグ
var _isAborted = false;
var _selected = [[],[]];

// Generate
var generate = async () => { 
    if (isRunning()) return;
    await getObject().generate();
};
// NoiseをRandomにしてGenerate
var generateByRandom = async () => { randomNoise(); await generate(); };
// 引数で指定したNoiseでGenerate
var generateBy = async a => { fixNoise(); setNoise(a); await generate() };
var cancel = () => { _isAborted = true; };

// ベクトルの操作
var add = (a, b) => a.map((x, i) => x + b[i]);
var sub = (a, b) => a.map((x, i) => x - b[i]);
var times = (a, t) => a.map((x, i) => x * t);
var interpolate = (a, b, p) => a.map((x, i) => x * (1-p) + b[i] * p);

// Current Noiseにした時にできるだけ絵が変わってしまわないようにする
var calculatebackToPixel = v => {
    let calc = (b, g) => Math.sqrt( -2.0 * Math.log( b ) ) * Math.cos( 2.0 * Math.PI * g );
    let f = (bg) => calc(1-bg[0]/256, 1-bg[1]/256);
    
    // 乱択のほうが速そう
    for (let b = 1; b < 256; b++) {
        let u = Math.sqrt( -2.0 * Math.log( 1 - b/ 256) );
        if (v / u < -1 || v / u > 1) continue;
        let pg = (1 - (Math.acos(v / u) / (2 * Math.PI))) * 256;

        let g = Math.floor(pg + 0.5); //四捨五入
        if (g < 0 || g >= 256) continue;
        //console.log([b, g]);
        return [b, g];
    }
    throw "error";
}

var noiseToPixels = a => a.map(calculatebackToPixel);
var pixelToNoiseOrigin = ps => ps.map(x => [1 - x[0]/256, 1 - x[1]/256]);
var noiseToNoiseOrigin = a => pixelToNoiseOrigin(noiseToPixels(a));

var downloadImage = (img = _selected[0][0], name = "mgm.png") => {
    img = img || document.body.querySelector(".result-canvas").firstChild;
    let a = document.createElement("a");
    a.href = img.src;
    a.target = "_blank";
    a.download = name;
    a.click();
}

// 生成済みの画像を下に表示
var addImg = (src, noise = null, noiseOrigin = null) => {
    let results = document.body.querySelector(".imgs");
    if (!results) {
        results = document.createElement("div");
        results.className = "row imgs";
        document.body.querySelector(".App").appendChild(results);
    }
    
    let img = document.createElement("img");
    
    noise = noise || getNoise();
    noise = noise.map(x => x);
    img.src = src;
    
    img.onclick = () => {
        console.log("[" + noise.join(',') + "]");
        console.log(img);
        if (_selected[1][1] && _selected[0][1] != _selected[1][1]) {
            _selected[1][1].style.border = "none";
        }
        _selected = [[noise, img, noiseOrigin], _selected[0]];
        if (_selected[1][1]){
            _selected[1][1].style.border = "dashed";
            _selected[1][1].style.opacity = 1.0;
        }
        _selected[0][1].style.border = "solid";
        //img.style.opacity = 0.5;
        if (_selected[1][1] && _selected[0][1] == _selected[1][1]) {
            downloadImage(img);
        }
    }

    results.insertBefore(img, results.firstChild);
    return img;
}

// 下に表示してある画像をクリア
var clearImgs = () => {
    let imgs = document.body.querySelector(".imgs");
    for (let x of imgs.children) {
        x.onclick = null;
        x.src = "";
    }
    imgs.parentNode.removeChild(imgs);
}

// 下に表示してある画像を一枚消す
var deleteImg = img => {
    img.onclick = null;
    img.src = "";
    img.parentNode.removeChild(img);
}


// aとbに指定したNoiseでn枚画像補間し,下に表示.wait_secはGenerateにかかる時間(実行環境により調整).
var generateInterpolations = async (n, a, b, im1 = null, im2 = null) => {
    if (isRunning()) return;
    let result = document.body.querySelector(".result-canvas").firstChild;
    // すでに生成された画像かどうか
    let ok = im1 && im2;
    
    if (ok) addImg(im1.src, a);
    for (let i = ok ? 1 : 0; i < (ok ? n - 1 : n); i++) {
        if (_isAborted) {
            _isAborted = false;
            break;
        }
        let noise = interpolate(a, b, i / (n - 1));
        await generateBy(noise);
        addImg(result.src, noise);
    }
    if (ok) addImg(im2.src, b);
}

// RandomなNoiseでn枚画像生成し,下に表示.wait_secはGenerateにかかる時間(実行環境により調整).
var generateRandomImages = async n => {
    if (isRunning()) return;
    let result = document.body.querySelector(".result-canvas").firstChild;

    for (let i = 0; i <= n - 1; i++) {
        if (_isAborted) {
            _isAborted = false;
            break;
        }
        await generateByRandom();
        addImg(result.src);
    }
}

// 指定したオプションの値をfromからtoまで動かして生成。
// param: オプション, n: 枚数, a: ノイズ
var generateSomeParams = async (param, n, a, from, to) => {
    if (isRunning()) return;
    a = a || getNoise();
    let result = document.body.querySelector(".result-canvas").firstChild;
    let op = getOption();
    let moto = op[param];
    for(let i = 0; i < n; i++) {
        if (_isAborted) {
            _isAborted = false;
            break;
        }
        op[param] = from + ((to - from) * i / (n - 1));
        await generateBy(a);
        addImg(result.src, a);
    }
    op[param] = moto;
}

// ボタン追加処理
var addButton = (text, func) => {
    let buttons = document.body.querySelector(".exbtns");
    if (!buttons) {
        buttons = document.createElement("div");
        buttons.className = "row exbtns";
        document.body.querySelector(".options-container").lastChild.appendChild(buttons);
    }
    let b = document.body.querySelector(".btn-primary").cloneNode();
    b.textContent = text;
    b.onclick = func;
    buttons.appendChild(b);
}


(() => {
    let buttons = document.body.querySelector(".exbtns");
    if (buttons) {
        buttons.parentNode.removeChild(buttons);
    }
    
    addButton("生成10", () => generateRandomImages(10));
    addButton("100", () => generateRandomImages(100));
    addButton("1000", () => generateRandomImages(1000));
    addButton("∞", () => generateRandomImages(100000000000000000));
    addButton("補間", () => generateInterpolations(10, _selected[0][0], _selected[1][0], _selected[0][1], _selected[1][1]));
    addButton("百合", () => generateInterpolations(3, _selected[0][0], _selected[1][0], _selected[0][1], _selected[1][1]));
    addButton("中断", () => { cancel() });
    // isRunning弾かないとgetNoise()でバグる
    addButton("下へ", () => {
        if (isRunning()) return;
        addImg(document.body.querySelector(".result-canvas").firstChild.src, getNoise());
    });
    addButton("上へ", async () => {
        await generateBy(_selected[0][0]);
        setNoiseOrigin(noiseToNoiseOrigin(getNoise()));
    });
    // 選択したやつなのか、表示してる画像なのかわかりにくいけど許して
    addButton("口パク", () => generateSomeParams("open_mouth", 10, _selected[0][0], 1, -1));
    addButton("笑顔", () => generateSomeParams("smile", 10, _selected[0][0], 2, -1));
    addButton("Blush x2", () => getOption().blush = 2);
    addButton("Smile x2", () => getOption().smile = 2);
    addButton("Open Mouth x2", () => getOption().open_mouth = 2);
    addButton("Hat x2", () => getOption().hat = 2);
    addButton("x3", () => getOption().hat = 3);
    addButton("Ribbon x2", () => getOption().ribbon = 2);
    addButton("Glasses x2", () => getOption().glasses = 2);
    addButton("x3", () => getOption().glasses = 3);
    addButton("クリア", () => clearImgs());
    addButton("1枚削除", () => {
        deleteImg(_selected[0][1]);
        _selected[0] = _selected[1];
    });

    /*
    // デフォルトオプション
    op = getOption();
    op.hair_color = 11;
    op.hair_style = 1;
    op.eye_color = 8;
    op.blush = -1;
    op.smile = 1;
    op.open_mouth = 1;
    op.hat = -1;
    op.ribbon = 1;
    op.glasses = -1;
    */ 
})();

工程3

同じく24661行目ではなくなっていますが、前の工程でクリックした場所と同じ場所をクリックしてください。
f:id:tosaka2:20170815165137p:plain

工程4

最後の工程です。
この画像を作ったときから少しプログラムを変えたのでボタンの数が増えています。 f:id:tosaka2:20170815165145p:plain

画像が重複して表示されてしまう人(8/16 追記)

プログラム中のwait_sec = 7となっている場所(2箇所あり)を変えてください。
これは生成を何秒待つ必要があるかを秒単位で指定するパラメータです。手元の実行環境の生成速度に合わせてデフォルトで7秒にしていますが、これより生成が速い場合は短く、遅い場合は長くしてください。

ちなみにプログラムを更新するときははじめからやり直す必要はなく、最初の2行だけを飛ばしてConsoleタブにコピペすれば大丈夫です。

この問題は解決しました(8/16)

既知のバグ

- 「補間」で生成した画像を元に補間ができない。(ノイズが正しく_tmpsに入っていない。)→多分直った(8/16)

その他の機能

「中断」を押すと画像の生成を中断できます。
生成した画像の中から好きな画像を2枚選んで「補間」を押すと10枚の間のイラストを生成します。
f:id:tosaka2:20170815180203j:plain

「複製」は元の画像表示領域にある画像を下に表示させます。
「クリア」は下の画像領域の画像をすべて消します。
「百合」は選択した2つのイラストの中点の画像を1枚だけ生成します。(左右に元画像を表示します。)

「Hat x2」等ではHatオプションを強調できます。通常通りHat Onにしただけでは上手く生成できなかったイラストにも、これを押してから生成すればはっきり帽子が出ることが多いです。
- Hat On
f:id:tosaka2:20170818173539j:plain
- Hat x3
f:id:tosaka2:20170818173519j:plain

「下へ」を押すと下の画像表示領域に画像が複製されます。 「上へ」を押すと上の元の画像表示場所に画像が再生成されます。(「Current Noise更新」はここに吸収されました。)

下の画像をダブルクリックすると画像がダウンロードできます。

また、Consoleタブからプログラムを入力すれば他にも色々な操作が可能です。詳しくは上記プログラムを見てみてください。(適当なJavaScriptの知識で書いてあるのは許して)

生成した画像

とりあえず100枚生成して気に入った2枚を選んで補間すると良いのが出たりします。
f:id:tosaka2:20170815173205p:plainf:id:tosaka2:20170815173330p:plainf:id:tosaka2:20170815172920p:plainf:id:tosaka2:20170815173018p:plainf:id:tosaka2:20170815172348p:plainf:id:tosaka2:20170815172350p:plainf:id:tosaka2:20170815172352p:plainf:id:tosaka2:20170815172354p:plain

他にもたくさん良いのがあるんですがとりあえずこの辺で。

補足

自動で100枚も生成させたらサーバの負荷になるだろ!と言われそうなので一応捕捉しておくと、MakeGirls.moeの画像生成処理は全てブラウザ上で行われています。
WebAssemblyでモデルを動かしてくれるWebDNNというライブラリが使われています。また、Macの場合はGPUを利用して100倍高速に実行できるそうです。うらやましい…

詳しくは以下のFaster generationを見てください。
make.girls.moe

ひとりごと

Chromeデバッガを使わないといけない行はgetObject = () => t;の部分だけなので、このオブジェクトがデバッガ無しで取ってこれればもっと楽に導入できるんだけどなぁ。
どなたか即時関数内で定義されているオブジェクトを取得する方法を知っている人がいたらおしえてください。

wait_secは環境によって異なる値なのに直書きしてしまったのでハマってる人がいるみたいです。アレなプログラムで申し訳ない。改良するかも?
本当はPromiseオブジェクトとかを取ってきてちょうどいい時間待てれば良いんですが、それが簡単に出来るのかは未検証です。
→できました(8/16)

8/16 追記

GIFにしている方がいるようです。

口パク生成に関してはこちら

qiita.com

口パクボタン追加しました(8/16)
補間ボタンと同じように下に表示されている画像を選択してから実行してください。
f:id:tosaka2:20170816171053p:plain
他にも笑顔/メガネ/1枚削除(下の表示から)/ダブルクリックで保存機能をつけました。

gif生成サービスと組み合わせると楽しい!
GIFアニメーション画像作成ツール - フォトコンバイン f:id:tosaka2:20170816200705g:plain

k-meansとニューラルネットと機械学習と...

もともとk-meansにDeep Forestのカスケード構造を導入したDeep k-meansみたいなものをやろうとしていましたが、あまりうまく行かなかったうえ、そこから得られる考察もあまり面白くなかったので、関連した違う話を書こうと思います。

おことわり

この記事に書いてあることはしっかりと裏を取って書いたことではありません。
解説記事というわけでもなく、考えたことのメモみたいなものです。間違い等ありましたらご指摘お願いします。

k-means

k-meansはk個のクラスタに対応するk個の代表点を定めます。データを分類する際は、そのデータと最も距離が近い代表点が属するクラスタに分類します。

ここでk=2のときを考えます。2つの代表点からの距離が等しくなる軌跡を図示すると、一つの超平面になります。この平面に対して点がどちら側にあるかどうかで属するクラスタが決定されるので、これはn次元空間において分離超平面であるといえます。

これを拡張すると、k>2のときは分離超平面が\displaystyle_ kC_2=k(k-1)/2個配置されると考えることができます。それぞれの超平面による分類結果は、代表点に対応するクラスタ、つまりクラスタiクラスタjの代表点p_ip_jによって配置される超平面の分類結果はiまたはjになるとします。すると、ある点が分類されるクラスタは、全ての超平面によってその点を分類した後、その結果の多数決を取ることによって決定できます。(選ばれるクラスタに分類される回数は常にk回になります。)

このように、k-meansはk個の代表点を用いることで_kC_2個の分離超平面を配置し、それらの分類結果をもとに最終的に属するクラスタを決定する手法であると解釈することもできます。(当然ですがこれはk-meansに限った話ではなく、幾つかの代表点を定めてそれらとの距離で分類する手法一般に言えることです。)

ニューラルネット

全結合ニューラルネットを構成する基本的な人口ニューロンについて考えます。人口ニューロンの結合をベクトルをw,バイアスをb,入力をx,活性化関数をfとすると、出力はf(wx+b)で表されます。するとwx+bは「『wを法線ベクトル,bを定数項とする分離超平面』と『x』の符号付き距離」に,|| w ||を掛けたものだと解釈することができます。詳しくは以下のPDFを見てください。

https://github.com/madoibito80/poem/blob/master/01.pdf

ニューラルネットの層はこの人口ニューロンを複数もっているので、ニューラルネットの1つの層は、複数の分離超平面による分類結果を返している事になります。さらにニューラルネットの層の出力を次の層の人口ニューロンの入力として多値分類を行うと、これはk-meansの時と同様に、複数の超平面による分類結果をもとに最終的な分類結果を決定する手法であると解釈できます。

転移学習的な(ここからポエム感が増します。)

k-meansとニューラルネットは複数の超平面を用いて分類した結果をもとに分類する手法であることがわかりましたが、この話はk-meansやニューラルネットに限らず、多値分類を行う機械学習モデル一般に言えることだと思います。(当たり前の話といえば当たり前の話です。) そう考えると、ニューラルネットの層の初期値を決定するのに、他の機械学習のモデルで得た超平面を用いる手法などがあっても良いような気がしますが、今流行ってないことを考えるとあまりうまく行かないのでしょうか? ラベル付きデータが少ないときなどに教師なしクラスタリングで得た超平面を用いたり、ニューラルネットよりも学習が速い機械学習器で得た超平面を用いたりするのはある程度有効そうな気はしなくもないですが、IMSATのような優れた教師なし学習方法が発展している今の時代には無用の長物なのかもしれません。
ただ、これに関しては後で実験するかもしれません。(Done is better than perfect.に則って実験する前にブログを書きました…)

[追記] 僕もまだちゃんと中身見ていませんが、k-meansでCNNの初期値を定めるのはうまくいくらしいです。

ニューラルネットと同等な表現

ところで、ニューラルネットでもk-meansのように点を決定する手法で分離超平面を配置することができます。(それは同時に法線ベクトルですが…)
学習するベクトルをvとして「座標vを通りvを法線ベクトルとする分離超平面」を配置すると、n次元空間においてはn個のパラメータのみによって全ての分離超平面が表現できます。このvを使ってニューラルネットを構築することも出来ます。
順伝播時には、vによって決定される分離超平面を表す法線ベクトルw=v、バイアス項b=-|| v ||^2とし、通常のニューラルネットと同様に計算します。
これで一つ学習するパラメータを減らしてニューラルネットが構築できたように見えますが、超平面が通る点、つまりバイアス項によってノルムが変化してしまうので、ニューラルネットと同等な表現力をもたせたい場合、実数kも同時に学習させて、出力をkwx+bとすれば良いです。

この表現を得ることで何か嬉しいことがあるのかと言われたら特には思いつきませんが、パラメータを1つでも減らしたい場面がもしあったら使える可能性がゼロでは無いかもしれません。その場合は活性化関数に渡す値を(wx+b)/|| w ||、つまり通常の超平面からの符号付き距離にすることが有効だと思います。(バイアス項によるノルムの変動の影響がなくすことができるため。この場合通常のニューラルネットで言うとノルムを1に常に正規化している状態と同じになり、「各超平面の重み」を表すことができなくなります。)(これに関しては実験を行おうと思います)
ただ、実数kを用いる表現では「法線ベクトルのノルムの意味」と「ベクトルと独立した実数の意味」が通常の人工ニューロンと逆になるという点は少し面白いかなとは思います。

また少し違う話ですが、人口ニューロンでは分離超平面からの符号付き距離を求めているところを、点からの距離にしても学習できるんじゃないかなと思っています。(もちろん式としては違うものが出てきます。また活性化関数も通常のものは使えなくなります。)
結局実験してみないとわからないので、後日試してみたいと思います。

所感

勢いで書いて数式書くのもサボったら非常に読みにくくなってしまいまいました。(追記: とりあえず数式は直しました)
k-meansもニューラルネットも50年以上前に発表されたものなので、今回書いたことはとうの昔に指摘されていることだろうなあとは思っています。

AtCoderのプログラミング入門教材 AtCoder Programming Guide for Beginners の宣伝

この記事はCompetitive Programming Advent Calendar 2016 12/10の記事です。

AtCoderのコンテンツとして、プログラミング入門の教材を作ることになりました。
AtCoder Programming Guide for Beginners」みたいな名前でやっていこうと思っています。

AtCoderのコンテンツなので、当然オンラインジャッジを最大元活用した内容にしていきます。
一応「競技プログラミングのためのプログラミング入門」ではなく、「オンラインジャッジを活用したプログラミング入門」です。 とはいえ、この教材で学び、ACの快感を知ってしまった人は競技プログラミングの世界に自然に入っていけるでしょうし、競技プログラミングの人口増加に繋がるかもしれません。

逐次公開しつつ、みなさんからの意見を受けてフィードバックしながらより良いものを作っていきたいと思っています。
進捗を報告したり、意見を受け付けたりするためのTwitterアカウントを作成したので、気軽にリプライやDMを送って下さい。よろしくお願いします!

内容

この教材の到達目標は「プログラミング初学者が様々なアルゴリズムを記述するために必要なプログラミング言語の文法知識を身に付ける」ことです。
言語はC++を採用します。

オンラインジャッジを活用したプログラミング入門なので、各項目について問題とジャッジを用意します。

まずは、「最速」でプログラムを書けるようになるため、最低限の文法知識を扱います。
AtCoder Biginner ContestのA問題とB問題のほぼ全てと、一部のC問題を解けるようにします。
その後は、アルゴリズムを記述するのに役立つ言語機能や、それまで「おまじない」的扱いを受けていた文法について説明します。

ただし、C++の言語仕様に詳しくなること自体は目的としていないため、詳細な文法の解説はしません。
また、保守性の高いプログラムの書き方や、高度なアルゴリズムとデータ構造等も扱いません。

現状の目次は以下のようなものを考えています。あくまで暫定なので、内容は順番は変化する可能性が高いです。

基礎

  • 導入
  • 出力
  • 四則演算
  • 変数(1)
  • 入力
  • if文
  • 条件演算子
  • bool型
  • 変数(2)
  • while文
  • for文
  • 文字列
  • 配列
  • STL(1)(関数のみ紹介)
  • 関数
  • 数値型とビット演算

繰り返し処理の応用

計算量

  • 計算量について

C++

以上の項目の他に↓のようなページがあったら良いかなぁと思っていますが、労力が余っていれば...くらいに思っています。

  • C++基本文法チートシート(基礎文法最速マスターみたいなもの)
  • プログラムの書き方について(インデント等)
  • 典型コンパイルエラー/バグ集

ちなみに、ポインタを扱うかどうか迷っています。平衡二分探索木とかを実装したかったら必要になるんですが、うーん...

対象者のより詳細な前提知識としては、基本的には中学二年生開始時程度の数学、英語知識を最低限求めるくらいのものにしようと思っています。
PCの知識は、アプリケーションのインストールと見ながらタイピングくらいはできるくらいを想定するつもりです。
説明が冗長になりすぎない範囲でできるだけハードルを下げたいと思っているので、実際には中学1年生でもわかるくらいの書き方になっていると思います。
中高の部活動から大学生以上まで広く使われる教材になったら良いなあと思っています。

明日のCompetitive Programming Advent Calendar 2016はmatsu7874さんの記事とhotpepsiさんの「バグ」です。

以下はおまけです。


プログラミング入門とオンラインジャッジ

オンラインジャッジを用いたプログラミング入門は非常に効率的だと思います。

プログラミングはプログラムを書かないと覚えられません。しかし、一般的な入門書でプログラミングを覚えようとすると、入門書に書いてあるコードを写経するだけで終えてしまう人が多いです。
また、ソフトウェア制作を通じたプログラミング入門も、GUI周りのAPIを覚えること等とプログラミング言語の文法を覚えることが混在してしまい、 プログラミング言語そのものの知識を身に付ける方法としてあまり効率的でない面があります。

それに対し、オンラインジャッジを用いたプログラミング入門では、学んだ文法を使う問題を解くことによって、より確実に知識を定着させることができます。
プログラミング言語以外で覚えなければならない要素もほとんどありません。

さらに、ACしていくことはかなりモチベーションに繋がります。入門書にも例題がついていることはありますが、基本自己採点になってしまいますし、答えが載っていないことすらあります。 オンラインジャッジでは、コンパイルと出力の確認だけとはいえ、ある程度確実な採点を行えますし、オンラインジャッジに「AC」と出るのは自己採点よりも強い快感があると思います。

一通り文法を学び、教材で用意した問題を解き終わった後も、他の問題を解いたり、開催されているコンテストに参加することによって、プログラムを書く能力を上げていくことができます。 「プログラミングに興味はあるけど、作りたいものがあるわけではない」という人は案外多く、そういった人たちにとってこのことは重要だと思います。

オンラインジャッジを活用した日本語のプログラミング入門教材は、僕の知る限り現状AOJ系のものだけです。この資料はAOJの資料とはまた違った価値を提供していきたいです。

教材作成者について

教材の構成等は「経験上」という曖昧な感覚から決めているため、どういう経験をしてきたのか、自分語りをしておきます。

僕は中高時代コンピュータ部の部長を務めていました。
部長として部員のレベルを上げるため、中1~高1くらいの人に対し、プログラミングをよく教えていました。対象者の前提知識が中学生程度なのは、このこととも関係しています。
プログラミングの入門教材を作るのは実は二度目で、中学3年生の時に部活の仲間とC#の入門教材を作ったことがあります。
コンピュータ部の宣伝として、コンピュータ部外の人にプログラミング講座を開催したりもしていたので、今までプログラミングを教えた人数は多分50人~100人(超大雑把)くらいでしょうか。
今回の教材ではそこでの経験を活かしていきたいと思っています。

競技プログラミング経験としては、JOI春合宿の出場経験があり、大学生になってから引き続きICPCに出場しています。
アルゴリズムを記述するのに役立つ言語機能」は実際の所、競技プログラミングで使われる言語機能のことですが、今まで見てきた競プロのソースでよく見る or 便利だと思ったものを扱っていきたいと思っています。

書いてる途中の感想

基礎のところは半分くらい書き上がってますが、やっぱ読みやすい文章書くのは難しいなあと感じています。 文章書くのが遅いので、この教材作成経験を通じて速くしていきたいですね。(まぁよく見ると文章量は大したこと無く、説明のほとんどがサンプルコードみたいなことが多いですが...)
「あ、これも説明しないといけないんだった」みたいなことが頻発し、一章書き上がったら一章増えるみたいなことが起きていて、自分たちが普段書いているプログラムも意外と多くの知識の元で作られているんんだなぁというのを実感します。

教材を作るにあたって、本屋や図書館で色々とプログラミングの入門書を眺めているんですが、質の高い本もある一方、びっくりするような(遠回し)構成の入門書が結構多くてなんだかなぁと思うことがあります。160ページとかではじめてif文が出てきたJavaの入門書(初学者向けっぽいタイトルをしている)には流石に驚きました...
全体的な傾向として、入門書の書き方は意外と難解だと感じました。この教材ではできるだけ易しく説明することでも一般的な入門書との差別化を図っていきたいと考えています。

グラニ インターン体験記

インターン体験記

8/15~9/2の間、株式会社グラニにエンジニアとしてインターンに行っていました。
少し(だいぶ)遅れましたが、簡単にどんな感じだったのかまとめておきたいと思います。

(以下の話でおかしな点があった場合、僕の解釈間違いです。念のため。)

ラニ

f:id:tosaka2:20160927050151p:plainラニはモバイル端末向けゲーム開発会社です。
スローガンの一つとして「using CSharp;」を掲げており、C#Visual Studioを主軸において開発を行っています。
.NET 界隈ではMS MVPでUniRxの作者である@neueccさんがCTOを務めていることでも有名だと思います。

インターンの経緯

もともと夏休みはこれといった予定がなく、せっかくなのでアルバイトかインターンをしようかなあと思っていました。
どういった会社にするかは少し迷いましたが、最近開発のモチベーションが落ちてきていて良くないなあと思っていたこともあり、モチベーションを上げるためにも開発業務が行える会社でアルバイトかインターンをしようと決めました。

僕はC#が好きなので、C#をメインで使っており、開発者のレベルが高い会社で本格的な開発現場を体験したいと思いました。 最近ではC#統一を掲げている会社にも幾つか候補がありますが、以前から名前を知っているグラニに一番にお願いすることにしました。

ただ、グラニの公式サイトを探してもインターンとアルバイトの申し込みページが見つからなかったので、neueccさんにDMを送ってお願いすることにしました。 しかし、DMを送る直前になって「公式サイトに無いということは募集してないということなのでは...」「自分程度の技術力で申し込むのは迷惑なのでは...」といった不安にかられ、とても緊張して送信ボタンを押したのを覚えています。女の子に告白するときくらい緊張しました(?)。

実際には募集ページはちゃんと存在していて、僕が見つからなかっただけのようでした。(DMの返信で教えていただきました。「新卒採用」ボタンをクリックした先のページにあったようです。 募集職種一覧) ただ、今までグラニはエンジニアのアルバイトやインターンを受け入れたことが無かったので、社内での「エンジニアのインターン」という存在の知名度も低かったようです。 (あと実は筑波大学にもインターンの募集をかけていたらしいのですが、僕は全く知りませんでした...)

その後応募ページから応募して後日の面接を行い、日付、だいたいの内容、待遇などを相談し、グラニインターンすることが決定しました。

職場の環境

オフィスは六本木ヒルズ 森タワーの15階にあり、ビルの入口付近に設置されているゲートに社員証(画像)をかざして中に入る形でした。
15階が全てグラニのフロアというわけではないので、15階に上がった後またグラニの中に入る際に社員証をかざさないと入場できません。 お手洗いはグラニの外にあるので、社員証の携帯が必須なのですが、一度社員証を机に忘れ、NEW GAME!1話の青葉みたいになるところでした。

PCは3面ディスプレイでメモリ32GBのものが一台貸し与えられました。
椅子も高級そうな感じで、一日そこで作業してても疲れにくかったように感じました。インターンのお給料でまともな椅子を買おうかなと真面目に検討中です。

また、最高だったのがフリードリンクです。(「自由ソフトウェア(free software)」ではなく「ドリンク飲み放題(free drink)」と考えて下さい)(伝わりにくいネタ
レッドブルからヨーグルトジュース、オレンジジュース、コーラ、お茶、ココア、コーヒー、炭酸水、牛乳その他諸々があり最高でした。コーヒとココアに関しては↓みたいな感じの自販機が2種類置いてあって、無料で使えました。(適当にググってきたのでまんまこれではないかも)

さらに、朝ごはんの支給もありました。始業時間30分前(午前10時)から社員の方がトーストを焼いてくれるので、毎日美味しくいただいてました。トーストの他にはコーンフレークやバナナ、ゆで卵等もありました。

バイル端末ゲーム開発業界はブラックなところも多かったりするという話を以前聞いたことがありましたが、グラニは全くそんなことはなく、社員が働きやすい環境を整えることに非常に気を使っているように感じました。
職場環境を整える他にも、(僕はインターン生なので関係ありませんでしたが)福利厚生が充実していて、「オシャレ手当」というので申請すると服代が一定額支給されたり、職場近くに住む場合は家賃手当が出たりするそうです。そのため、六本木ヒルズから徒歩10分~15分くらいの距離に住んでいる方が多くいるようでした。

やったこと

本来ここがメインなような気もしますが、書けないことが多いので短めです。
当然使用言語はC#です。HTML/JS/SQL等も多少いじりはしました。グラニというと最近はUnityという感じもしますが、僕は基本的にASP.NET MVC 5上での開発を行っていました。僕はWeb方面がかなり弱点だなあと思っていたので、いい経験になりました。 また、実装完了後に仕様が変わるという「エンジニアの洗礼」も受けることができ、感動しました。(非常に妥当な変更で、作業量もそれほど多くなかったので負の感情等はないです。念のため。)

開発そのもの以外では、社内で「.NETのクラスライブラリ設計」輪読会が行われており、それに参加させていただきました。5,6人の少人数で対象の本の特定の章を事前に読んでおき、書いてある内容について、主にneueccさんがそれに対するコメントをした後、他の参加者も自分の考えを述べるというような形式でした。
主な目的は「設計思想の共有」でした。あるフレームワーク上でプログラムを書くとき、そのフレームワークの思想に沿ってプログラムを書くことによって、より自然で使いやすい形になります。また、プログラムの設計に関しては様々な思想がありますが、少なくとも同じプロジェクトのチーム内ではその思想が統一されているべきです。 そこで、この会では.NETというフレームワークがどのような思想で設計されているのかに加え、社内フレームワークの思想についても、現状のプロジェクトの失敗と成功の例もあげながら語られていました。
対象の章は大した量ではありませんでしたが、2時間~3時間くらいかけてじっくり行われました。 特に印象に残っているのが、「三種の神器」の話です。(以下の話はまとめたもので、実際はより掘り下げた話がありました。)

  • IntelliSensability インテリセンスを使いやすくする
  • Navigatability(多分違う命名をされてましたが忘れました...) コードナビゲーションを大事に。F12や「参照」などから、定義元に飛びやすくする。
  • Stacktraceability スタックトレースで呼び出し元を探しやすくする

C#はその言語仕様からしてVisualStudioを始めとしたリッチな開発環境での開発しやすさを考えられています。.NET Frameworkに関しても同様です。そのため、上記のようなC#特有のことにも気を配ると、「実際に扱いやすい」プログラムを書くことができます。
上の話も含め、普段適当にネットの記事を見ていてもあまり触れられていない話を多く聞くことができたので、本当に勉強になりました。

他にも、株式会社一休さんとのミーティングに参加させていただいたり、「Team Geek」から、「HRT」の講義をしていただきました。HRTとは、

  • Humility (謙虚)
  • Respect (尊敬)
  • Trust (信頼)

の略です。グラニではこのHRTを常に意識し、コミュニケーションを円滑に行おうという運動が社内全体であるようです。(詳しくは書籍「Team Geek」で)

ちなみに、上で触れている「.NETのクラスライブラリ設計」と「Team Geek」の書籍をインターン最終日にいただきました。圧倒的感謝...!🙏 (ちなみに .NETの本は現在廃盤なので物理書籍の方は結構レアものです。)
(画像)

感想

3週間を通して、本当に勉強になりました。「開発者のレベルが高い会社で本格的な開発現場を体験」という目的も果たすことができました。
ラニの皆様、そして色々と面倒を見てくださったして下さった@xin9leさんへの感謝の気持ちでいっぱいです。本当にありがとうございました。

おまけ お昼ごはん

お昼ごはんはグラニの皆様のご厚意で六本木の様々なところに連れて行っていただきました。せっかくなので紹介したいと思います。

1日目 トリュフハンバーガー
ちなみに一緒に来た他の方はステーキを食べており、「六本木のエンジニアは昼からステーキを食べるのか...」と衝撃を受けました。 (実際は普段ははなまるうどんを食べているそうです) f:id:tosaka2:20160927042744j:plain

2日目 焼肉
社内チャットサービスでC#を動かすことが出来るので、C#で抽選するプログラムを書いた結果焼肉になりました。 f:id:tosaka2:20160927045350j:plain

3日目 寿司
f:id:tosaka2:20160927045354j:plain

4日目 ニョッキ
写真撮り忘れました。

5日目 ササミかつ
ものすごくサクサクで感動しました。 f:id:tosaka2:20160927045356j:plain

6日目 ペヤング ソース焼きそば
台風だったので... 社内コンビニで買いました(会社が半額以上負担してくれる。商品が置いてあってコインを入れて持ってく形式。)

7日目 会社弁当
社内で弁当が販売されています。500円でした。

8日目 ラーメン+親子丼
f:id:tosaka2:20160927045358j:plain

9日目 とんかつ
f:id:tosaka2:20160927045359j:plain

10日目 おうどん+とろたく丼
つるとんたんってお店で変わったうどんがたくさんあります。(自分は比較的普通のうどんをたのみました)。あと容器がすごくでかいです。
f:id:tosaka2:20160927045401j:plain

11日目 ラーメン
普段食べてるラーメンよりだいぶ美味しかったです。
f:id:tosaka2:20160927045403j:plain

12日目 天ぷら
f:id:tosaka2:20160927045405j:plain

13日目 うどん
写真を撮り忘れたので食べログからの借り物です。
これもかなり美味しかったのでまた食べたいです。
f:id:tosaka2:20160927045406j:plain

14日目 ビュッフェ
f:id:tosaka2:20160927045408j:plain

15日目 ピザ
f:id:tosaka2:20160927045410j:plain

美味しいものを食べすぎた副作用か、インターンの期間が終わった後から平気で高いものを食べようとしてハッとなることがあります。怖い怖い...

ちなみに、お昼休みは主にスマブラWiiUで遊んでました。(一度ポーカーにも誘っていただきました。) インターンのときに使ってたもの以外のキャラも多少使えるようになったのでまた勝負したいです。

ICPC予選参加記

ICPC(国際大学対抗プログラミングコンテスト) 2016 国内予選にチームprinding–purantei–として参加し、予選を通過しました。ヤッター!

さて、prinding-purantei-のチーム編成は、僕(1年)、中国人留学生(1年)、先輩(2年)となっていました。
ICPC予選出場経験のある先輩と、中国のJOI(Jじゃないけど)に参加していた留学生という頼りがいのある二人と組むことができ、いいチームで出られたと思います。

予選本番では
A: 僕, B:先輩, C:僕, D:留学生
の問題をそれぞれ通しました。

D問題は留学生がバグらせて少し時間がかかっていたので、僕も実装をしようとしてパソコンを交代してもらったりもした(ICPCでは1チーム1台のPCしか使えません)のですが、最終的に彼のプログラムでACしました。
彼がプログラムをバグらせ続けて通せないという最悪のケースが起こらないように、と考えての行動でしたが、結果論では僕が余計なことをしなければもっと早くACできたわけで、どうするのが正解だったのかなあと思いました。
プログラムを再実装すること以外にも、彼のコードを印刷してバグ探しをしたり、ペアプログラミングをしたりすることもできたので、もしかしたらそちらのほうが良かったのかもしれません。

順位としては 全体49位 学内2位 で予選敗退ラインだったのですが、選抜ルール手順3のワイルドカード枠で予選を通過しました。(順位表

手順3で選ばれるチームはアジア予選のホスト校から選ばれることが多いらしく、 僕が所属するチームは今年のホスト校である筑波大学内の(手順2までの)不通過チームのうち順位が最も高いチームだったため選ばれたのだと思います。筑波大学でよかった~~~
ちなみに、他の手順3での通過チームには、6位の東京大学のチームと48位の神奈川工科大学のチーム、56位の金沢高専のチームが選ばれたようです。

ホスト校枠で通ってしまったので、4完して同じくらいの順位だったのに予選落ちしてしまった他大学の友人のチームには少し申し訳ない気もしますが、彼らの悔しさも背負って(?)10月のアジア地区予選に向けて精進したいと思います。

SuperCon 2016 予選問題をCSPソルバーで解く

SuperCon 2016 参加者の皆さん予選お疲れ様でした。予選通過するといいですね。 僕は高校生で無くなってしまったので本戦への参加権はありませんが、予選問題を読んだところCSPソルバーでさくっと解けそうだったのでやってみました。

※この記事はしっかりとした解説記事ではなく、紹介程度のものです。

CSPソルバーとは

CSPソルバーとは、問題の制約を決まった形式のテキストに変換し、そのファイルをCSPソルバーに渡して上げると、内部で「いい感じ」に問題を解いてくれるというツールです。予選参加者のみなさんは頑張って探索を最適化していったと思いますが、CSPソルバーを使うと簡単なテキストファイルを生成するだけでそれなりに高速に問題を解いてくれます。(とは言ってもみなさんのガチガチにチューニングしたプログラムの方がだいぶ速いと思います。)

CSPソルバーで虫喰い魔方陣を解く

百聞は一見にしかず。CSPソルバーについての詳しい説明は横において、今回の問題を解く様子を見てみましょう。CSPソルバーにはSugarを使います。
とはいっても、魔方陣の解法については自分が書くことはあまりなく、「CSPソルバー 魔方陣」で検索すると

http://bach.istc.kobe-u.ac.jp/sugar/puzzles/sugar-puzzles.pdf

というスライドのPDFが引っ掛かり、このスライドにある3×3魔方陣のCSPファイルと同じように6×6用のCSPファイルを生成するだけで解くことができます。

具体的には以下のようになります。

;それぞれの魔方陣のマスに入る数をx_i_jという変数で表す
(int x_0_0 1 36);整数変数 x_0_0 の宣言。範囲は 1 <= x_0_0 <= 36 となる。
(int x_0_1 1 36)
(int x_0_2 1 36)
(int x_0_3 1 36)
(int x_0_4 1 36)
(int x_0_5 1 36)
(int x_1_0 1 36)
(int x_1_1 1 36)
(int x_1_2 1 36)
(int x_1_3 1 36)
(int x_1_4 1 36)
(int x_1_5 1 36)
(int x_2_0 1 36)
(int x_2_1 1 36)
(int x_2_2 1 36)
(int x_2_3 1 36)
(int x_2_4 1 36)
(int x_2_5 1 36)
(int x_3_0 1 36)
(int x_3_1 1 36)
(int x_3_2 1 36)
(int x_3_3 1 36)
(int x_3_4 1 36)
(int x_3_5 1 36)
(int x_4_0 1 36)
(int x_4_1 1 36)
(int x_4_2 1 36)
(int x_4_3 1 36)
(int x_4_4 1 36)
(int x_4_5 1 36)
(int x_5_0 1 36)
(int x_5_1 1 36)
(int x_5_2 1 36)
(int x_5_3 1 36)
(int x_5_4 1 36)
(int x_5_5 1 36)

; すべての変数は互いに違う数を取る
(alldifferent x_0_0 x_0_1 x_0_2 x_0_3 x_0_4 x_0_5 x_1_0 x_1_1 x_1_2 x_1_3 x_1_4 x_1_5 x_2_0 x_2_1 x_2_2 x_2_3 x_2_4 x_2_5 x_3_0 x_3_1 x_3_2 x_3_3 x_3_4 x_3_5 x_4_0 x_4_1 x_4_2 x_4_3 x_4_4 x_4_5 x_5_0 x_5_1 x_5_2 x_5_3 x_5_4 x_5_5)

;縦、横、対角線のマスに入る数の和が111になる(ポーランド記法で書く)
(= 111 (+ x_0_5 (+ x_0_4 (+ x_0_3 (+ x_0_2 (+ x_0_1 x_0_0))))))
(= 111 (+ x_1_5 (+ x_1_4 (+ x_1_3 (+ x_1_2 (+ x_1_1 x_1_0))))))
(= 111 (+ x_2_5 (+ x_2_4 (+ x_2_3 (+ x_2_2 (+ x_2_1 x_2_0))))))
(= 111 (+ x_3_5 (+ x_3_4 (+ x_3_3 (+ x_3_2 (+ x_3_1 x_3_0))))))
(= 111 (+ x_4_5 (+ x_4_4 (+ x_4_3 (+ x_4_2 (+ x_4_1 x_4_0))))))
(= 111 (+ x_5_5 (+ x_5_4 (+ x_5_3 (+ x_5_2 (+ x_5_1 x_5_0))))))
(= 111 (+ x_5_0 (+ x_4_0 (+ x_3_0 (+ x_2_0 (+ x_1_0 x_0_0))))))
(= 111 (+ x_5_1 (+ x_4_1 (+ x_3_1 (+ x_2_1 (+ x_1_1 x_0_1))))))
(= 111 (+ x_5_2 (+ x_4_2 (+ x_3_2 (+ x_2_2 (+ x_1_2 x_0_2))))))
(= 111 (+ x_5_3 (+ x_4_3 (+ x_3_3 (+ x_2_3 (+ x_1_3 x_0_3))))))
(= 111 (+ x_5_4 (+ x_4_4 (+ x_3_4 (+ x_2_4 (+ x_1_4 x_0_4))))))
(= 111 (+ x_5_5 (+ x_4_5 (+ x_3_5 (+ x_2_5 (+ x_1_5 x_0_5))))))
(= 111 (+ x_5_5 (+ x_4_4 (+ x_3_3 (+ x_2_2 (+ x_1_1 x_0_0))))))
(= 111 (+ x_5_0 (+ x_4_1 (+ x_3_2 (+ x_2_3 (+ x_1_4 x_0_5))))))

ただし、このCSPファイルはすべての魔方陣のマスが開いている状態の制約を表しているので、既に埋まっている場所は制約として追記して上げる必要があります。 例えば次の魔方陣の場合、

18 13 35
20 33 19 7
2 32 10 9
30 3 15
29 4 26 28
5 31 16

以下の様に制約を追記します。

(= x_0_1 18)
(= x_0_3 13)
(= x_0_4 35)
(= x_1_1 20)
(= x_1_2 33)
(= x_1_3 19)
(= x_1_4 7)
(= x_2_1 2)
(= x_2_2 32)
(= x_2_4 10)
(= x_2_5 9)
(= x_3_0 30)
(= x_3_3 3)
(= x_3_5 15)
(= x_4_1 29)
(= x_4_2 4)
(= x_4_4 26)
(= x_4_5 28)
(= x_5_2 5)
(= x_5_3 31)
(= x_5_4 16)

あとはこのファイルを適当な名前(ここではmahou.cspとします)で保存し、sugarに渡すだけです。

% sugar mahou.csp
s SATISFIABLE
a x_0_0 6
a x_0_1 18
a x_0_2 25
a x_0_3 13
a x_0_4 35
a x_0_5 14
a x_1_0 11
a x_1_1 20
a x_1_2 33
a x_1_3 19
a x_1_4 7
a x_1_5 21
a x_2_0 36
a x_2_1 2
a x_2_2 32
a x_2_3 22
a x_2_4 10
a x_2_5 9
a x_3_0 30
a x_3_1 34
a x_3_2 12
a x_3_3 3
a x_3_4 17
a x_3_5 15
a x_4_0 1
a x_4_1 29
a x_4_2 4
a x_4_3 23
a x_4_4 26
a x_4_5 28
a x_5_0 27
a x_5_1 8
a x_5_2 5
a x_5_3 31
a x_5_4 16
a x_5_5 24
a

この通りに埋めると

6 18 25 13 35 14
11 20 33 19 7 21
36 2 32 22 10 9
30 34 12 3 17 15
1 29 4 23 26 28
27 8 5 31 16 24

となり、確かに解けていることが分かります。(すごい!)

実行時間をtimeコマンドで計測すると

real 0.94
user 0.46
sys 0.47

となりました。まぁまぁですかね。実行環境はVirtualBox上のUbuntu(メモリ1GB、CPU Core i7-6650U 2.20GHz)、内部で使用しているSATソルバーはMinisatです。
最悪ケースでどうなるかは自分も確かめてないので試してみてください。

このように、CSPソルバーを使うと問題の解が簡単に得られます。もちろん魔方陣以外にも様々な問題を解くことができます。
SuperConのような単一のソースファイルを提出するコンテストではこれをそのまま回答コードとして流用するのは難しいですが、覚えておくとテストケース生成の際などに役立つかもしれません。

参考

ひとりごと

本当は魔方陣のルールをdirect encodingとorder encodingで表すプログラムをそれぞれ書いて比較するっていうテーマにして、Sugarはついでで紹介するだけみたいなブログ記事にする予定だったけど、ちょっと時間が取れ無さそうだったのでとりあえずSugarの紹介だけすることにしました...
あと本当はWindows上でSugarを動作させたかったけど、うまく行かなかったので後回し中。でも大体原因がわかった(と思う)ので、もしできたらそれについてのブログも書くかも...?
SuperCon、現役としてもう一回やりたかったなあ。

SRM 677 Div1 Easy DoubleOrOneEasy

https://community.topcoder.com/stat?c=problem_statement&pm=14101&rd=16627

問題概要

整数a, b, newA, newBが与えられる。 (a, b)に対しそれぞれ同時に+1または*2する操作を繰り返して(newA, newB)に変える時の、操作の最少回数を求める。(変えられないなら-1)

ゆるふわな解法

+1を2回することは*2を1回することと等しいので、一番最初に*2をする前以外で+1を2回以上するのは無駄だよね。 という話から、最初に+1する回数をx、*2をする回数をnとすると、操作は(a * 2^n) + (x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)みたいな式で表せることがわかる。
(x * 2^n) + (1or0 * 2^(n-1)) + ... + (1or0 * 2^1) + (1or0 * 2^0)をkとおくと、a * 2^n + k == newA && b * 2^n + k == newBとなる時のnが答えの操作で*2する回数になる。 このnはたかだかlog(newA)<30程度なので1から順に試せばOK。
ちなみに(1or0 * 2^(n-1))以降の1or0の並びはnewA - (a * 2^n) + (x * 2^n)を2進数で表した時と等しくなるので、この部分で+1した回数はpopcountで求められて嬉しい。
計算量O(log(newA))

コード

INT_MAXのところを始めINF(= 1 << 29)にしていて落ちたりした。不注意...
そもそもa==bの時以外はremA==remBになったらすぐreturnしてもいいんだけどね。

#include "bits/stdc++.h"
using namespace std;

const int INF = 1 << 29;

//VSでコーディングしてるので拝借してきました http://www.nminoru.jp/~nminoru/programming/bitcount.html
int popcount(int bits)
{
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}

class DoubleOrOneEasy
{
public:
    int minimalSteps(int a, int b, int newA, int newB)
    {
        int kake = 1;
        int ksum = 0;
        int ans = INT_MAX;
        while (a * kake <= newA && b * kake <= newB)
        {
            int remA = newA - a * kake;
            int remB = newB - b * kake;
            if (remA == remB)
            {
                int tmp = ksum + remA / kake + popcount(remA % kake);
                ans = min(ans, tmp);
            }

            kake *= 2;
            ksum++;
        }

        return ans == INT_MAX ? -1 : ans;
    }
};

解いた問題をブログに上げるというのを初めてやってみたところ、意外と書くのが面倒で解説はもはや分からせる気も厳密に書く気もない感じになってしまった。
この問題はなんとなく競プロしようと思って最近の問題から適当に選んだけど、久しぶりに(自分にとって)やるだけじゃない問題を解いた気がする。
SRM Div1の問題を提出したのは初めてかもしれない。TopCoderCodeforcesは今までほとんどやって来なかったのでどんどんやっていきたいなあ。

(操作ミスで記事を消してしまったため再投稿です)