競技プログラミングでも 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) であるためそちらのほうが影響するかもしれません。

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

以前に投稿した記事

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 などを使うのがよいかもしれません。

 

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

DLR で名前付き引数を使う

C# で、メソッドに引数として「キーと値のペア」を渡す方法を考えてみます。
例えば HTTP で GET でアクセスするときに URL でクエリ文字列を指定する場合が挙げられます。

よく使われているのは、メソッドの引数に Dictionary や匿名型オブジェクトを渡す方法かと思います。
以下の HttpHelper クラスのように実装します。
なお、WebClient クラスではクエリ文字列 (QueryString プロパティ) は NameValueCollection 型であるため、
受け取った情報を NameValueCollection 型に変換しています。

なお、ここでは題材として CGI’s 郵便番号検索 API を利用しています。

さて、動的言語ランタイム (DLR)名前付き引数を利用して、引数の情報を実行時に解決できないかと考えると、
次のような方法を思いつきます。

dynamic http = new DynamicHttpProxy();
var result = http.Get(Uri_Cgis_Xml, zn: "402", ver: 1);

実際、DynamicObject クラスを継承した DynamicHttpProxy クラスを次のように作れば可能です。

TryInvokeMember メソッドの中で、引数の名前は binder.CallInfo.ArgumentNames で取得できます。
ただし、引数の名前を指定せずに渡された分はここに含まれない (コレクションの長さが変わる) ため注意が必要です。

 

また、C# 7.0 で追加された ValueTuple を利用して、

var result = HttpHelper.Get(Uri_Cgis_Xml, (zn: "6050073"));

とする案もありましたが、

  • 要素が 1 つ以下の場合、タプル リテラルを記述できない
  • コンパイル後はフィールド名が残らないため、実行時に動的に取得できない

という制約により実現できませんでした。

次回:インターフェイスに対する透過プロキシ

作成したサンプル
DynamicHttpConsole (GitHub)

バージョン情報
C# 7.0
.NET Framework 4.5

参照
動的言語ランタイムの概要
名前付き引数と省略可能な引数
タプル – C# によるプログラミング入門

命題論理を実装する (C#)

// この投稿は 数学 Advent Calendar 2016 の 16 日目の記事です。

命題といえば高校数学で「かつ」「または」「ならば」などを学習すると思いますが、
この投稿では、これらを一般化、形式化した命題論理をプログラミングで表現することを目指します。
プログラミングをしない方も、適宜飛ばせばなんとか読めると思います。

用語や定義については、主に Raymond Smullyan「記号論理学: 一般化と記号化」の第 7 章「命題論理入門」に記載されているものを使い、
解説と実装をしていきます。
プログラミング言語としては C# (.NET) を利用します。

Raymond Smullyan「記号論理学: 一般化と記号化」
「記号論理学: 一般化と記号化」
高橋 昌一郎, Raymond Smullyan, 川辺 治之

 

論理結合子

任意の命題 p は、真偽値 (truth value) を持ちます。真偽値とは、真 (T) または偽 (F) です。
そして、「かつ」「または」「ならば」などを一般化した概念を論理結合子 (logical connective) と呼び、次のものがあります。

  1. 否定 (~p)
    真偽値を反転させます。
  2. 論理積 (p ∧ q)
    p および q がともに真のときに限り真です。
  3. 論理和 (p ∨ q)
    p または q のうち、少なくとも一方が真のときに真です。
  4. 含意 (p ⇒ q)
    ~p ∨ q と同義です。
  5. 同値 (p ≡ q)
    (p ⇒ q) ∧ (q ⇒ p) と同義です。計算機においては、XOR 演算の否定と同義です。

論理式

さらに、論理式を次のように定義します。

  • 命題変数 (propositional variable): 命題を表す変数。値は、真または偽となりうる。
  • 命題定数 (propositional constant): 真を表す t および偽を表す f
  • 論理式 (formula): 命題変数、命題定数、論理結合子により構成される式。

ここまでの内容をもとに、論理式を実装します。 論理結合子は、否定のみが単項で、他はすべて二項です。

式を簡単に記述できるようにするため、静的メソッドを用意します。

 

恒真式および矛盾

論理式のうち、含まれる命題変数がどのような真偽値の組合せになっても真であるものを恒真式 (tautology) と呼びます。
逆に、含まれる命題変数がどのような真偽値の組合せになっても偽であるものを矛盾論理式または矛盾 (contradiction) と呼びます。
簡単な例を挙げると、p ∨ ~p は恒真式で、p ∧ ~p は矛盾です。

論理式が恒真式あるいは矛盾であるかどうかを判定するためのメソッドは、次のように実装できます。

以上のコードをまとめて、Blaze (GitHub) というライブラリとして公開しています。 NuGet でインストールできます。

 

ライブラリを使ってみる

さて、このライブラリを利用すると、命題論理に関する定理を証明できるようになります。
実際にいくつかやってみましょう。
Visual Studio で新規のコンソール アプリケーション プロジェクトを作成して、NuGet で Blaze をインストールします。
そして次のようなコードを記述します。

恒真式であるということは、その論理式がつねに成り立つということです。
このコードを実行することで、三段論法、背理法、対偶などを証明できます。

PropositionsConsole

 

次回は、このライブラリを利用してもう少し高度な問題を解いてみます。

次回: 命題論理の複雑な問題を解く (C#)

作成したライブラリ
Blaze (GitHub)
Blaze (NuGet Gallery)

作成したサンプル
PropositionsConsole (GitHub)

バージョン情報
.NET Framework 4.5

参照
Raymond Smullyan「記号論理学: 一般化と記号化」

Azure Table の検索条件を LINQ で指定する

Azure Storage の SDK (Windows Azure Storage) を利用して .NET のクライアントから Table のデータを取得する際に、
検索条件を指定しようとすると、通常の実装では次のようなコードになり少し複雑です。
この例では、フィルター条件を 2 つ指定しています。


var query = new TableQuery<Person>()
    .Where(TableQuery.CombineFilters(
        TableQuery.GenerateFilterCondition("PartitionKey", QueryComparisons.Equal, "2015"),
        TableOperators.And,
        TableQuery.GenerateFilterConditionForInt("Age", QueryComparisons.LessThan, 20)));

var result = PeopleTable.ExecuteQuery(query).ToArray();


ここで、Person  は TableEntity を継承したクラスで、PeopleTable は CloudTable 型のオブジェクトです。

結局、上記の Where メソッドに渡されるのは、

(PartitionKey eq ‘2015’) and (Age lt 20)

という文字列になります。
これなら string.Format メソッドでもよいのではないのかという気もしますが、
プログラミングのミスを防ぐためには、フィルターや射影などの検索条件は LINQ で指定したいところです。

検索条件を LINQ で指定する方法として TableServiceContext クラスを使う方法もあるようですが、
現在は Obsolete 属性が指定されており、非推奨となっています。

とはいえ、自力で IQueryable<T> を実装するのも骨が折れるので、
ここでは簡易的に、TableQuery<T> の拡張メソッドとして Select および Where メソッドを実装していきます。
ラムダ式で指定された検索条件を式ツリーとして受け取って解析し、動的にクエリを生成します。

このような TableHelper クラスを実装することで、Azure Table の検索条件を LINQ で指定できるようになります。
ただし、文字列の不等式については、String クラスの演算子として不等号が定義されていないため、

p.LastName >= "W"

と書くことができず、

p.LastName.CompareTo("W") >= 0

のようにせざるを得ませんでした。

 

作成したサンプル
ExpressionsConsole (GitHub)

バージョン情報
Windows Azure Storage 6.0.0

参照
Windows Azure Storage
Expression<TDelegate> クラス
TableQuery<TElement> Class

Windows Azure Storage Extensions
テーブル サービスに対する LINQ クエリの作成 (古い形式)
TableServiceContext Class (古い形式)