競技プログラミングを始めて6ヶ月が経ちました

雑記 競技プログラミング

最近はブログの更新も競プロへの出場も疎かになってしまいました。と同時に5月のゴールデンウィークに行われた AtCoder の AGC014 に初めて競技プログラミングのコンテストに参加してから半年が経ってしまいました。というわけで短い期間を振り返ろうと思います。

就職活動をするに当たって、Pythonを効率よく勉強する手段として採用したのが競技プログラミングを始めたきっかけです。何しろそれまでのプログラミング経験は大学1回生の時にC++を触ったことがあるという程度で、インターンなどをやってきた学生と渡り合う方法がありませんでした。録にプログラミングを書けない学生のまま面接をパスできるとは到底思えませんでしたし、そんな状態からいち早く抜けるために、"流行り"の機械学習分野と親和性のあるPythonを勉強して面接時の話題づくりになればいいかなくらいの気持ちで取り掛かりました。

２－３ヶ月位Pythonの基本的な文法や競技プログラミングの練習問題を解いて、5月から参加してみました。


初回の参加でしたが2問解くことが出来たのがうれしかった一方で、ルールがよくわからず何度も誤答を提出してしまっているのが微笑ましいですね。

AtCoderは最初の数回はレートが低く計算される方法を採用しているようで、回を増すごとにレートが上がる感じがして楽しかったです。

一方でパフォーマンスはほとんど向上していません…。そもそも純粋な勉強量が足りていないのですが、問題を通して復習をしても本番になるとひとつレベルの高い問題に手を付けられていないという印象があります。
どうやら ABC の D 問題クラスを安定して解けるようになることが次の目標のようです。グラフや動的計画法についてのアルゴリズムを総ざらいしたり、データ構造を理解して上手く使う、経験とひらめきでなんとかやっていくなどの工夫が必要な水準に近づいて来ているように思います。

フェルマーの小定理を使って mod の下での組み合わせ総数を求めるアルゴリズムを python で書いてみる

アルゴリズム 整数 python

注意：この記事は未完成です。こちらの記事を参考にお願いします
wakabame.hatenablog.com


{}_nC_r の素数 p で割った余りを求める方法について解説します. {}_nC_r は"n 個の異なるものからr 個を選ぶときの組み合わせの数"を表しており, 階乗記号 k!=k\times(k-1)\times \cdots \times 2\times 1を用いて,

{}_nC_r=\dfrac{n!}{(n-r)! r!}

と表されます. 階乗の大きさは指数関数的に増大していくので, 分母と分子は非常に大きな数になりえます. 素数 p で割った余りさえわかればよいことを用いて, どうにか計算量を減らしていきましょう.

続きを読む

mod の下での指数計算をするアルゴリズムを python で書いてみる

python アルゴリズム 整数

整数 a と整数 n に対して, a^n を整数p で割った余りを出力します. 安直に a を n 回乗じてからpで割れば良いのではないかと考えたくなりますが, この方法には2つの欠点があります.

  1. n 回乗じるのに計算量が O(n) かかってしまう.
  2. a^n は処理しきれなくなるくらい大きくなりえる.

この2点を解消する方法について解説します.

続きを読む

ABC074 の D 問題を python で解いてみようとしたら解けなかった

ABC-D AtCoder 競技プログラミング

ワーシャル＝フロイド法を用いた問題演習として, AtCoder Beginner Contest 074 の D 問題の解説をしてみます.

問題はこちら
abc074.contest.atcoder.jp
これは制限時間内に解けませんでした.

続きを読む

重み付き有向グラフの全2点間の距離を求める Warshall–Floyd 法を python で書いてみる

アルゴリズム python グラフ

ワーシャル＝フロイド法とは

今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル＝フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマン＝フォード法は以前紹介しました:
wakabame.hatenablog.com

今回紹介するワーシャル＝フロイド法では, 頂点の集合を V としたとき, 任意の頂点 i,j に対してその間の最短距離を一挙に計算してしまいます. その代わり, 計算量は O(|V|^3) とやや大量になってしまいます.

続きを読む

典型的な DP (動的計画法) のパターンが整理されていたので Python で書いてみる

アルゴリズム python 動的計画法DP

動的計画法(DP)について, qiita でまとめられました

qiita.com
勉強になったのでメモ代わりに. やはり数列の添え字は0から始めて記述したほうが実装との親和性が高そうなので, 以下では数列は a[0], a[1],\cdots ,a[N-1] として書きます. ここで, N は数列の要素数を表します.

1. 最大和問題

N要素を持つ数列 a[0], a[1],\cdots ,a[N-1] から任意の個数の項を選んで和を取った時の最大値

def max_sum(N, a):
    dp = [0] * (N + 1)
    for i in range(N):
        dp[i + 1] = max(dp[i], dp[i] + a[i])
    return dp[N]
続きを読む

有向グラフ上の2点間の最短距離を求めるアルゴリズム Bellman–Ford 法を python で書いてみる

python アルゴリズム グラフ

有向グラフとは

有向グラフ(directed graph)とは, 頂点(vertex)と辺(edge)からなり, 辺は (v_1, v_2, c) の形式を持ち, 頂点 v_1 から頂点 v_2 へはコスト c で移動できることを表しています. 辺に対して逆向きの進路があるとは限らず, あったとしても同じコストとは限りません.
今回はグラフの情報と始点が与えられたとき, 各頂点への最短距離をベルマン＝フォード法と呼ばれるアルゴリズムで求めていきます.
また, 有向グラフ上の2点間の最短距離を求めるアルゴリズムにはダイクストラ(Dijkstra)法と呼ばれるものもありますが, ベルマン＝フォード法の強みは辺の重みは負でもよいことが挙げられます.
一方, 負の重みを持つ辺があるときに考えなくてはならないのは負閉路の検出です. 閉路を一周するごとに距離をマイナスにすることができるものが存在する場合, その閉路を何度も通ることで最短距離をいくらでも縮めることができてしまい, 最短経路が定まりません. ですので負閉路が存在(かつ始点から到達)する場合には最短距離の代わりに警告を返します.

続きを読む