From 807d91879f2ae138058a9d90b7a1b779427def03 Mon Sep 17 00:00:00 2001
From: akmhmgc <akimuhamaguchi@icloud.com>
Date: Fri, 3 Oct 2025 22:35:52 +0900
Subject: [PATCH] 779

---
 779/step1.md | 29 +++++++++++++++++++++++++++++
 779/step2.md | 40 ++++++++++++++++++++++++++++++++++++++++
 779/step3.md | 18 ++++++++++++++++++
 779/step4.md |  1 +
 4 files changed, 88 insertions(+)
 create mode 100644 779/step1.md
 create mode 100644 779/step2.md
 create mode 100644 779/step3.md
 create mode 100644 779/step4.md

diff --git a/779/step1.md b/779/step1.md
new file mode 100644
index 0000000..4a29ac1
--- /dev/null
+++ 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
new file mode 100644
index 0000000..dc78467
--- /dev/null
+++ 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
new file mode 100644
index 0000000..cd4bdf1
--- /dev/null
+++ 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
new file mode 100644
index 0000000..5941ee1
--- /dev/null
+++ b/779/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正