説明会つらい履歴書つらいエントリーシートつらいグループディスカッションつらい集団面接つらい個人面接つらいつらいつらいつらいつらいつらいいいいいいいいいいいいいいい
(´・ω・`)
「バイナリ・カウント」とは
「バイナリ・カウント」はリクルートキャリア社が運営する「CodeIQ」の企画です。
「CodeIQ」は「コード転職サイト」、すなわち「出題された問題に対し解答コードを提出→その内容によって企業からのオファーが来る」というシステムなのですが、たまに転職とは関係のない「問題」が掲載されることがあり、「バイナリ・カウント」もそのひとつとなっています。
では内容はというと……詳しいことは避けておきます。一応会員制サイトなので。知りたい方は是非登録を!(ステマ)
あと同じ出題者さまによる問題について、以前記事化しています。参考のほどに。
提出コード
使用言語はRuby。1回目の提出で合格。ideoneでの実行時間は0.02秒でした(そのはず)。
提出コード解説(?)&小反省会
本問を解答するにあたってはいろいろ考えたので、その軌跡を(おもに自分用として)ブログに残しておきたいのですが――正直書く元気がありません。
理由は明確。就活です。16年卒の新卒採用活動がちょうどピークに入っており、体力がそっちに持っていかれています。特にメンタル面の疲弊がひどく、ブログはおろか日常生活にすら差し支える始末。つらい(´・ω・`)
というわけで今日は簡単に済ませておきたいと思います。ごめんね(´・ω・`)
どのように考えたか
本問は0からnまでの数字を2進数で表現したときにあらわれる1の総和を求めるものです。「0からnまでの整数を2進数にする→それぞれに含まれる1の数を数える→それを足し合わせる」という単純な解き方では、nが大きくなると当然破たんしますので、何かしらの「規則性」を見つける必要があらわれます。
ではその「規則性」というと……正直なところ、提出コードに書いた以上の説明ですべてです。 というかこれ以上に丁寧かつ上手に説明する文章力も気力もないという(´・ω・`)
とはいえわかりづらそうなところだけ簡単に解説をしておくと――
まず4行目の「1と0は同じだけ含まれている」。例えば(000..111)を考えてみます。
10進数 | 2進数 |
---|---|
0 | 000 |
1 | 001 |
2 | 010 |
3 | 011 |
4 | 100 |
5 | 101 |
6 | 110 |
7 | 111 |
上の表より(000...111)に含まれる1と0の数は同じであることがわかります。この性質を利用すれば(000..111,1000)に含まれる1の総和も簡単に求めることができ、提出コードではその関数をg(4)としているわけです。
次に9-11行目。たとえば9行目の「1000000..1001000 => 100[000..100] => 1 * ? + g(3)」を表にしてみます。
10進数 | 2進数 | 上3けた | 下3けた |
---|---|---|---|
64 | 1000000 | 100 | 000 |
65 | 1000001 | 100 | 001 |
66 | 1000010 | 100 | 010 |
67 | 1000011 | 100 | 011 |
68 | 1000100 | 100 | 100 |
「上nけたは固定、下mけたは規則的に変動」という状況を無理やり作り出し、それを利用してその範囲に含まれる1の総数を求めていきます。(1000000..1001000)の場合、上3けたにあらわれる1の総数は「1 * 5」、下3けたに関しては(00..11,100)に含まれる1の総和だから「g(3)」で求めることができます。
解説はこんなものかしら……というよりこんなもので勘弁してください。精神力の限界です(´・ω・`)
小反省会
問題が公開されてすぐ解答コードを提出したので、多分2-3週間は経過しているはず。その視点から自分のコードを見返してみると――
- コードが「美しくない」。「書き捨て」感がある。
- コメントアウトをもう少し残すべき。内容をさっぱり忘れたころに読んだ場合、この量では自分のコードを解読できない可能性がある。
- 「規則性」はもうちょっと工夫すべきだったかも……? どうやら再帰などが利用できたらしく、もっと簡潔なコードもできたはず。
反省点はこれぐらいかしら――って、ほとんど致命的な問題ばかりじゃないですかやだー。
やはり「他人に見せる」あるいは「何もかも忘れたあとの自分に見せる」という視点は大事ですね。精神的に疲労困憊の状態でコードを見て、改めて実感しました。