[名刺バインダー管理] 初投稿でpaiza×Qiitaキャンペーンに便乗してみた。[Bレベル問題]

初めまして。
閲覧ありがとうございます、きぃす(Keith)です。
今回はpaiza×Qiita記事投稿キャンペーン「プログラミング問題をやってみて書いたコードを投稿しよう！」に便乗して、Qiitaの海に初ダイブしてみた、な投稿です。
自己紹介と、Bランク問題を解いてみたの流れで書いてみましたので、よかったら見ていってください。
「こんな書き方もあるよ」等コメントも、どしどしお待ちしております。

1回目のコードでは満点が出ませんでした。
修正版も載せていますので、参考にされる方は最後までお読みください。

自己紹介

外部受験して、今は情報系を専攻している院生。素敵な同期に負けないように何か極めていきたいお年頃。就活ってなぁに。

使ってる言語：Python, C++, 日本語, 英語.
paizaレベル：Bランク（Bが解けるとは言っていない）
趣味：アニメ鑑賞, カラオケ, 声優.
挑戦中なこと：思いついたものをプログラムで実装したい。 \ｾｲｶﾌﾞﾂ!seikabutu!/
最近Flask勉強中。（別記事にするかも）

GeeksforGeeksをよく使っていたのでQiitaは初心者です。

paizaキャンペーンについて

paiza: (基本)無料でプログラミング学習からレベルチェックまでできるプラットフォーム。就活・転職にも活用できるみたいだぞ。

対象のプログラミング問題を解いて関連記事を投稿すると、抽選で何かしら当たるらしい。詳しくは上のリンク先をどぞ。

問題、解いてみた。

今回はBランク相当の問題：「名刺バインダー管理」を解いてみます。試行錯誤で解いているので、頑張って整理して記事にしてみます。

問題内容

入出力のルール

入力：n m
出力: m番目の名刺の裏側の番号
条件: 1 ≦ n, m ≦ 100,000
ここで、nはファイル1枚に付属するポケットの数で、mはポケットの番号を示す。

アイデア出し

1. 一度ファイルの端に行くと折り返す動きは、再帰に似てるなぁ。

2. 図をよく見てみると、各ファイル(以下、階層と呼ぶ)の中で、1ポケット毎の数値の合計は一定だと気付く。（n=3のとき、1+6 = 2+5 = 3+4 = 7）

3. とりあえず、nを変えた時の値を以下の様に描きだしてみる。（図ではn=3の時のみ描画）
   

4. ここで見つけた関係を、自分なりに式にしてみる：

ポケット数を n_i={n₁, n₂,...,n_k}; 1 ≦ k ≦ 100,000.

バインダーのファイル数(階層) L_i ∈ℕ(自然数; {1,2,...}).

t_i,Lはn_iの時のL階層目のとあるポケットの両面の番号を足した数（以下、トータルと呼ぶ）.

とすると、
t_i,1 = 2n_i+1；1階層目のトータルは、ポケット数の2倍に1を加えたものに等しい。
t_{i, L+1} = t_{i, 1}+ (L-1) * 4n_i；同ポケット数の時の、1階層下のファイルのトータル

また、出力＝(m番目を含む階層のトータル) - m.

コードに書き起こす

#include <iostream>
using namespace std;
int main(void){
    // Variables
    int n, m=0;
    cin >> n >> m;

それぞれの入力をint型変数に記録。

    // Find which layer has m-th pocket.
    // There are 2*n slots in 1 layer.
    int layer=0;
    layer = 1 + (m / 2*n);
    int t=0; //total num of indexes at one slot
    if(layer == 1){
        t = 2*n + 1;
    }else{
        t = (2*n + 1) + (layer-1)*(4*n);
    }

①m番目のポケットを含む階層を探す
②上で求めた階層のトータルを計算

    cout << t - m << endl;
    return 0;

結果を表示。

採点結果１

.......
うん、なんで？

実は上記のコードには些細なミス1点と大事な考え方1点が抜けていました。
以下で解説と修正を行います。

修正してみる

さて、今回のミスの原因はどこにあったでしょうか。答えから言うと、階層の計算に漏れがあったようです。
以下、再掲：

layer = 1 + (m / 2*n);

エラー１：(m / 2n)が適切に計算されない場合がある。
解決策：(m / (2n))の様に計算順序を明確化した。
エラー２：1ベース（人ベース）で計算しているため、漏れが生まれる可能性がある。
解決策：((m-1) / (2*n))にすることで、0ベース(0-based indexing)に変換した。

修正後：

layer = 1 + ((m-1) / (2*n));//0ベースに変更

採点結果２

やったぜ。全ケース問題なくパスしました。

考察・メモ

1. 裏表の位置を明確にする必要がないため、単純な計算で解くことができた。
2. 四則計算を記述する際は、計算順序を明確に表す意識が大切。（ここ見落としガチ）
3. 0ベースに従うマインドセット
4. 実用的な面では、ファイルの表と裏まで判定するコードがあると格好良かったかも。
5. 文章書くの割と楽しいな。

深堀：なんで0ベースがいいの？

文献１: Why numbering should start at zero
簡単にまとめると、数学的に
1. 下限を≤で、上限は<で表現する方が美しい。
例：7 ≤ k < 13
2. 列の長さの表記として分かりやすい。
例：1 ≤ i < N+1 → 0 ≤ i < N

一般論でいえば、文献1のような理由と、多くのプログラミング言語（C++含む）のインデックスが0から数えることがあげられている。

しかしながら、今回のような整数の割り算については、特に 境界条件(boundary conditions) を正しく扱うには必要な考え方みたいだ。

例えば、1ベースならそのまま代入して
(k = 3), (k/3 + 1) → (1 + 1 = 2).
(k = 4), (k/3 + 1) → (1.333 + 1 ≈ 2).
しかし0ベースに変換してから計算すると
(k = 3), ((3-1)/3 + 1) → (2/3 + 1 = 1).
(k = 4), ((4-1)/3 + 1) → (3/3 + 1 = 2).

境界のどちらに含まれるべきかが、0ベースに変換することで表現される。
どちらにせよ、プログラミングを扱う上で、0ベースを軸に考える癖は今後トクが多そう。

おわり

ここまでお読みいただきありがとうございます。
文字書きもコードもつたないところがありますが、これから少しずつ、投稿していきたいと思います。
（どうやらメモ代わりにされている方も散見されるので、パク.. リスペクトしてもいいかもなと考えてます。）