ABC088 を Julia で解いてみる

先ほどまで開催されていた AtCoder の ABC088 に参加してみました。
問題や解説についてはリンク先をご覧ください。
abc088.contest.atcoder.jp
最近は数値計算をしてみたいなと思うところがあり、Julia の勉強を始めていました。
というわけで、使い慣れてきた Python と Julia の二つで解いていきました。

続きを読む

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

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

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

2-3ヶ月位pythonの基本的な文法や競技プログラミングの練習問題を解いて、5月から参加してみました。
f:id:wakabame:20171106041134p:plain
f:id:wakabame:20171106041145p:plain
初回の参加でしたが2問解くことが出来たのがうれしかった一方で、ルールがよくわからず何度も誤答を提出してしまっているのが微笑ましいですね。

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

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

{}_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 で書いてみる

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

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

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

続きを読む

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

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

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

続きを読む

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

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

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

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

続きを読む

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

動的計画法(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]
続きを読む