ブログのとさか

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の問題を提出したのは初めてかもしれない。TopCoderとCodeforcesは今までほとんどやって来なかったのでどんどんやっていきたいなあ。

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

この記事について

中高生プログラマ Advent Calendar 2015 6日目です。
どうも皆さん。とさか2です。高校3年生をやっています。
「中高生プログラマ」という肩書の中では一応年長者（このアドベントカレンダーでは高専4,5年生の方も参加していますが）なので、今までの経験から、まだまだ中高生をやっていられる優秀で有望な皆さんに向けて伝えたい的な記事です。あまり技術的な話はしません。

自己紹介

この企画は学生間の交流を兼ねてるらしいので、自己紹介をします。
一番得意な言語はC#です。開発と競技プログラミングをしてます。コンピュータ部の部長を務めていたりもしました。CTFはあまりやってませんが、scryptosで準メンバー的に何回か参加してました。
他の分野だとゲームAI・機械学習・ヒューリスティックアルゴリズムの勉強をしたりコード書いたりしています。
CombGigでは一応運営側として参加してたので、そこで会ったことがある人もいるかもしれません。
twitterは@nanTosaka2です。( ~~諸事情あって鍵がかかっています。もう少ししたら外すかも。~~ 鍵外しました)

本題

皆さん御存知の通り、一口に「プログラミング」と言っても様々な用途があります。
それに伴い、プログラマのコミュニティも用途ごとに形成されています。特に最も人口が多い「ソフトウェア開発」に関しては、使用言語やフレームワークなどでそれなりに強くコミュニティが分断されています。
それ以外の要素として、所属組織や住んでいる地域によって分けられることを考えると、各々が所属するコミュニティは必然的に小さくなります。

さらに、開発コミュニティは平均年齢が高く、中高生が同世代と同じコミュニティで出会うというのはなかなか難しいように感じます。
結果として、同世代の中で自分が一番優秀なのではないかという気がしてくるのがよくあるパターンです。
それはそれで幸せな生き方だとは思います。しかし、技術力を上げるという観点から見ても、「自分が一番優秀だ」というのが思い込みだった場合、早めにそれに気付いた方が良いでしょう。
勘違いをしていなくても、優秀な同世代の仲間がいたほうがモチベーションが上がると思います。さらに言えば、将来的に有用な人脈になるかもしれません。

というわけで、ここでは優秀な同世代の仲間と出会う方法について書いていきたいと思います。

1.twitter

すべてはtwitterのアカウント作成から始まります。以下で紹介する方法で出会った人と繋がりを保つにはtwitterが一番です。また、ある程度繋がりが広くなってくるとtwitterを通じて新しく知り合うことも出てきます。アカウントを持っていない人は絶対に作りましょう。

2.セキュリティ・キャンプ

セキュリティ・キャンプは、合宿形式の情報セキュリティ技術に関する勉強会です。
大学生以下対象なので、一度に大量の同世代の人々と出会うことが出来ます。参加者は、セキュリティに詳しくない人でも、別のコンピュータ技術分野には精通している人であることが多いので、そのつもりで交流すると良いでしょう。
参加のためには選考を通る必要がありますが、それさえ通れば交通費含め全額無料で参加できるので最高です。夏に一度ある全国大会以外にも、地方大会が行われているそうなので、地方の方はまずそちらに参加してみてもいいでしょう。

3.競技プログラミングの大会への参加

競技プログラミングは、「アルゴリズム」の設計と実装の能力を競うプログラミングを使った「競技」です。与えられた問題を解くプログラムを作成し、提出すると機械的に採点され、それの結果に応じて順位が付きます。
プログラミングコンテストと呼ばれることもありますが、アプリケーションを作成して提出するもの（U22プログラミングコンテストなど）とは全くの別物です。
順位がつくので強さがはっきりと分かります。初めたばかりの頃は上位陣の圧倒的な実力に驚かされるでしょう。

一応書いておくと、これはソフトウェア開発とは非常に異なるものなので、プログラマだからといって競技プログラミングが出来なければいけないわけでは決してありません。
しかし、プログラミングと深い関わりを持ちながらも、開発ではあまり触れることのない「アルゴリズム」を身をもって体験できるので、一度くらい取り組んで見るのが良いと思います。練習を重ねると実装速度が上がるので、開発にも役立ちます。あと単純に面白いです。

中高生向けの大会では以下の三つが有名です。以下の全ての大会では競技時間とは別に懇親会等の時間が設けられているので、勝ち上がったら存分に交流することが出来ます。
1. 日本情報オリンピック
2. パソコン甲子園プログラミング部門
3. SuperCon

日本情報オリンピックは予選で勝ち上がると関東にある会場に集められ本戦を行い、そこで20位以内に入ると代表選考合宿に参加できます。さらにそこで3位以内になると、日本代表として、海外で行われる国際情報オリンピックに参加できます。ここでかかる交通費や宿泊費等は全て無料です。最高。
パソコン甲子園の本戦は会津大学で行われます。勝つとガッツリ賞金をもらえます。
SuperConの本戦は大阪大学と東京工業大学で行われます。この本戦は独特で、スーパーコンピュータ上で行います。スパコンプログラミングは通常のプログラミングと異なる部分が結構多いので、結構面白いです。
ちなみに、以上の三つで結果を残せば大学受験で有利になったりもします。参加しない手はないな！

中高生向けの大会以外でも、様々なコンテストが開催されています。国内だとAtCoderが有名です。社長は@chokudaiさんです。
基本オンラインですし、参加費も無料なので気軽に参加してみましょう。

「競技プログラミングをしている」というだけで結構簡単に繋がりが広げられると思うので、おすすめです。

4.JOI夏季セミナー

夏期セミナーは先述の情報オリンピックを開催している団体が開いている合宿です。書類選考はありますが、競技プログラミングが出来なくても参加できます。
情報科学に関連する本を読んで演習（実装）したり講義を聞いたりします。これは参加者も扱う内容もレベルが高いです。
僕は日程が合わず一度も参加できなかったのでものすごく後悔しています。皆さんは後悔の無いようぜひ参加してください。

5.中高生向け勉強会

中高生向けの勉強会に参加するか、皆さんの手で開催してください。様々な人と交流できます。
CombConfやCombGig・Comb Meetup等の前例があります。
開催のノウハウは@mt_caretに相談すれば喜んで教えてくれると思います。お気軽にどうぞ。
僕はもう中高生では無くなりますが、次の開催者が現れることを期待しています。

以上です。
これらのイベントに参加する際は、名刺を用意しておくのが一般的なので、作っておきましょう。twitterのハンドルを書くのを忘れずに！