Posts

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 一方通行（グラフ上の移動） | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 まずは以下のように実装しました。 package main import "fmt" func main(){ var n int fmt.Scan(&n) g := make([][]int, n) for i := 0; i < n; i++ { g[i] = make([]int, n) } for i := 1; i < n; i++ { var a, b int fmt.Scan(&a, &b) g[a - 1][b - 1] = i g[b - 1][a - 1] = i } fmt.Println(1) for i := 0; i < n; i++ { for j := 0; j < n; j++ { if g[i][j] == i + 1 { fmt.Println(j + 1) break } } } } ですがこれだと入力例１は解けてもそれ以外が解けません。 ということで少し改修しました。 package main import "fmt" func main(){ var n int fmt.Scan(&n) g := make([][]int, n) for i := 0; i < n; i++ { g[i] = make([]int, n) } for i := 1; i < n; i++ { var a, b int fmt.Scan(&a, &b) g[a - 1][b - 1] = i g[b - 1][a - 1] = i } fmt.Println(1) i := 0 cnt := 1 for { for j := 0; j < n; j++ { if g[i][j] == cnt { fmt.Println(j + 1) i = j cnt++ break } } if cnt == n { break } } } 問題は解けるようになったはずですが、タイムオーバーになってしまいました。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 重みあり有向グラフの隣接行列と隣接リスト | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 前回の実装を少し変えてあげれば実装できます。 具体的には今まで重みとして1を与えていた部分をkに変えてあげればいいです。 package main import "fmt" func main(){ var n, m int fmt.Scan(&n, &m) g := make([][]int, n) for i := 0; i < n; i++ { g[i] = make([]int, n) } for i := 0; i < m; i++ { var a, b, k int fmt.Scan(&a, &b, &k) g[a - 1][b - 1] = k // 前回まで必ず1を入れていた箇所を、入力されたkにしてあげる } for i := 0; i < n; i++ { for j := 0; j < n; j++ { fmt.Printf("%d", g[i][j]) } fmt.Println() } for i := 0; i < n; i++ { for j := 0; j < n; j++ { if g[i][j] > 0 { fmt.Printf("%d(%d)", j, g[i][j]) } } fmt.Println() } } これで実装できました。 重み付き有向グラフみたいな難しそうな言葉に惑わされそうになりますが、理解してしまえば簡単ですね。 では今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 有向グラフの隣接行列と隣接リスト | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 これも一瞬よくわからなかったので、AIと少し壁打ちしました。 これまでは双方に関係性があることが前提でしたが、これが片方のみになるということですね。 例として、以下のような方向の場合 1 → 2 1 → 3 4 → 2 4 → 5 5 → 3 以下のような表になります。 実装としては以下のようになります。 package main import "fmt" func main(){ var n, m int fmt.Scan(&n, &m) g := make([][]int, n) for i := 0; i < n; i++ { g[i] = make([]int, n) } for i := 0; i < m; i++ { var a, b int fmt.Scan(&a, &b) g[a - 1][b - 1] = 1 // 前回からここの部分が変わっただけ } for i := 0; i < n; i++ { for j := 0; j < n; j++ { fmt.Printf("%d", g[i][j]) } fmt.Println() } for i := 0; i < n; i++ { for j := 0; j < n; j++ { if g[i][j] == 1 { fmt.Printf("%d", j) } } fmt.Println() } } 前回から変わった部分はコメントの部分だけです。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 隣接リスト | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 問題文を読んでも、何を出力すればよいのかいまいちよく分かりませんでした。 そこでこれもAIと壁打ちしました。 問題の例の図の場合は以下のように出力すればよいです。 図1（五角形のような形）を「隣接リスト」にすると、こんな感じのメモ帳セットになります。 ※コンピュータの世界なので、番号を「-1」して 0番から数えるルールで書きますね。 0番（頂点1）のリスト: [1, 2] （2番と3番とつながっている） 1番（頂点2）のリスト: [0, 3] （1番と4番とつながっている） 2番（頂点3）のリスト: [0, 4] （1番と5番とつながっている） 3番（頂点4）のリスト: [1, 4] （2番と5番とつながっている） 4番（頂点5）のリスト: [2, 3] （3番と4番とつながっている） ということで以下のように実装しました。 前回とあまり変わらないですね。 package main import "fmt" func main(){ var n, m int fmt.Scan(&n, &m) g := make([][]int, n) for i := 0; i < n; i++ { g[i] = make([]int, n) } for i := 0; i < m; i++ { var a, b int fmt.Scan(&a, &b) g[a - 1][b - 1] = 1 g[b - 1][a - 1] = 1 } for i := 0; i < n; i++ { for j := 0; j < n; j++ { if g[i][j] == 1 { fmt.Printf("%d", j) } } fmt.Println() } } ということで実装できました。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 隣接行列 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 隣接行列というものがなんなのか、いまいち理解できなかったのでAIと壁打ちしました。 結果として得られた回答を要約すると以下の通りです。 「隣接行列」はただのチェック表 「頂点iと頂点jがつながっているか？」を、表の i行目 とj列目 が交差する場所に書き込みます。 つながっている！ → 1 を書く つながっていない… → 0 を書く 5つの頂点がある図（1枚目の五角形のような図）で表を作ってみましょう。 つながっているペア（辺）の一覧： 1と2 1と3 2と4 3と5 4と5 これをもとに、5×5の表を埋めるとこうなります。 …ということで、なんとなくイメージがつかめてきました。 実装してみます。 package main import "fmt" func main(){ var n, m int fmt.Scan(&n, &m) g := make([][]int, n) for i := 0; i < n; i++ { g[i] = make([]int, n) } for i := 0; i < m; i++ { var a, b int fmt.Scan(&a, &b) g[a - 1][b - 1] = 1 g[b - 1][a - 1] = 1 } for i := 0; i < n; i++ { for j := 0; j < n; j++ { fmt.Printf("%d", g[i][j]) } fmt.Println() } } これで実装できました。 ...

こんにちは、ナナオです。 前回の記事で、キーボード上でマウスジェスチャを扱えるようにしました。 今回はそれを発展させて、BT接続先（Windows / Mac）ごとにレイヤとジェスチャを切り替えるようにします。 BTの接続先ごとの対応 前の記事でマウスジェスチャ自体は実装できたのですが、私の環境ではBT接続先ごとにOSを行き来することが多くあるので、それに対応します。 どのように切り替えを行うかですが、以下のような手順で実装しました。 BT接続先によってデフォルトレイヤを変更するマクロを実装する 接続先切り替えを行っているキーを、設定したマクロに置き換える Windows用のデフォルトレイヤーと別にMac用のデフォルトレイヤを定義する Windows向けに組んでいた複数のレイヤを、Mac向けに複製しました Windowsでctrlとして定義していた部分をcommandに変更するなどの異なる定義を行いました 1. BT接続先によってデフォルトレイヤを変更するマクロを実装する Behaviorの&btと&toを使って、BT接続先の切り替えとレイヤーの切り替えを一回でできるマクロを作成します。 （= 接続先を変えた瞬間に、使うキーレイアウトも切り替える） 私の場合、BT接続先は0と1がWindows用のプロファイル、2がMac用のプロファイルになっているので、以下のように設定しました。 &toに設定している5レイヤは別途定義します。 2. マクロに置き換え 接続先切り替えを行っているキーの設定を変更します。 私の場合、接続先切り替えを行うキーをまとめたレイヤーをlayer_4に定義しています。 3. Macのデフォルトレイヤを定義 keymap editorで「Duplicate layer」という項目を選択すると、現在定義されているものと同じレイヤーを複製することができます。 これを使って、Windows用に定義していたレイヤを複製します。 Windows用のデフォルトレイヤが0レイヤ、Mac用のデフォルトレイヤは5レイヤに定義しています。 マウスジェスチャのMac対応 Windowsの仮想デスクトップ起動のコマンドと、Macのミッションコントロールの起動コマンドは異なるため、別々で定義する必要があります。 変更ファイルは以下の通りです。 /config/keymap.keymap /boards/shields/torabo_tsuki_lp/torabo_tsuki_lp.dtsi /boards/shields/torabo_tsuki_lp/torabo_tsuki_lp_right.overlay keymap.keymap 以下のようにMac用のマウスジェスチャを定義します。 ついでに前回実装したWindows用のマウスジェスチャもわかりやすい名前に変更しておきます。 / { // ...中略... // Windows用とMac用の二つを定義する zip_mouse_gesture_for_win: zip_mouse_gesture_for_win { compatible = "zmk,input-processor-mouse-gesture"; #input-processor-cells = <0>; enable-eager-mode; prev_tab { pattern = <GESTURE_RIGHT>; bindings = <&kp LC(LS(TAB))>; }; next_tab { pattern = <GESTURE_LEFT>; bindings = <&kp LC(TAB)>; }; vdesk { pattern = <GESTURE_DOWN>; bindings = <&kp LG(TAB)>; }; vdesk_send_next { pattern = <GESTURE_UP>; bindings = <&kp LG(LC(LS(RIGHT)))>; }; }; zip_mouse_gesture_for_mac: zip_mouse_gesture_for_mac { compatible = "zmk,input-processor-mouse-gesture"; #input-processor-cells = <0>; enable-eager-mode; vdesk_prev { pattern = <GESTURE_RIGHT>; bindings = <&kp LC(LEFT)>; }; vdesk_next { pattern = <GESTURE_LEFT>; bindings = <&kp LC(RIGHT)>; }; vdesk { pattern = <GESTURE_DOWN>; bindings = <&kp LC(UP)>; }; vdesk_down { pattern = <GESTURE_UP>; bindings = <&kp LC(DOWN)>; }; }; // ...中略... }; torabo_tsuki_lp.dtsi layer_listenersの設定を変更して、マウスジェスチャのオンオフを設定するレイヤを定義します。 ...

こんにちは、ナナオです。 前回、torabo-tsuki lp xsを購入したという記事を書きました。 ということで最近結構カスタマイズしているのですが、今回はマウスジェスチャを実装したので一旦記事にしておこうと思います。 リポジトリはこちらです。 GitHub - satodaiki/zmk-keyboard-torabo-tsuki-lp · GitHub マウスジェスチャの実装 変更するファイルは以下の4ファイルです。 /config/west.yml /config/keymap.keymap /boards/shields/torabo_tsuki_lp/torabo_tsuki_lp.dtsi /boards/shields/torabo_tsuki_lp/torabo_tsuki_lp_right.overlay ymlファイル以外のファイル更新の際は末尾にセミコロンを入れるのをお忘れなきよう…（私はこれで何回もビルド失敗しました） west.yml まずは必要なライブラリを追加します。 マウスジェスチャの実装は以下のライブラリを使用します。 GitHub - kot149/zmk-mouse-gesture: A ZMK module that converts combinations of 4-direction mouse strokes into key presses or any other behaviors. · GitHub また、特定のレイヤに入った時と離れた時に特定のBehaviorを呼び出すためのライブラリも使用します。 （これはマウスジェスチャの実装で定義されているBehaviorを呼び出すために使用します） GitHub - ssbb/zmk-listeners: ZMK module to invoke behaviors on certain events. · GitHub ライブラリの追加はwest.ymlに以下のように追記すればよいです。 manifest: remotes: - name: zmkfirmware url-base: https://github.com/zmkfirmware - name: sekigon-gonnoc url-base: https://github.com/sekigon-gonnoc # 以下の4行を追加 - name: kot149 url-base: https://github.com/kot149 - name: ssbb url-base: https://github.com/ssbb projects: - name: zmk remote: zmkfirmware revision: v0.3 import: app/west.yml - name: zmk-component-bmp-boost remote: sekigon-gonnoc import: west.yml revision: v0.2 - name: zmk-feature-status-led remote: sekigon-gonnoc revision: main - name: zmk-driver-paw3222 remote: sekigon-gonnoc revision: torabo-tsuki - name: zmk-feature-cdc-acm-bootloader-trigger remote: sekigon-gonnoc revision: v0.2 - name: zmk-feature-non-lipo-battery-management remote: sekigon-gonnoc revision: main # 以下の6行を追加 - name: zmk-mouse-gesture remote: kot149 revision: v1 - name: zmk-listeners remote: ssbb revision: v1 self: path: config keymap.keymap マウスジェスチャを定義します。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最大公約数 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 まずは愚直に以下のように実装しました。 package main import "fmt" func main(){ var a, b int fmt.Scan(&a, &b) min := 0 if a < b { min = a } else { min = b } for i := min; i > 0; i++ { if a % i == 0 && b % i == 0 { fmt.Println(i) return } } } ですが、これだとタイムオーバーになってしまいました。 ということで修正します。 ユークリッドの互除法 を用います。 これは 「AとBの最大公約数は、BとA%Bの公約数と等しい」 という性質を利用して最大公約数を求める方法です。 この方法を用いると計算量がO(log(max(A, B)))となります。 ユークリッドの互除法は再帰を使って簡単に実装できます。 package main import "fmt" func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) } func main(){ var a, b int fmt.Scan(&a, &b) fmt.Println(gcd(a, b)) } うーん、びっくりするくらい簡単に実装できましたね。。 ただすぐわすれちゃいそう… というわけで今回はこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 素数判定 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 最初は以下のように実装しました。 package main import "fmt" func main(){ var n int fmt.Scan(&n) if n == 1 { fmt.Println("NO") return } for i := 2; i < n; i++ { if n % i == 0 { fmt.Println("NO") return } } fmt.Println("YES") } （ほんとの最初はn = 1のときの考慮もなかったことは内緒） ですが当然のように実行時間オーバーしてしまいました。 残念。。 ということで解説を見ると…目から鱗な解決法がありました。 実は調べるのは Nの0.5乗（ルートN） まででいいです。 なぜかというと、 N に 1 と N 以外の約数があると仮定した場合、少なくとも 1 つは N の 0.5 乗（ルート N ） 以下の約数があることになるからです。 ということで実装を変更します。 なんと先ほどのコードに2文字追加するだけで解決できてしまいます。 package main import "fmt" func main(){ var n int fmt.Scan(&n) if n == 1 { fmt.Println("NO") return } // 条件式をi*i < nとするだけでOK for i := 2; i*i < n; i++ { if n % i == 0 { fmt.Println("NO") return } } fmt.Println("YES") } いやぁびっくりしました。確かに言われてみればという方法でした。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 べき乗の計算 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 まずは以下のようにべき乗を計算して余りを出力する実装をしました。 package main import "fmt" func main(){ var n int fmt.Scan(&n) exp := 1 for i := 1; i <= n; i++ { exp *= 2 } fmt.Println(exp % 1000003) } ですがこれだと実行時間エラーになりました。 以下のように、繰り返し二条法を使うことで解決しました。 package main import "fmt" func main(){ var n int fmt.Scan(&n) m := 1000003 p := 2 ans := 1 for 0 < n { if n & 1 == 1 { ans = ans * p % m } p = p * p % m n >>= 1 } fmt.Println(ans) } シフト演算とかしてるのであまり直感的でないので、ちょっとAIと壁打ちしてもう少し理解を深めます。。 ではこれで👍