競技プログラミング

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 有向グラフの隣接行列と隣接リスト | レベルアップ問題集 | プログラミング学習サイト【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() } } これで実装できました。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最大公約数 | レベルアップ問題集 | プログラミング学習サイト【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 } // 最小の数から1ずつ減らして割り切れる数を探す 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と壁打ちしてもう少し理解を深めます。。 ではこれで👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 規則的な数列の和 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 最初は以下のように実装しました。 package main import "fmt" func main(){ var n, k int fmt.Scan(&n, &k) m := []int{1, 0, -1} c := n - 1 sum := 0 for c < k { sum += m[c % 3] c++ } fmt.Println(sum) } しかし、うまくいきませんでした。。 実行時間エラーになってしまったため、高速化が必要です。 解法としては、法則性を考えれば以下のようにN(1)で実装できます。 package main import "fmt" func main(){ var n, k int fmt.Scan(&n, &k) result := 0 switch n % 3 { case 1: if k % 3 >= 1 { result = 1 } case 2: if k % 3 == 0 { result = -1 } case 0: if k % 3 == 0 { result = -1 } } fmt.Println(result) } これですっきり実装できました👍

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最長の区間 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ var n, k int fmt.Scan(&n, &k) a := make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&a[i]) } x := 1 c := 1 for i := 0; i < n; i++ { x *= a[i] if x == 0 { c = 1 x = 1 } else if x >= k { fmt.Println(c) return } c++ } } ですがこれだと攻略はできませんでした。。 回答を見ながら修正しました。 package main import "fmt" func main(){ var n, k int fmt.Scan(&n, &k) a := make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&a[i]) } start := 0 end := 0 count := 1000000 mul := func(data []int) int { result := 1 for _, v := range data { result *= v } return result } for end < n && start <= end { if mul(a[start: end + 1]) >= k { if end - start + 1 < count { count = end - start + 1 } start += 1 } else if a[end] == 0 { start = end + 1 end += 1 } else { end += 1 } } fmt.Println(count) } ですがいまいち理解できていません。クソー ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最長の区間 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 まずは以下のように実装しました。 package main import "fmt" func main(){ var n, m int fmt.Scan(&n, &m) a := make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&a[i]) } s := make([]int, n) for i := 0; i < m; i++ { var mn, mx, t int fmt.Scan(&mn, &mx, &t) for k := mn - 1; k < mx; k++ { s[k] += } } for i := 0; i < n; i++ { fmt.Println(a[i] + s[i]) } この回答でもGoの場合解けるのですが、まぁ実行時間制限ギリギリなので、一応模範解答のように改修しておきましょう。 この実装、よく考えると累積和で解けるんですよね。 つまり、mnとmxは累積和の区間として考えることができるわけです。 実装としては以下の通りです。 package main import "fmt" func main(){ var n, m int fmt.Scan(&n, &m) a := make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&a[i]) } s := make([]int, n) for i := 0; i < m; i++ { var mn, mx, t int fmt.Scan(&mn, &mx, &t) s[mn - 1] += t if mx < len(s) { s[mx] -= t } } x := 0 for i := 0; i < n; i++ { x += s[i] fmt.Println(a[i] + x) } } あーすっきりした。 ...

こんにちは、ナナオです。 前回に引き続き競プロを実施していきたいと思います。 今回の問題は以下です。 最長の区間 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング】 実装 以下のように実装しました。 package main import "fmt" func main(){ var n, m int fmt.Scan(&n, &m) a := make([]int, n) x := 0 s := make([]int, n) for i := 0; i < n; i++ { fmt.Scan(&a[i]) x += a[i] s[i] = x } sum := 0 d := 0 l := 0 for r := 0; r < n; r++ { sum += a[r] for sum > m { sum -= a[l] l++ } c := r - l + 1 if d < c { d = c } } fmt.Println(d) } なんででしょう、しゃくとり法がなぜか直感的にちゃんと理解できていない… もっとAIと壁打ちして、ちゃんと理解できるようにしないと…！！ ということで今回はこれで👍