夕立進行会報

別に計算用途があったわけでもないけど、有理数を分数のまま計算するためのクラスを作成してみた。1/3が0.333...にならずに1/3のまま計算できるもの。 ソースコード ちょっと長いけど全文載せる。 class RationalNumber : IEquatable<RationalNumber>, IEquatable<long>, IComparable<RationalNumber> { private bool sign = true; private long a = 0; private long b = 1; private static Regex Pattern = new Regex("&#92s*(-?[0-9]+)&#92s*(/&#92s*([0-9]+)&#92s*)?"); //-------------------- /// <summary> /// 分子の絶対値を取得します。 /// </summary> public long Numerator { get { return a; } } /// <summary> /// 分母の絶対値を取得します。 /// </summary> public long Denominator { get { return b; } } /// <summary> /// 小数値を取得します。 /// </summary> public double DoubleValue { get { var v = (double)a / (double)b; return SignValue * v; } } /// <summary> /// 値が0であるかを取得します。 /// </summary> ...

気づけばだいぶほったらかしになっていた。今日は競技プログラミングで出てくる「～で割ったあまりの数」についての覚え書き。 AtCoderでよく出てくる以下の文。 ～を10^9+7で割った余りを求めてください。 競プロ特有の表現なので初見は「なんのこっちゃ？」と思った。要は答えが通常の数値型では表現できない大きな数になるので、1000000007の剰余を答えろということ。 当然割る前の数を求めるとオーバーフローするので、途中途中で剰余をしながら答えを求めるわけだが。 (a + b) % m → (a % m) + (b % m) 各四則演算について上記のような置き換えが可能であることを確かめる。 証明 任意の二つの数x1,x2を以下のように定義する。 x1 = aM + c x2 = bM + d ※Mは除数、a,b,c,dは任意の整数 なお以下では除数Mでxの剰余を取ることを「x mod M」と記載する。 加算 y = x1 + x2 = (aM + c) + (bM + d) = (a + b)M + c + d y mod M = c + d = (x1 mod M)+(x2 mod M) よって (x1+x2) mod M = (x1 mod M)+(x2 mod M) 減算 加算と同じである。ただしプログラムの実装では計算過程で負の値が現れる可能性を考慮し、負値の場合Mを加算する処理を入れる。 乗算 y = x1 * x2 = (aM + c)(bM + d) = abMM + adM + bcM + cd y mod M = cd = (x1 mod M)(x2 mod M) よって (x1 * x2) mod M = (x1 mod M)(x2 mod M) 除算 ここまでは感覚的に理解してる人も多いと思う。除算だけ少し毛色が異なる。実はここが本題。 除算は以下のようにこねくり回してもMの倍数と定数項の形にできない。 y = x1 / x2 = (aM + c) / (bM + d) = aM / (bM + d) + c / (bM + d) つまるところ (x1 / x2) mod M = (x1 mod M) / (x2 mod M) は成り立たない。 ここで フェルマーの小定理 というものがある。その詳細や証明はひとまず置いてお...

主にAtcoderでやる競技プログラミングで再利用するために、C#で書いたコードたちを載せてみる。どれも既知のアルゴリズムなのでコピペとかして構わないけど、もし間違っていても責任はとらない。 また何かあれば追加するかも。 公約数／公倍数 最大公約数 static long Gcd(long m, long n) { if (m < n) {var t=m; m=n; n=t;} while (true) { var mod = m % n; if (mod == 0) return n; m = n; n = mod; } } ユークリッド互除法 の実装。 最小公倍数 ※2020/5/13 計算途中でのオーバーフローに対策 static long Lcm(long m, long n) { var x1 = Math.Max(m, n); var x2 = Math.Min(m, n); var gcd = Gcd(x1, x2); return x1 / gcd * x2; } 上のGcdが必要。最大公約数から最小公倍数を求める公式。 演算 累乗 ※2020/5/31 2^32でOFしてたのに対応 static long Pow(long x, long n) { long ans = 1; while (n > 0) { if (n % 2 == 1) { ans = ans * x; } n /= 2; if(n == 0) break; x = x * x; } return ans; } 通常はMath.powを使う累乗の手書き実装。n<0には対応しない。単純ループするとO(n)だが、2乗を入れ子にするアルゴリズムで実装してO(log n)。いわゆる繰り返し二乗法。 x^20 = (((x^2)^2)^2)^2 * (x^2)^2 累乗（Mod） ※2020/5/31 2^32でOFしてたのに対応 static long ModPow(long x1, long x2){ l...

空き時間に AtCoder というサービスをやってみたので感想や環境など。 概要 AtCoderは日本企業が運営している競技プログラミングのサイト。毎週主に土曜日の夜に定期コンテストが開かれていて、Webから登録すれば簡単に参加することができる。 コンテストの流れ コンテストは事前に告知された時間にみんなで一斉に行う。 開始時間になるとページに問題が表示されるので、それに沿うようにコーディングを行う。 ソースコードをWeb画面から送信するとサーバでコンパイル、テストケースが実行され成否が判定される。正解した問題数と回答時間で順位が決まるようだ。 プログラミング言語はC++やJavaなどの選択肢から選ぶが、主要なものはほぼ揃っている。COBOLなんかもあるが流石に利用者はほぼ見当たらない。自分はC#でやっている。 所感 プログラミングというよりはアルゴリズムのコンテストといった感じで、数学的な問いをプログラムで実装するようなものが基本。 評価は「インプットに対するアウトプット」「計算時間」「回答時間」でされるので、コーディングのフォーマットやエラー処理なんかは特に問われれない。 難易度 毎週やってるBeginner Contestは難易度準にA～Fまでの問題がある。 ABは初学者教本にあるような基礎。足し引きと分岐・ループができればだいたいOK。 Cは数1Aぐらいまでの内容で、プログラミング的にも再帰やコレクションの使い分け、計算量を想定した実装が必要になってくる。普通のプログラマはこのあたりが及第点だろうか。 Dからは動的計画法や漸化式みたいな考え方が出てくるし、既知のアルゴリズムをベースにしたりする必要があるので、現役理系学生以外は対策しないと厳しい。 実務に活かせるか 内容がアカデミック寄りなので、ほとんどの現場ではあまり直接的な関係はなさそう。実際の業務コーディングではアルゴリズムより機能の切り分けや将来設計、速度より安全な実装と適切なエラー処理などの方が大事になってくる。 検索エンジンやミドルウェアを作るならそういう機会もあるかもしれない。 就職アピールなら評価の対象は問題そのものよりも、プログラミングへの興味の高さや、やっていくうえでの工夫や学習法あたりになるだろうか。 コーディング環境とか 一応Webサイト上にデバッグ環境みたいなのはあるが、すべてそれで...