trsing’s diary

勉強、読んだ本、仕事で調べたこととかのメモ。

EFFECTIVE C# 6.0/7.0 読書メモ 項目27

項目27 最小限に制限されたインターフェイスを拡張メソッドにより既往拡張する

インターフェイスには最小限の機能を定義しておき、拡張メソッドを用意するようにする。

インターフェイスとして定義されたメンバを最小限に抑え、 補助的な機能を拡張メソッドとして定義する。こうすると、 インターフェイスを実装する側では作業量を最小にでき、インターフェイスを使用する側の利便性を最大化できる。

例えばSystem.Linq.Enumerableクラス。 System.EnumerableにはIEnumerable<T>に対する拡張メソッドが定義されている(WhereOrderByThenByGroupintoなど)。

IEnumerable<T>に対して拡張メソッドを定義すると、IEnumerable<T>を実装しているクラスを変更せずに機能を追加でき、すべてのコレクションに対してクエリ演算を行うことができる。

利用例

IComparable<T>を直感的にするため、 left.LessThan(right),left.GreaterThanEqual(right) を追加する。

public static class Comparable
{
    public static bool LessThan<T>(this T left, T right)
        where T : IComparable<T> =>left.CompareTo(right)<0;
    //略
}

インターフェイスを実装する側では1つのメソッド(CompareTo)だけの実装でよい。使用する側では直感的にわかりやすいメソッドとして呼び出すことができる。

アプリケーションで独自に定義するインターフェイスに対しても同様に、必要最小限の機能だけをインターフェイスに定義し、補助的なメソッドを用意する場合には拡張メソッドとして実装するとよい。

注意点

拡張メソッドよりクラスに定義されたメソッドのほうが優先される。インターフェイスを使用するようになっているコードの場合、型に定義されたメソッドよりも拡張メソッドの方が優先される。

public interface IFoo { }
public static class FooExtensions
{
    public static void NextMarker(this IFoo thing) { }
}
class MyType : IFoo
{
    public void UpdateMarker() => this.NextMarker();//拡張メソッドのNextMarkerが呼ばれる
}
class MyType2 : IFoo
{
    public void NextMarker() => Marker += 5;
    public void UpdateMarker() => this.NextMarker();//型に定義されたメソッドが呼ばれる
}
class MyType3 : IFoo
{
    public void NextMarker() => Marker += 5;
    public void UpdateMarker() => ((IFoo)this).NextMarker();//拡張メソッドのNextMakerが呼ばれる
}

EFFECTIVE C# 6.0/7.0 読書メモ 項目26

項目26 ジェネリックインターフェイスとともに古いインターフェイスを実装すること

ジェネリックインターフェイスをサポートするクラスを作成するなら、非ジェネリックインターフェイスもサポートする。

ジェネリック以前のコードも多数存在しており、それらの古いコードを使用して新しいコードを作成しなければならないため。

例えば、IEnumerable<T>IEnumerableから派生しいる。ICollection<T>IList<T>ICollectionIListから派生していないが、IEnumerable<T>を継承している。

ジェネリックインターフェイスのサポート

ジェネリックインターフェイスをサポートするには、適切なシグネチャを持ったメソッドをクラス内に追加すればよい。

このとき、明示的に実装(int IComparable.CompareTo(object obj))すれば、非ジェネリックインターフェイスが意図せず呼ばれることがない。

その他

派生クラスとは比較したくない場合、as演算子ではなく型のチェックをする。

obj.GetType()==typeof(Name);//objがNameの派生クラスでもfalse
obj as Name;//objがNameの派生クラスの場合Name型の参照を返す
> public class Name { }
> public class Name2 : Name { }
> var nm2 = new Name2();
> var nm2nm = nm2 as Name;//nullにならない
> nm2nm.GetType()
[Submission#1+Name2]

AtCoder Beginner Contest 126参加メモ

問題増えた!目標は3+\alpha

atcoder.jp

結果

A,B,CはAC。Dは方針決まったけど実装まで至らず。E,Fは問題ちょいみ。

後日、D,Eは自力でAC、Fは解説見てAC。

C:Dice and Coin

intで割り算して「あれ???」となっていました。初心者かよ。

D:Even Relation

例えばa-b-cとなっている場合、ac間の距離を求める必要はない。 aの色を決める、a-b間の距離でbの色を決める(偶数ならaと同じ色、奇数なら別の色)、b-c間の距離でcの色を決める(偶数ならbと同じ色、奇数なら別の色)とすればいい。

グラフ作成してどっか適当なノードの色を決め、そこから全探索。自ノードの次のノードとの距離で次のノードの色を決めていく。

グラフ作成するには・・・重みもいるし・・・えーと・・・複数グラフの接続も・・・と悩んでいるうちに時間切れ。残念。

E:1 or 2

後日ちゃんと問題を見てみると、

  • X,Y,Zからはカードに書かれた数字が決まらない
  • 同じグループの場合、1枚カードの数字がわかればほかのカードの数字もわかる

ということに気づいた。グループの数が魔法の使用回数ということ。グラフ作成すればグラフの数がグループの数になる。

※グループ
1 2 Z1
2 3 Z2
とあれば1,2,3は同じグループ。

F:XOR Matching

範囲にペアになるやつがあれば0になるからKを対称に挟めば(abc K cba)・・・あ、もう一個Kあるな。K以外でKを作れれば(K K' K K')・・・いや残りがあるから残りが上手く相殺できるならK abc K' cba K K' (abc=0))・・・えーとこんな都合のよいものになるかどうやって判定すればいいんだ・・・??

わからん。ちょっと視点を変えて各桁のビットに注目してみると・・・どれも2^{M-1}個になるのか・・・こっからKを・・・わからんもぅマヂ無理解説みょ・・・

\displaystyle{
\oplus_{i=0}^{2^{M}-1}i=0
} (各桁とも1の数が偶数個(2^{M-1})のため)

これからKを抜くにはKでxorを取ればよく

\displaystyle{
\left( \oplus_{i=0}^{2^{M}-1}i \right)  \oplus K=0\oplus K=K
}

おお・・・おお・・・

というわけで
K以外を適当に並べる(1) K 1を逆順に並べる K
とすればよい。

所感

実装力が・・・実装力が足りない・・・。

diverta 2019 Programming Contest E: XOR Partitioningメモ

atcoder.jp

うっかりE問題を見てしまい1週間うんうん唸り続ける羽目になったけどようやくなんとなくわかったのでメモ。公式解説のほかいろいろ見た。問題名でググって出てくるとこは大体目を通しましたよと。もはやどれを参考にできたかも覚えておらぬ。

解説の流れ

https://img.atcoder.jp/diverta2019/editorial.pdf

0,1,..,N+1の番号がついたN個のマスが左から右に向かって並んでいる。 マスiには整数b_{i}が書かれている。 すぬけ君ははじめに好きな整数Xを任意に選んだのち、駒をマス0に置く。 その後、以下のルールで駒を動かす。

  • 現在駒が置かれているマスより、番号が大きいマスにしか動かせない
  • 現在駒が置かれているマスに0が書かれているなら、Xが書かれているマスに駒を移動させなくてはならない
  • 現在駒が置かれているマスにXが書かれているなら、0が書かれているマスに駒を移動させなくてはならない

最終的に駒がマスNに置かれているように駒を動かす方法は何通りあるか?

与えられた数列をA、各要素をa_{i}, 1\leq i \leq Nとおく。
a_{i}の累積xorの数列をB、各要素をb_{i}, 1\leq i\leq Nとおく。
与えられた数列を分割して作成した数列をC_{i}, 1\leq i\leq k、 数列C_{i}の要素をc_{ij}, 1 \leq j \leq lとおく。下図みたいな感じ。
f:id:trsing:20190519135624g:plain

ある値XC_{i}たちの美しさが全て等しくなるとする。このとき、

C_{i}の要素に対してxorを取るとX
C_{i}に対して累積xorを取るとC_{1}=b_{d}=X,C_{1}\oplus C_{2}=b_{e}=0,C_{1}\oplus C_{2}\oplus C_{3}=b_{f}=Xと、X,0が交互に並ぶ形になる。

Bの要素からX0に注目し、交互に並ぶように選べば美しさが等しい分割となる。
f:id:trsing:20190519160046p:plain

簡単のためb_{N}0でない場合を考えます。このときはXが一意に定まります。

\oplus_{i=1}^{k}C_{i}=\oplus_{i=1}^{N}a_{i}=b_{N}だからb_{N}= 0 or X
b_{N}\neq0ならX=b_{N}Xが一意に定まる。

f:id:trsing:20190519140209p:plain

0/Xの遷移に加え、前の値の代わりに自分の値を使えるということだろう(あまり理解してない)
f:id:trsing:20190519151615p:plain

X= 0の場合は特殊ですが、容易に計算可能です。

値が0b_{i}の数がn個とすれば2^{n-1} (単に仕切りをどこにいれるかという話)。

bX0以外の数を取り除いたのち、ランレングス圧縮を行った数列における0の出現回数はbにおけるXの出現回数で抑えられることが重要です。

0Xに隣接していることになるので、圧縮すればせいぜいXの出現数+1

b_{i}= 0なるiに関する遷移をうまく遷移をまとめると

うまくまとめる・・・
f:id:trsing:20190519141517p:plain

ここで詰んだので他の解説やらを探すと次の方のコードおよび解説のおかげでなんとなくわかりました。ありがとうございます。

Submission #5380934 - diverta 2019 Programming Contest

自分の理解は次のようになります。あってるかどうかは知らぬ。

dp[j]からdp[i]への影響は途中にある0の個数による。 f:id:trsing:20190519151656p:plain
漸化式は
\displaystyle{
dp[i]=1+\sum_{j=0}^{i-1}\left( \sum_{k=j}^{i-1}z[k] \right)dp[j]\\ \hspace{20pt}=
1+\sum_{j=0}^{i-2}\left( \sum_{k=j}^{i-1}z[k] \right)dp[j]+z[i-1]dp[i-1]\\ \hspace{20pt}=
1+\sum_{j=0}^{i-2}\left( \sum_{k=j}^{i-2}z[k] + z[i-1] \right)dp[j]+z[i-1]dp[i-1]\\ \hspace{20pt}=
1+\sum_{j=0}^{i-2}\left( \sum_{k=j}^{i-2}z[k] \right) dp[j]+ z[i-1]\sum_{j=0}^{i-2} dp[j]+z[i-1]dp[i-1]\\ \hspace{20pt}=
dp[i-1]+z[i-1]\sum_{j=0}^{i-1} dp[j]
}
※最初の1は初手でiを選ぶ場合

上手く計算(dpの累積和、区間0の個数を記録しておく)すればO(bにおけるXの出現回数)。それぞれのXの出現回数の総数はNなので全体としてO(N)となる。

次のようにしてb_{i},b_{j}区間0の数を出せるようにしておけば使いまわせる。
f:id:trsing:20190519151936p:plain

所感

難しい・・・とても難しい・・・。考え方がわかってたとしても時間内に終わる気しねえ・・・。

EFFECTIVE C# 6.0/7.0 読書メモ 項目25

25 型引数がインスタンスのフィールドではない場合にはジェネリックメソッドとして定義すること

次の条件に該当しないのなら、ジェネリッククラスではなく非ジェネリッククラス内のジェネリックメソッドを定義するとよい。

ジェネリックメソッドのメリット

ユーザーとしては呼び出すのが楽(型の指定が必要ではない)。
作成者としてはアルゴリズムを更新する際の選択肢を増やすことができる(コンパイラが最適なメソッドを選択してくれる)。

ジェネリッククラスを定義

毎回型パラメータを指定する必要がある。
型によらずComparer.Default.Compare()が使用される。
実行時の型がIComparerを実装しているかを実行時に確認、適切なメソッドを呼び出すという手間がかかる

public static class Utils<T>
{
    public static T Max(T left, T right) =>
        Comparer<T>.Default.Compare(left, right) < 0 ? right : left;
    //略
}
double d1 = 4;
double d2 = 5;
double max = Utils<double>.Max(d1, d2);//型パラメータを指定

ジェネリッククラスにジェネリックメソッドを定義

型指定が不要。自動的に最適な型が呼ばれる。
ジェネリックバージョンより効率的。
後から型固有のメソッドを追加できる。

public class Utils
{
    public static T Max<T>(T left, T right) =>
        Comparer<T>.Default.Compare(left, right) < 0 ? right : left;
    public static double Max(double left, double right) =>//double型であればこっちが呼ばれる
        Math.Max(left, right);
    //public static double Max(int left, int right) =>//後からint型用のメソッドを追加できる
        Math.Max(left, right);
    //略
}
double d1 = 4;
double d2 = 5;
double max = Utils.Max(d1, d2);//型パラメータの指定不要

EFFECTIVE C# 6.0/7.0 読書メモ 項目24

24 親クラスやインターフェイス用に特化したジェネリックメソッドを作成しないこと

オーバーロード解決について。 ジェネリックメソッドは、型パラメータをそれぞれに該当するあらゆる型と一致できる。暗黙的型変換(例えば親クラスへの変換)よりも優先されるため、使用する側にとってわかりにくくなる場合がある。使用する側が混乱しないように実装すべき。

オーバーロード解決のルール

一致度が高いものが優先される

ufcpp.net

引数の型

引数の型は、以下のリストの上の方ほど「一致度が高い」と判断されます。

  • ぴったり一致する型
  • ジェネリックな型
  • 親クラス
    • 多段に派生している場合、近い方ほど優先
  • 暗黙的に変換できる型
  • object

public class MyBase{}
public interface IMessageWrite{/*略*/}
public class MyDerived : MyBase, IMessageWrite{/*略*/}
public class AnotherType : IMessageWriter{/*略*/}

static void WriteMessage(MyBase b){/*略*/}
static void WriteMessage<T>(T obj){/*略*/}
static void WriteMessage(IMessageWriter obj){/*略*/}

MyDerived d = new MyDerived();
WriteMessage(d);                        //WriteMessage<T>(T) MyDerived
WriteMessage((IMessageWriter)d);        //IMessageWriter MyDerived
WriteMessage((MyBase)d);                //WriteMessage(MyBase) MyDerived
AnotherType anObject = new AnotherType();
WriteMessage(abObject);                 //WriteMessage<T>(T) AnotherType
WriteMessage((IMessageWriter)anObject); //IMessageWriter AnotherType

MyDerivedに厳密に一致するのはジェネリックメソッド。 親クラスであるMyBaseには暗黙的型変換が必要なため優先度が下がる。 明示的な変換を行えば変換後のものが厳密に一致となる。

static void WriteMessage<T>(T obj)コメントアウトすると WriteMessage(d);でエラーになる

次のメソッドまたはプロパティ間で呼び出しが不適切です: 'Program.WriteMessage(MyBase)' と'Program.WriteMessage(IMessageWriter)'

親クラスの方が優先順位高いはずだけど…わからん。

ジェネリックメソッド作成時の注意点

  • 次の理由から、型のチェックは実行時に行うのではなく、コンパイルに処理させた方が良い
    • チェックする条件が少ない間は良いが、増えてくるとコードが煩雑になる
    • 実行時にオーバーヘッドがかかる
  • 実行時の判断が明らかに適切な場合に採用すべき
    • 採用する際は、問題が起こらないようなライブラリを作成できるかパフォーマンスも含めて検討する。
  • 特定の型/インターフェイスに対するジェネリックメソッドを作成する場合、その型ならびに派生クラスすべて/そのインターフェイスを実装するすべての型に対するメソッドを用意する

EFFECTIVE C# 6.0/7.0 読書メモ 項目23

項目23 型パラメータにおけるメソッドの制約をデリゲートとして定義する

たいていの場合、制約としてクラス制約やインターフェイス制約を指定する方法が適している。.NET BCLでもIComparable<T>などが実装されていることを期待する機能が多数ある。

しかし、独自の制約を作成する場合は、インターフェイスとして定義するより、デリゲート型を定義するほうが手間を省くことができる。

インターフェイスで制限する場合

ジェネリッククラスの作成者はインターフェイスを用意、実装する。ジェネリッククラスの使用者はインターフェイスを実装するクラスを作成する。

//Addメソッドを持つインターフェイス
public interface IAdd<T>
{
    T Add(T obj);
}
//型TにAdd()メソッドを必要とするジェネリッククラス
public static class Example<T> where T : IAdd<T>
{
    public static T Add(T left, T right) => left.Add(right);
}
//IAddを実装しているクラス
public class SumAdd : IAdd<SumAdd>
{
    public int Value { get; set; }
    public SumAdd(int value) => this.Value = value;
    public SumAdd Add(SumAdd obj) => new SumAdd(obj.Value + this.Value);
}
var a = new SumAdd(6);
var b = new SumAdd(7);
var sum = Example<SumAdd>.Add(a, b);

デリゲートを定義する場合

ジェネリッククラスの作成者は ジェネリッククラスで呼び出したいメソッドに一致するシグネチャを持ったデリゲートを定義する。ジェネリッククラスの使用者は使用時にメソッドを定義する。

//必要なシグネチャを持ったデリゲートを定義
public static class Example
{
    public static T Add<T>(T left, T right, Func<T, T, T> AddFunc) => AddFunc(left, right);
}
int a = 6;
int b = 7;
//使用時にメソッドを定義
int sum = Example.Add(a, b, (x, y) => x + y);

デリゲートとして登録されたメソッドを複数個所で呼び出すような場合

クラスのインスタンスを生成する際に、クラスのメンバをジェネリック型のデリゲートとして登録する。

public class InputCollection<T>
{
    //略
    privaete readonly CreateFromStream<T> readFunc;
    public InputCollection(Create FromStream<T> readFunc) => this.readFunc = readFunc;
    public void ReadFromStream(TextReader reader) => thingsRead.Add(readFunc(reader));
    //略
}