カタツムリ匹

プログラマー-カタツムリ

問題の説明

パラメータは整数nです.下図に示すように、長さと高さnの三角形では、上部頂点から反時計回りにカタツムリ充填を行い、solution関数を完了し、最初の行から最後の行まで順番にマージされた新しい配列を返します.

せいげんじょうけん

nは1000より大きい.

I/O例

nresult4[1,2,9,3,10,8,4,5,6,7]5[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]6[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

に近づく

まず、私はこの問題に失敗しました.私が思うようにアルゴリズムを実現することもできず、一日を超えたので、最終的には他の人の解答を借りてこの問題を解決したいと思っています.
それでも、私が近づく方法を記録することが重要だと思います.方法を説明するために、n=4を基準として説明する.

1からnまで、インデックスの増幅は1です.
1 -> 0
2 -> 1
3 -> 3
4 -> 6
1つの法則は、数字が1増加するたびに、全インデックスの増加幅も1増加することです.

nに保存すると、n-1に連続して保存されます.
nに保存すると底辺になるので、連続して数字を保存できます.上記の場合は4に保存するので、5、6、7はインデックス7、8、9に連続して格納することができる.

インデックス2-n,-(n-1),...インデックスを順番に減らす
まず、すでに底辺が作られている場合は、2まで逆さまに保存すべきであり、このときインデックスの減少幅は-n、-(n-1)、-(n-2)...順次減少が確認できます.
7 -> 9
8 -> 5
9 -> 2

しかし、ここでの問題は、今回のプロセスで終了しない場合には、再循環が必要な場合に、1回のプロセスが何回行われるかを特定できないことである.n=4の場合は1回のみ行い,nが5または6の場合は2回行うが,これをどのように実現すればよいか分からない.

他人の解答

まず,この問題を一次元配列で解決しようとするのは誤った方法かもしれないと思う.底辺と高さがあるので、2 D配列を考えるともっと自然です.
これを2 D配列と見なしてインデックスを計算すると、次のルールが得られます.

01                        [0][0]
02  09             ->     [1][0]  [1][1]
03  10  08                [2][0]  [2][1]  [2][2]
04  05  06  07            [3][0]  [3][1]  [3][2]  [3][3]

,このとき,1~nの間ではx値(行)のみが1増加する.

の底辺の場合、y値(列)だけが1増加します.

以降、対角線が充填されると、x値とy値の両方が−1減少することがわかる.

問題は、いつどのプロセスを回転すべきかを決定する基準を見つけることです.このとき,問題で提案した3つの三角形を見ると,上記の3つの操作のうちの1つがnの値に従って行われていることがわかる.
では、range(n)の値で各プロセスを区別できるはずですが、3つのプロセスがあるので、残りの3つの値を利用することができます.

def solution(n):
    answer = []
    arr = [[0 for _ in range(i)] for i in range(1, n + 1)]
    num = 1
    x = -1
    y = 0

    for i in range(n):
        for j in range(n - i):
            if not i % 3:
                x += 1
                arr[x][y] = num
                num += 1
            elif i % 3 == 1:
                y += 1
                arr[x][y] = num
                num += 1
            else:
                x -= 1
                y -= 1
                arr[x][y] = num
                num += 1

    return answer

そこで、前述した論理を以下のように実現します.質問では1次元配列を返し、答えを1次元配列に変換すればよい.

    for row in arr:
        for x in row:
            answer.append(x)

次の方法で1次元配列を作成しました.しかし、他人の解答を見てみると、次のような方法があります.

return list(itertools.chain(*tri_snail))