akmhmgc · akmhmgc · Oct 3, 2025 · tokuhirat · Oct 4, 2025 · akmhmgc
diff --git a/779/step1.md b/779/step1.md
@@ -0,0 +1,29 @@
+# step1 何も見ずに解く
+簡単な例を書いていくと、n行目のk番目の値はn - 1行目の(k + 1) / 2の値によってわかると気づく。
+kは半分ずつ減るので時間計算量はO(logk)となる。kの最大値は2^(30 - 1)なので1秒以内に間に合う。
+stackの深さは最大でも30なのでstack overflowは起きない。
+空間計算量はO(n)
+
+```ruby
+# @param {Integer} n
+# @param {Integer} k
+# @return {Integer}
+def kth_grammar(n, k)
+    return -1 if n <= 0 || k <= 0 || k > 2 ** (n - 1) # 不正な値は-1を返す
+    return 0 if n == 1 && k == 1
+
+    if kth_grammar(n - 1, (k + 1) / 2).zero?
+        if k.even?
+            1
+        else
+            0
+        end
+    else
+        if k.even?
+            0
+        else
+            1
+        end
+    end
+end
+```
diff --git a/779/step2.md b/779/step2.md
@@ -0,0 +1,40 @@
+# step2 他の方の解答を見る
+## より簡潔に書く
+https://github.com/tokuhirat/LeetCode/pull/46/
+0 -> 01
+1 -> 10
+と子が作られるとすると、左の子であれば親から反転しないし、右側の子であれば反転することを利用する。
+
+```ruby
+# @param {Integer} n
+# @param {Integer} k
+# @return {Integer}
+def kth_grammar(n, k)
+    return -1 if n <= 0 || k <= 0 || k > 2 ** (n - 1) # 不正な値は-1を返す
+    return 0 if n == 1 && k == 1
+
+    result = kth_grammar(n - 1, (k + 1) / 2)
+    result^= 1 if k.even?
+    result
+end
+```
+
+## 再帰を使わずにループで書く
+rootに辿りつくまでに何回反転したかを考える
+
+```ruby
+# @param {Integer} n
+# @param {Integer} k
+# @return {Integer}
+def kth_grammar(n, k)
+    return -1 if n <= 0 || k <= 0 || k > 2 ** (n - 1) # 不正な値は-1を返す
+
+    flips = 0
+    col = k
+    while col > 1
+      flips^= 1 if col.even?
+      col = (col + 1) >> 1
+    end
+    flips
+end
+```
diff --git a/779/step3.md b/779/step3.md
@@ -0,0 +1,18 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {Integer} n
+# @param {Integer} k
+# @return {Integer}
+def kth_grammar(n, k)
+    return -1 if n < 1 || k < 1 || k > 2 ** (n - 1) # 不正な値
+
+    flips = 0
+    col = k
+    while col > 1
+        flips^= 1 if k.even?
+        col = (col + 1) >> 1
+    end
+    flips
+end
+```
diff --git a/779/step4.md b/779/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正