数論・素数に関するメソッドを実装する

数論・素数に関するメソッドを C# で一通り実装してまとめました。
通常の数値計算プログラミング用にも、また競技プログラミング用のライブラリとしても使えます。

機能は次の通りです。

Euclid 互除法

  • 最大公約数 (GCD)
  • 最小公倍数 (LCM)
  • ax + by = 1 の解 (Euclid 互除法の拡張)

素数

下の O(x) は計算量のオーダーを表します。

  • 素因数分解
    • O(√n)
  • 約数の列挙
    • O(√n)
  • 素数判定
    • O(√n)
  • n 以下の素数の列挙
    • およそ O(n)
  • m 以上 M 以下の素数の列挙
    • およそ O(max(√M, M – m))

ソースコードは以下の通りです。
ここではシンプルな実装とし、例外処理も全体的に省略しています。
さらに無駄な演算処理を除くように改良することで、もう少し速くすることはできるはずです。

使用例を次に示します。

前回: 二分探索のライブラリ化

作成したサンプル

バージョン情報

  • C# 7.0
  • .NET Standard 2.0

参照

カテゴリー: アルゴリズム, 数学. タグ: . 1 Comment »

二分探索のライブラリ化

// Competitive Programming (2) Advent Calendar 2019 の 20 日目の記事です。

競技プログラミングでたびたび利用する二分探索について考察してみます。
といっても、とくに競技プログラミングに限らず活用できると思います。言語は C# です。

まず二分探索の基本的な例として、昇順にソートされた整数のリスト a に対して「値 v をリストに挿入するときのインデックス」を求めてみます。 これは「値 v より大きい値が最初に現れるインデックス」と考え、最後の要素が v 以下のときはリストの長さ a.Count を返すことにすれば、次の IndexForInsert メソッドとして実装できます。

同じ考え方を利用して、Array.BinarySearch メソッドのように「値が一致するインデックスを求める。一致しない場合は、それより大きな値のインデックスの補数」という仕様にするには、上の IndexOf メソッドのように書けます。

注意点:

  • IList<T> インターフェイスは、 T[]List<T> クラスを含みます。
  • リスト内の値は重複してもかまいません。
  • 例外処理は除いています。
  • (l + r - 1) / 2 とするとオーバーフローすることがあるため、 l + (r - l - 1) / 2 としています。

上記のメソッドは、リストのみ、しかも昇順にソート済みという制約の下で適用することができます。
そこで、さらに汎用的に使えるように、抽象度を上げてライブラリを作ることを考えます。

二分探索により実現できることは、見方を変えると「状態が変化する境界を見つけること」、厳密には「与えられた条件に対し、ある境界が存在して、その前方と後方で真偽が逆転する場合にその境界を見つけること」だと考えます。
この考え方で先ほどのコードから抽象化した部分を抜き出すと、次の First メソッドのようになります。

この形にすれば、降順のリストにも、リスト以外の数値の範囲にも適用できます。
例として、AtCoder の ABC 146 C – Buy an Integer を解いてみます。
先ほどの First メソッドに対して Last メソッドを用意し (コメントは省略)、価格が所持金以下となる最後の整数を求めればよいです。

だいぶ簡潔に書けました。

次に小数向けのメソッドを用意して、二分法で平方根を求めてみます。
誤差を表す桁数を指定できるようにしています。

まとめ

というわけで、今後は二分探索の問題を意味論的に「与えられた条件を満たす最初または最後の値を求める」と考えれば、
今回作成したライブラリを使って実装ができます。

その他

  • これまでは二分探索を実装するときに再帰を使っていたのですが、おそらく過去に読んだ解説に再帰を使うものが多かったためだと思います。競技プログラミングを始めてから自然に while (l < r) を使うようになりました。
  • Array.BinarySearch メソッドList.BinarySearch メソッドでは、重複する値を検索する場合、その最初のインデックスが返ってくるとは限りません。

前回: 競技プログラミングでも C# で簡潔に書きたい
次回: 数論・素数に関するメソッドを実装する

参照

カテゴリー: アルゴリズム. タグ: . 2 Comments »

競技プログラミングでも C# で簡潔に書きたい

// Competitive Programming (2) Advent Calendar 2019 の 15 日目の記事です。

競技プログラミングの AtCoder というものを今年の8月に始めて、3~4か月をかけて水色に到達しました。

20191124-Rating

スピード勝負は得意ではないのですが、難しめの問題を少し時間をかけて解くのが向いているようです。
また、簡潔なコードを書くことを心掛けていて、ショートコード C# 部門があるとしたらだいたい優勝していると思います。
(スペースを切り詰めたりはしません。むしろ Visual Studio で既定のフォーマットをしてから提出しています。)

20191201-E

20191201-F

 

さて、12月1日に実施された 三井住友信託銀行プログラミングコンテスト2019 では、別解が多くあり考察を楽しめる問題セットでした。
全体的にだいぶ簡潔に書ける回だったので、その中から問題 B, C, D を解説してみたいと思います。

B – Tax Rate

税込価格で N 円となるときの税抜価格はいくらか。

小数を考慮しなければならないため、第一感ではどんな値が適合するのかもやっとしますが、
そんなときは 1 から N までの全探索でも正解できます。LINQ を使って次のように書けます。

しっかり考察してみると実は、税抜価格が1だけ離れると税込価格も1以上離れることから税抜価格と税込価格は1対1に対応し、
税込価格 N に対する税抜価格はたかだか1個存在することがわかります。
また、 1.08X ≥ N つまり X ≥ N / 1.08 であることから、X の候補は N / 1.08 の天井 (ceiling) に限られます。
(これより 1 以上大きい整数の税込価格は N+1 以上になってしまう。)
あとはこれの税込価格が実際に N に一致するかどうかを確かめれば OK です。

 

C – 100 to 105

合計価格がちょうど X 円となるような買い物ができるか。

商品の価格の差が1円単位なので、商品の個数が N のとき、合計価格の候補は 100N ≤ X ≤ 105N の範囲の整数値となります。
そこでこの問題も、やはり安全策の全探索で通ります。

では今度もまたしっかり考察してみます。
商品の個数 N が [X / 100] より大きい場合は、合計価格は X を超えてしまいます。
また、N が [X / 100] より小さい場合に 100N ≤ X ≤ 105N を満たしているとすると、N+1 もこれを満たしているはずです。
したがって N = [X / 100] の場合のみを調べればよく、次のようなコードで書けます。

 

D – Lucky PIN

半角数字からなる文字列 S から3文字を取り出してその順に並べたものは何種類あるか。

例によって 000 から 999 までを全探索します。
たぶんこれが一番短いと思います (当社比)

いちおう次に計算量を考慮して別解を考えてみましょう。
まず前処理として、どの文字がどのインデックスに現れるかを取得できるように辞書を作っておきます。
この辞書のキーはたかだか10種類です。
そして1文字目から順に、選択可能なインデックスの範囲から文字を選択していきます。
3文字目を選ぶときは、候補のうち最後のインデックスが2文字目のインデックスより大きければ成立します。

多重の foreach 文を使って探索してもよいのですが、今回は C# のクエリ式を使ってみます。
クエリ式は普段はそれほど使わないのですが、このようにコレクションの入れ子構造を平坦化 (flatten) するときは見やすくなると思います。通常の LINQ では SelectMany メソッドに相当します。

計算量は、1文字目が10、2文字目が N (たかだか N 文字しかない)、3文字目が10のため、全体で O(100・N) です。
また、2文字目のインデックスを探索するところを二分探索にすれば O(1000・logN) となります。
ただし、前処理が少なくとも O(N) であるためそちらのほうが影響するかもしれません。

次回: 二分探索のライブラリ化

以前に投稿した記事

ASP.NET SignalR でデバイスの回転状態を同期する

前回の transform と deviceorientation における回転の表現 (HTML) では、
そのデバイスのブラウザー上で回転の状態を表示していましたが、
今回は他のデバイスのブラウザーにネットワーク経由で同期するようにしました。

WebSocket で同期するためのフレームワークとして ASP.NET SignalR を利用し、
Azure Web App に GitHub からの継続的デプロイを設定しています。

HTML 3D Device Orientation on Web Browsers

 

これを実装する方法を以下に示します。

Visual Studio で空の ASP.NET Web プロジェクトを作成し、NuGet で Microsoft.AspNet.SignalR をインストールします。
まずサーバー側の C# コードとして、次のクラスを実装します。

Startup.Configuration メソッドの中で ASP.NET SignalR を有効にします。
そして、送受信をするためのハブとして SensorHub クラスを作成しています。
今回は、JavaScript の deviceorientation イベントで取得できる alpha, beta, gamma の値を引数で受け取って
クライアントに通知するだけです。なお、Clients.Others は送信者以外のクライアントを表します。

次に、クライアントとなる HTML を実装します。

センサーのデータを送信する sensor.html と、それを受信して表示する viewer.html に分かれています。
各 JS ファイルを <script> で読み込み、$.connection から各機能にアクセスします。

 

前回: transform と deviceorientation における回転の表現 (HTML)

作成したサンプル

バージョン情報

  • .NET Framework 4.7
  • ASP.NET SignalR 2.4.0

transform と deviceorientation における回転の表現 (HTML)

CSS の transform プロパティと JavaScript の deviceorientation イベントではともに 3D の回転状態 (姿勢、傾き) が登場しますが、
その扱い方に差があるため検証しました。
deviceorientation は、デバイスのジャイロ センサーが回転状態を通知することで発生するイベントです。

HTML の 3 次元座標系では、2 次元スクリーン座標系の x 軸および y 軸に加えて、スクリーンに垂直な z 軸が存在します。
デバイス (スマートフォンなど) を水平に持ち、北を向いた状態を基準に考えます。

このとき、CSS の transform プロパティと JavaScript の deviceorientation イベントにおける、
回転に関する性質の違いを下の表にまとめました。例えば z 軸を中心とする回転の角度は、現在は北を向いていたとしたら、
transform では東側 (時計回り) を向くと正、deviceorientation では西側を向くと正になります。

  transform deviceorientation
座標系 左手系 右手系
x 軸 右が正 右が正
y 軸 下 (手前) が正 上 (奥) が正
z 軸 (画面が水平のとき) 鉛直の上が正 鉛直の上が正
回転角度 回転軸の正方向に左ねじを進める場合が正 回転軸の正方向に右ねじを進める場合が正

 

検証のため、CSS の transform プロパティと JavaScript の deviceorientation イベントを利用して、
デバイスの回転状態を画面内の立方体オブジェクトに同期させるサンプルを作成しました。

DeviceOrientation

ジャイロ センサーを搭載した端末であれば、こちらのテストページで確認できます。
HTML のソースは以下の通りです。

以下は、各技術についての説明です。

transform プロパティ

transform プロパティで rotateX などを利用して回転状態を指定する場合、次に示すように複数の回転を重ね合わせることができます。

CSS:
transform: rotateX(45deg) rotateY(30deg) rotateZ(60deg);

JavaScript:
element.style.transform = "rotateX(45deg) rotateY(30deg) rotateZ(60deg)";

ただし、座標系ごと回転させながら左から順に適用します (オイラー角)。
これは、以前に 3D における回転の表現と相互変換で書いた通り、元の座標系のまま右から順に適用する、と考えても同じです。

以下に rotateX(45deg)rotateY(45deg) を組み合わせた例を載せておきます。

初期状態

rotateX(45deg) (左)        rotateX(45deg) rotateY(45deg) (右)

rotateY(45deg) (左)        rotateY(45deg) rotateX(45deg) (右)

deviceorientation イベント

window.addEventListenerdeviceorientation に対するイベントリスナーを登録します。
デバイスの回転状態が変化すると、イベントリスナーが呼び出されます。

引数の alpha, beta, gamma はそれぞれ z 軸、x 軸、y 軸を中心とした回転の角度を表し、
座標系ごと回転させながらこの順に重ね合わせたものが回転状態を表します。
それぞれの値の範囲は次の通りです。

  • z 軸: 0 ≦ alpha < 360
    • 北を向いたとき、alpha = 0
  • x 軸: -180 ≦ beta < 180
  • y 軸: -90 ≦ gamma < 90

 

回転状態の同期

以上から、デバイスの回転状態を画面内のオブジェクトに同期させるには次のようにします。

cubeEl.style.transform = `rotateZ(${-e.alpha}deg) rotateX(${-e.beta}deg) rotateY(${e.gamma}deg)`;

正負の符号に注意します。
結果として、z 軸および x 軸における回転角度の正負は異なり、y 軸では同じになります。

 

次回は、回転状態をネットワーク経由で同期させます。

次回: ASP.NET SignalR でデバイスの回転状態を同期する

作成したサンプル
参照
transform
deviceorientation

半角カタカナなどを変換するライブラリ

半角カタカナからひらがなへの変換や、Shift_JIS の文字エンコーディングへのプロパティなど、
日本で利用される機能を集めたライブラリ Zipangu を制作しました。
以前にハッカソンで日本の郵便番号を検索するための Postal Codes JP Web API を制作しており、そこからのスピンオフです。

ターゲット フレームワークを .NET Standard 2.0 および .NET Framework 4.0 以降としています。
したがって、.NET Core 2.0、UWP 10.0.16299 などでも利用可能です。

機能

文字の変換

  • ASCII 文字 → 全角 ASCII 文字
  • 全角 ASCII 文字 → ASCII 文字
  • ひらがな → カタカナ
  • カタカナ → ひらがな
  • 半角カタカナ → ひらがな
  • 半角カタカナ → カタカナ

.NET Framework に以前から存在する Microsoft.VisualBasic.dll の Strings.StrConv メソッドとは、一部の仕様を変更しています。
例えば、「ヴ」をひらがなに変換した結果が「ゔ」になるようにしています。
仕様の詳細はこちらに記述しました:

文字エンコーディング
各文字エンコーディング (文字コード) のインスタンスにアクセスするためのプロパティを提供します。

  • Shift_JIS (932)
  • ISO-2022-JP (50220)
  • EUC-JP (51932)

利用方法

セットアップ
プロジェクトに NuGet で Zipangu をインストールします。

コード (C#)
このライブラリの使用例を以下に示します。

 

バージョン情報
  • .NET Standard 2.0
  • .NET Framework 4.0
参照
カテゴリー: .NET Core, ライブラリ. タグ: . Leave a Comment »

Roslyn の構文解析を使ってデバッガーを自作する

// C# Advent Calendar 2018 の 23 日目の記事です。

デバッガーのようなものを自作してみました。

動機

  • 普段は Visual Studio を使っているが、デバッグ時に手動でステップ実行するのが面倒
    • ループなどでステップ数が多い場合
    • 分岐の様子や変数の状態を軽くチェックしたい場合

解決案

  • ステップの時間間隔だけを指定して、デバッガーを自動で実行させる
    • 変数の一覧が表示される
    • 時間間隔をリアルタイムで調節できる
  • .NET Compiler Platform (Roslyn) の構文解析の機能を使い、各ステップの間にデバッグ用のコードを差し込めば実現できそう

結果

というわけで、WPF でプロトタイプ「Tick-tack Debugger」を作ってみた結果、このようになりました。
例として、ニュートン法で平方根を求めています。 (クリックで拡大)

 

解説

以下は概略の技術解説です。
WPF アプリを作成する前に、まず .NET Framework 上のコンソール アプリで実験してみます。
C# の構文解析を使うには、NuGet で Microsoft.CodeAnalysis.CSharp をインストールします。

デバッグ対象となるソースコードにデバッグ コードを挿入し、それを動的にコンパイルして実行する、という方針です。
コンソール アプリのソースコードを以下に示します (全体のソリューションは SyntaxTreeSample にあります)。

SyntaxHelper クラスでは、デバッグ対象の C# ソースコードを構文ツリー (SyntaxTree) に変換して走査し、
各ステートメントの前にデバッグ用のコード行を挿入していきます。

CSharpSyntaxTree.ParseText メソッドを使うことで、ソースコードを構文ツリーに変換できます。
また、メソッド・ステートメント・式など、すべてのノードを表す親クラスは SyntaxNode クラスであり、

  • Parent プロパティ: 親
  • Ancestors メソッド: 祖先
  • ChildNodes メソッド: 子
  • DescendantNodes メソッド: 子孫

が存在することを知っておけば、だいたいの探索ができるでしょう。

この他に、デバッグ用のコードから呼び出されるメソッドを定義するクラス ライブラリとして DebuggerLib を作成しています。
各ステートメントの位置、およびその直前で存在する変数とその値を通知するために、このライブラリを経由させます。

Program クラスでは、生成されたデバッグ用のソースコードをファイルに保存したら、
System.CodeDom.Compiler 名前空間の CodeDomProvider を使ってこれをコンパイルし、
そのエントリ ポイント (Main メソッド) を呼び出します。
また、デバッグ コードが実行されたときのイベントハンドラーを登録しておき、
Thread.Sleep メソッドを使って、指定した時間だけ停止させます。

これで、デバッグ対象の元のソースコードが次の Program.cs だとすると、
デバッグ用のソースコードとして下の Program.g.cs が生成されます。

作成したコンソール アプリを実行すると、次の図のようになります (時間間隔は 0.3 秒)。

 

以上をもとに、WPF アプリでデバッグ ツールを作成しました。
左側の C# ソースコードの部分は TextBox で、編集もできます。
デバッグ実行時は、各ステートメントを選択状態にすることでハイライトしています。
右側の変数一覧が表示される部分は DataGrid です。

(図は円周率を求める例)

今回は上記の方法でプロトタイプを作ってみましたが、
デバッグ コードの挿入やコンパイルに関しては、よりスマートな方法があるのではないかと思います。

注意点
  • 考えられうるすべてのステートメントには対応できていません。また、Main メソッドしか構文解析していません。
  • コンパイル時に生成されるアセンブリ (EXE) は、%TEMP% フォルダー (ユーザーの AppData\Local\Temp) に保存されていきます。
  • TextBox で、IsInactiveSelectionHighlightEnabled を True に設定しても利かないことがあります。
    また、選択状態のハイライトがずれることがあります。
    RichTextBox で Run などを使うのがよいかもしれません。

 

作成したサンプル
バージョン情報
参照