trsing’s diary

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

diverta 2019 Programming Contest参加メモ

企業主催?よくわからんが参加だ。数をこなせウィッヒー! 配点的にABとCかDクリアを目標で。

atcoder.jp

結果

A,B,C問題はAC。D問題は提出にもいたらず。E以降は問題文すら見れてねえ。

C:AB Substrings

連結してABができるか。変に被ったりしないので文中にあるABのほか、頭としっぽに注目すればよいことにはすぐ気づいた。 すると

  1. 頭がB、しっぽがAの文字列
  2. 頭がB、しっぽがA以外の文字列
  3. 頭がB以外、しっぽがAの文字列

の場合でちょいと調整が必要であることがわかるから簡単な例を並べて調整方法を見つければよい。

追記
1.を全部くっつける。2.、3.から1個ずつ持ってきて1.にくっつける。残りの2.、3.をくっつける。みたいな感じ。

D:DivRem Number

最大10^{12}だから全探索じゃとても間に合わないよねえということで高速化が必要。で止まった。 modなんでとりあえずN=km+lと置いてみりゃ解説の方法思いついたかも。約数求める高速なアルゴリズム思いつかないから結局無理だったかな。いやググればすぐ出てくるからいけるか。

追記
N=km+lとして計算したらいいだけみたいだ。

N=km+l,\,l<mとおく。

\displaystyle{
\lfloor \frac{N}{m} \rfloor=\lfloor \frac{km+l}{m}\rfloor=k,\\
N\mod m = (km+l)\mod m=l
}

\lfloor \frac{N}{m} \rfloor=N\mod mより k=l
\displaystyle{
N=km+k=k(m+1)>k^{2}\\
\sqrt{N}>k
}

[1,\sqrt{N})でkを探索、mを算出すればよい。 \sqrt{N}10^{6}なので間に合う。ACできた。

所感

B問題を読み間違えて無駄に時間使っちゃった。問題文は落ち着いてちゃんと読もう。 約数を高速に求める方法とか定石的なものは一通り見ておこう。

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

項目22 ジェネリックの共変性と反変性をサポートする

独自にインターフェイスやデリゲートを作成する場合、できる限り反変性inあるいは共変性outを設定する。

共変性と反変性をサポートするメリット

作成したインターフェイスやデリゲートの変性*1が誤用されたとしても、コンパイラが検出してくれる。

ジェネリック型C<T>における共変性と反変性

型Xが型Yに変換できる(Y:基底、X:派生)ことがわかっている場合

共変性

C<X>をC<Y>に変換できる(C<Y>←C<X>)

反変性

C<Y>をC<X>に変換できる(C<X>←C<Y>)

配列の共変性にある問題

基底クラスの配列に派生クラスの配列を割り当てることができるが、その要素に別の派生クラスを入れようとすると実行時エラーになる。

static void Main(string[] args)
{
    var planets = new CelestialBody[] { new Planet { Name = "mar", Mass = 1000 } };
    CoVariantArray(planets);
    UnsafeVariantArray(planets);
    CelestialBody[] spaceJunk = new Moon[2] { new Moon(), new Moon { Name="ast",Mass=10000} };
    UnsafeVariantArray(spaceJunk);//System.ArrayTypeMismatchException: '配列と互換性のない型の要素にアクセスしようとしました'
    spaceJunk[0] = new Planet();//System.ArrayTypeMismatchException: '配列と互換性のない型の要素にアクセスしようとしました'
}
abstract public class CelestialBody  :IComparable<CelestialBody>
{
    public double Mass { get; set; }
    public string Name { get; set; }
    public int CompareTo(CelestialBody other)
    { throw new NotImplementedException();  }
}
public class Planet : CelestialBody { }
public class Moon : CelestialBody { }
public class Asteroid : CelestialBody { }
//これはタイプセーフ
public static void CoVariantArray(CelestialBody[] baseItems)
{
    foreach (var thing in baseItems)
        Console.WriteLine($"{thing.Name}の質量は{thing.Mass}Kgです");
}
//これはタイプセーフではない
public static void UnsafeVariantArray(CelestialBody[] baseItems)
{
    baseItems[0] = new Asteroid { Name = "Hygiea", Mass = 8.85e19 };
}

※基底クラスの配列の要素に派生クラスの配列を入れるのはエラー出ない。

    CelestialBody[] spaceJunk = new CelestialBody[2] { new Moon(), new Moon { Name="ast",Mass=10000} };
    spaceJunk[0] = new Planet();

C#における共変性、反変性

共変性:out修飾子がつく
出力位置((限定された場所のこと。関数の戻り値、プロパティのgetアクセサ、デリゲートのシグネチャの一部))にある型がTに制限されるようコンパイラに強制させることができる。

反変性:in修飾子がつく
Tが入力位置にのみ表れるようコンパイラに強制させることができる。

デリゲートでは共変性と反変性が逆転してしまうことがあることに注意

DerivedクラスをBaseクラスからの派生とした場合、

ICovariantDelegate<out T>に対して*2

ICovariantDelegate<Base> ib = new CovariantDelegate<Derived>();
  • Func<T> GetAnItemLater();

使用者:返り値がFunc<Base>であり、このデリゲートを使用すると、Baseが返ってくると期待する。
実際:Func<Derived>が返り値で、このデリゲートを使用するとDerivedが返ってくる。しかしBaseに変換できるので問題なし。

Func<Base> fb = ib.GetAnItemLater();
Base b = fb();
> fb.GetType()
[System.Func`1[Submission#0+Derived]]
> b.GetType()
[Submission#0+Derived]
  • void GiveAnItemLater(Action<T> WhatToDo);

使用者:Action<Base>を設定する。
実際:GiveAnItemLaterは引数がAction<Derived>と考えているのでAction<Base>Derivedを入れる。しかしBaseに変換できるので問題なし。

> ib.GiveAnItemLater((Base b) => { Console.WriteLine(b.GetType().Name); })
Derived

IContravariantDelegate<in T>に対して

IContravariantDelegate<Derived> id = new ContravariantDelegate<Base>();
  • void GetAnItemLater(Func<T> item);

使用者:Func<Derived>を設定する。
実際:GetAnItemLaterFuncからの返り値がBaseであるとして処理をする。Derivedが返ってくるがBaseに変換できるので問題なし

> id.GetAnItemLater(() =>  new Derived() );
Derived
  • Action<T> ActOnAnItemLater();

使用者:返り値がAction<Derived>であることを期待し、このデリゲートにDerivedを入れる。
実際:Action<Base>が返り値で、このデリゲートにDerivedを入れる。しかしBaseに変換できるので問題なし。

> Action<Derived> ad = id.ActOnAnItemLater();
> ad.GetType()
[System.Action`1[Submission#0+Base]]
> ad(new Derived());
Derived

結局どういうことなの

派生クラスは基底クラスに変換できるということ。

  • 引数として基底クラスを期待してるメソッドには派生クラスを入れることができる。

Action<Derived>Action<Base>を代入(反変性)。 ab(new Derived())が可能であるからadに代入しても問題ない。

> Action<Base> ab = (target) => Console.WriteLine(target.GetType().Name);
> Action<Derived> ad = ab;
> ad(new Derived());
Derived

Action<Derived>の引数は中身がAction<Base>でもDerivedじゃないとだめ。

> ad(new Base());
(1,4): error CS1503: 引数 1: は 'Base' から 'Derived' へ変換することはできません。
  • 返り値として基底クラスを期待している型には派生クラスを返すことができる。

Func<Base>Func<Derived>を代入(共変性)。

> Func<Derived> fd = () => new Derived();
> Func<Base> fb = fd;
> Base br = fb();
> br.GetType().Name

返り値はBase(に変換されたDerived)なのでDerivedで受けるには型変換が必要。

> Derived dr = fb();
(1,14): error CS0266: 型 'Base''Derived' に暗黙的に変換できません。明示的な変換が存在します (キャストが不足していないかどうかを確認してください)
Derived dr = (Derived)fb();

デリゲートでの逆転のとこコード

 public class Base { public Base() { } }
 public class Derived : Base { public Derived() { } }
 public interface ICovariantDelegate<out T>
 {
     T GetItem();
     Func<T> GetAnItemLater();
     void GiveAnItemLater(Action<T> whatToDo);
 }
 public class CovariantDelegate<T>  : ICovariantDelegate<T> where T:new()
 {
     public T GetItem() { return new T(); }
     public Func<T> GetAnItemLater() { return () => new T(); }
     public void GiveAnItemLater(Action<T> whatToDo) { whatToDo(new T()); }
 }
ICovariantDelegate<Base> ib = new CovariantDelegate<Derived>();
Func<Base> fb = ib.GetAnItemLater();
Base b = fb();
> fb.GetType()
[System.Func`1[Submission#0+Derived]]
> b.GetType()
[Submission#0+Derived]
> ib.GiveAnItemLater((Base b) => { Console.WriteLine(b.GetType().Name); })
Derived

public interface IContravariantDelegate<in T>
{
    void ActOnAnItem(T item);
    void GetAnItemLater(Func<T> item);
    Action<T> ActOnAnItemLater();
}
public class ContravariantDelegate<T> : IContravariantDelegate<T> where T : new()
{
    public void ActOnAnItem(T item) { }
    public void GetAnItemLater(Func<T> item) { var t = item(); Console.WriteLine(t.GetType().Name); }
    public Action<T> ActOnAnItemLater() { return (T t) => { Console.WriteLine(t.GetType().Name); }; }
}
IContravariantDelegate<Derived> id = new ContravariantDelegate<Base>();
> id.GetAnItemLater(() =>  new Derived() );
Derived
> Action<Derived> ad = id.ActOnAnItemLater();
> ad.GetType()
[System.Action`1[Submission#0+Base]]
> ad(new Derived());
Derived

参考とか

ufcpp.net

docs.microsoft.com

*1:文中やMSDNでは分散とあるけどたぶん変性

*2:コードは後述。CovariantDelegateはICovariantDelegateを実装したクラス

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

項目21 破棄可能な型引数をサポートするようにジェネリック型を作成すること

型引数がIDisposableを実装している場合にも対応するようにジェネリック型を設計すること。

例1:メソッド内で型引数のインスタンスを作成して使用するようなジェネリックメソッドがある場合

   public void GetThingsDone()
    {
        T driver = new T();
        driver.DoWork();
    }

TがIDisposableを実装する場合、リソースリークが起こる。

例1の解決策

TがIDisposableを実装しているか確認し、実装している場合は適切に破棄する。 usingステートメントに入れるとよい。

   public void GetThingsDone()
    {
        T driver = new T();
        using (driver as IDisposable)
        {
            driver.DoWork();
        }
    }

TがIDisposableを実装していればDispose()が呼び出される。実装していない場合呼び出されない。

例2:型引数のインスタンスをメンバ変数として使用する場合

IDisposableを実装しているかもしれない型への参照を保持することになる。

例2の解決策

ジェネリック型においてもIDisposableを実装する。型引数にIDisposableが実装されているかどうかを確認し、実装されている場合には破棄するように実装する。

注意点
  • sealedクラスとしないなら、派生クラスにおいてもDispose()メソッドが呼び出せるようにIDisposableパターンを実装する
  • 複数回Dispose()を呼べるようになっていること

その他解決策

Dispose()を呼び出す責任をジェネリッククラスの外に任せ、オブジェクトの所有権をジェネリッククラスの外に委ねる。

   private T driver;
    public EngineDriver(T driver)
    {
        this.driver = driver;
    }

例1の解決策のIL

詳しくは本文のusingステートメントの動作に関する説明参照

    // Methods
    .method public hidebysig 
        instance void GetThingsDone () cil managed 
    {
        // Method begins at RVA 0x205c
        // Code size 44 (0x2c)
        .maxstack 1
        .locals init (
            [0] !T,
            [1] class [mscorlib]System.IDisposable
        )

        IL_0000: call !!0 [mscorlib]System.Activator::CreateInstance<!T>()
        IL_0005: stloc.0
        IL_0006: ldloc.0
        IL_0007: box !T
        IL_000c: isinst [mscorlib]System.IDisposable//オブジェクト参照が特定のクラスか。結果はスタックにプッシュされる
        IL_0011: stloc.1//スタックからをローカル変数1に値(isinstの結果)を取り出す
        .try
        {
            IL_0012: ldloca.s 0
            IL_0014: constrained. !T
            IL_001a: callvirt instance void C/IEngine::DoWork()
            IL_001f: leave.s IL_002b
        } // end .try
        finally
        {
            // sequence point: hidden
            IL_0021: ldloc.1//スタックにローカル変数1の値(isinstの結果)を置く
            IL_0022: brfalse.s IL_002a//スタックの値が0ならIL_002aに分岐

            IL_0024: ldloc.1
            IL_0025: callvirt instance void [mscorlib]System.IDisposable::Dispose()

            // sequence point: hidden
            IL_002a: endfinally
        } // end handler

        IL_002b: ret
    } // end of method EngineDriverOne`1::GetThingsDone

次サイトでIL確認

sharplab.io

命令文の意味とか

docs.microsoft.com

www5b.biglobe.ne.jp

AtCoder Beginner Contest 125、AtCoder Grand Contest 033参加メモ

AtCoder Beginner Contest 125

初心者用ということでとりあえず参加

atcoder.jp

結果

A,B,D問題はAC(Accepted:正解)。CはTLE(Time Limit Exceeded:プログラムが規定時間内に回答できなかった)。

C:GCD on Blackboard

高速化の方法思いつかなかったのでACできず。
解説見たときは「こんなの思い浮かばねーよ!」と思ったけど、答えは出せてる場合、解説のポイント

「正数A_{i}を書き換える」行為は「整数A_{i}を消す操作」と等価
gcdには「どこから計算しても結果は変わらない性質」があります

がわかっているわけだからここから計算途中のものを流用していくという考えが出てくるのは自然なんだよなあ。勿体ないことした。

D:Flipping Signs

操作で何ができるかというと符号-を任意の場所に移動することができる、と考えればあとは楽ちん。負の数が偶数なら全部正、奇数なら1つだけ負。

解説読んで、C問題を安定してとくには動的計画法触っといた方がいいんだろうなーと思った。

AtCoder Grand Contest 033

ABCでつまづいてる初心者が出ても無駄な涙が流れるだけじゃない?と思ったけどまあいいや目標1問、ワンチャン2問くらいの気持ちで。

atcoder.jp

結果

AはAC。BはWA(Wrong Answer:不正解)。C以降はBにかかりっきりで問題すら見てねえ…。

A問題

(幅優先探索だ…!)と考えればそれで。迷路の探索問題見たことあればカカッと思いつくんじゃないかな。

B問題

先手後手の最適な行動の結果は何よ、と考えると
先手:最短手でマス目外
後手:最後までマス目内
先手の最適な行動を考えるのはいかにもめんどくさい。後手は1つしかない上明確なので楽。となるとマス目内に残る条件を逆算してく方法を思いつくのは難しくなかったはず。

前から考えてて結局時間切れでしたが…。

所感

まずは緑色目指してガンバロー!オー!

AtCoder始めました

経緯

転職したいけど面接とかクソ苦手だ…。技術力評価的なあれやそれで下駄はかせてくれる都合良いののないかな…。下駄どころか地面にめり込む可能性あるけど…。

スキルチェック的なものあんのか。Paizaってのええやん。

あかん…。スキルチェック問題間違えたけど解説も解答もあらへん。もやもやする…*1

競プロってのが似た系統の問題だすみたいやな。日本やとAtCoderてのに聞き覚えあるで。解説あるし他の人のコードも見れんのか。ええやん。前から興味あったしやってみよ*2

atcoder.jp

所感

わーいたーのしー

ひとのこーどみれるおもしろーい

プログラムはやりたいけど別に作りたいソフトとかねーからなあ…。という人は一回手を出してみるとよいと思う。

とはいえ一般的なソフト作成で求められるスキルと同じ、というわけではないなのでそこら辺は注意か。

*1:TLE食らった

*2:手段が目的に入れ替わった

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

項目20 IComparableとIComparerにより順序関係を実装する

IComparable<T>IComparer<T>は順序関係を定義するインターフェイス。コレクションのソート、検索するために順序関係を定義する必要がある。

例えば'List.Sort()'では'T.CompareTo(T)'を使用する。

IComparable<T>

自然な順序を定義する。メソッドはCompareTo(T)

IComparable<T>を実装するときはIComparableも実装すること。IComparable<T>よりも古いインターフェイスであるIComparableを実装する理由は
後方互換
・BCLでは1.0当時の実装との互換性が要求される

IComparableのメソッドはCompareTo(object)。object型の引数を取るため、あらゆるものを指定でき間違ったコードを記述できる。一部の引数(値型?)においてはボックス化とボックス化解除が発生し、コストがかかる。

次のように明示的に実装すると、IComparableインターフェイスの参照を経由しなければ呼び出すことができなくなり、間違って使用するのを防ぐことができる。

public struct Customer : IComparable<Customer>, IComparable
{
    private readonly string name;
    private double revenue;
    //略
    public int CompareTo(Customer other) => name.CompareTo(other.name);
    int IComparable.CompareTo(object obj)
    {
        if (!(obj is Customer))
            throw new ArgumentException("引数はCustomer型ではありません", "obj");
        Customer otherCustomer = (Customer)obj;
        return this.CompareTo(otherCustomer);
    }
    //略
}
Customer c1;
Employee e1;
if( c1.CompareTo(e1)>0 )//シグネチャが一致しないのでコンパイルエラー
{}
if( ((IComparable)c1).CompareTo(e1)>0 )//明示的な呼び出し。コンパイルエラーにならない
{}
関係演算子(<.<=,>,>=)をオーバーロード

CompareTo(T)メソッドを使用するとよい。インターフェイスを定義することによる実行時の性能低下を回避しつつ、型に固有の比較処理を実行できるようになる。

    public static bool operator <(Customer left, Customer right) => left.CompareTo(right) < 0;

IComparer

例ではCustomerに対して、通常の順序(CompareTo)としてnameを使用した。 別の基準(revenue)で順序を付けたい場合はIComparer<T>を使用する。 IComparable<T>型を処理するメソッドには、IComparer<T>インターフェイス経由でオブジェクトを並び替えるようなオーバーロードが用意されている。 例えば List<T>.Sort(IComparer<T>);。他、SortedListなど。

Customer構造体の内部クラスとして新しいクラス(RevenueComarer)を定義するとよい。

    private static Lazy<RevenueComparer> revComp = new Lazy<RevenueComparer>(() => new RevenueComparer());
    public static IComparer<Customer> RevenueCompare => revComp.Value;
    private class RevenueComparer : IComparer<Customer>
    {
        int IComparer<Customer>.Compare(Customer left, Customer right) => left.revenue.CompareTo(right.revenue);
    }

(なぜ遅延で作ってるのだろう…)

Comparison

同じ型の 2 つのオブジェクトを比較するメソッド。
public delegate int Comparison<in T>(T x, T y);

ジェネリックが導入された後から追加されたほとんどのAPIでは、別のソートを実行できるようにComparison<T>を受け取るようになっている。例えばList<T>.Sort(Comparison<T>);

statcプロパティをCustomer型に用意すればよい。 所得額(revenue)で比較する場合、

    public static Comparison<Customer> CompareByRevenue => (left, right) => left.revenue.CompareTo(right.revenue);
注意点

順序関係と同値性はそれぞれ異なる処理。CompareTo()が0を返してもEquals()がfalseを返すことがあり、これは問題のない挙動。

使用例
> var cstl = new List<Customer>() { 
    new Customer("d", 100), 
    new Customer("f", 500),
    new Customer("a", 300), 
    new Customer("g", 400) };
> foreach(var cst in cstl) 
  { Console.WriteLine(cst.Name + "," + cst.Revenue); }
d,100
f,500
a,300
g,400
> cstl.Sort()//デフォではCompareToが使用される
> foreach (var cst in cstl) 
  { Console.WriteLine(cst.Name + "," + cst.Revenue); }
a,300
d,100
f,500
g,400
> cstl.Sort(Customer.CompareByRevenue);//Comparison<T>を使用してSort
> foreach (var cst in cstl)
  { Console.WriteLine(cst.Name + "," + cst.Revenue); }
d,100
a,300
g,400
f,500
> cstl.Sort()
> foreach (var cst in cstl) { Console.WriteLine(cst.Name + "," + cst.Revenue); }
a,300
d,100
f,500
g,400
> cstl.Sort(Customer.RevenueCompare);//IComparer<T>を使用してSort
> foreach (var cst in cstl) { Console.WriteLine(cst.Name + "," + cst.Revenue); }
d,100
a,300
g,400
f,500

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

項目19 実行時の型チェックを使用してジェネリックアルゴリズムを特化する

実行時の引数の型に応じ、その型が持つ機能に適したアルゴリズムを使用するようにする。

型引数が適切な機能を備えている場合、より効率的なアルゴリズムを効率的に実装できる。

ジェネリック型のインスタンスは、実行時の型ではなく、コンパイル時におけるオブジェクトの型をもとにして生成されることに注意。

例)一連の要素を逆順にして返すことができるようなクラス

IEnumerable<T>の機能のみ使用した場合

public sealed class ReverseEnumerable<T> : IEnumerable<T>
{
    //省略
    IEnumerable<T> sourceSequence;
    IList<T> originalSequence;
    public ReverseEnumerable(IEnumerable<T> sequence)
    {
        sourceSequence = sequence;
    }
    public IEnumerator<T> GetEnumerator()
    {
        if(originalSequence == null)
        {
            originalSequence = new List<T>();
            foreach(T item in sourceSequence)
                originalSequence.Add(item);
        }
        return new ReverseEnumerator(originalSequence);
    }
    //省略
}

IEnumerable<T>はランダムアクセスをサポートしてない。逆順に操作するために、ランダムアクセス可能な型(List<T>)を作成している。

IListの機能を使用する場合
   public ReverseEnumerable(IEnumerable<T> sequence)
    {
        sourceSequence = sequence;
        originalSequence = sequence as IList<T>;
    }

入力sequenceIList<T>をサポートしている場合、ランダムアクセス可能なためList<T>の作成は不要。上記のように修正すれば、IList<T>をサポートしている場合はoriginalSequenceがnullではなくなるのでif(originalSequence == null)のブロックが実行されない。

他、ICollectionを実装しているなら.Countを利用してして宣言時に必要なメモリを確保(new List<T>(source.Count))して効率をよくする、など。