Python で波動方程式の数値計算と動画 gif の書き出しをやらせてみよう

2次元正方形領域における波動方程式の初期値境界値問題を考えます。
こんな感じで波が伝播していく様子を気軽にシミュレーションできます。
f:id:wakabame:20180307201626g:plain

続きを読む

プログラミングコンテストにおける Python での標準入出力のまとめ

入力

1行に1要素の場合

N = int(input())
  • 文字列
S = input()

beta 版のコードテスト環境だと改行を含む場合もあるので注意しよう。
無印のコードテストとテスト時には改行は含まれない。
f:id:wakabame:20180304121614p:plain
気になる場合は input().rstrip() とすればよい。

1行にスペース区切りで複数要素の場合

  • 2つの数字を別の変数 N, M に
N, M = map(int, input().split())
  • 2つの文字列を別の変数 S, T に
S, T = map(str, input().split())
  • 複数の数字をリスト A に
A = list(map(int, input().split()))

複数行に1要素がある場合

  • 複数の数字をリスト A に
A = [int(input()) for _ in range(N)]
  • 複数の文字列をリスト A に
A = [input() for _ in range(N)]

beta版のコードテスト環境下では input().rstrip() とすればよい。

複数行にスペース区切りで複数要素の場合

  • 複数の数字をリスト A に
A = [list(map(int, input().split())) for _ in range(N)]

A[i][j] は  i+1 行目の j+1 文字目を表す

出力

1要素の出力

  • 文字列または数字 A を改行つきで表示
print(A)

複数要素の出力

  • リスト A を1要素ごとに改行して出力
[print(A[i]) for i in range(N)]
  • リスト A を空白区切りで出力
print(' '.join(map(str, B)))

クォーテーション内の半角スペースが挿入される。
別の文字(例えばカンマ)で区切りたい場合はそこを変更すればよい。

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
これは制限時間内に解けませんでした.

続きを読む