SORA.GetOutput()

備忘録と捌け口とシェアと何か。

rails generateに失敗した時、「無かったこと」にする

rails generateの動作

generateコマンド自体が失敗したり、generateした後にもっといい名前を思いついてやり直したくなったり、そんな時の戻し方。
基本的に、generateコマンドを実行して作成されるファイルは一つだけじゃない。routesファイル等既存のファイルの上書きもあるので、手動でgenerateをなかったコトにするのはけっこう大変だったりする。
例えばコントローラを作ったけど消したくなった時、生成されたコントローラを削除してハイ終わり、というようには出来ない。

だけどそこは天下のRuby on Rails、スマートな解決策がある。

作る

  $ rails generate controller HogeController hoge

無かったことにする

  $ rails destroy controller HogeController hoge

destroyコマンドを使うだけ。うーん簡単。

POH7 水着問題の解答例

Paizaの通常問題は外部で回答を公開することが禁止されていますが、POHはその限りではないそうです。
応募期間が終了したので、自分の提出したコードと考え方を貼ってみます。使用言語はC#

※もちろんこれがベストな解法か全く自信はありません。
 どなたかこれよりイカす解き方した人がいたら、是非コメント下さい。
 特に、後ろのゼロを省くには10作らないように工夫するよりも、
 愚直に計算するたびに10で割ったほうが良かった気がします。

問題文 - POH7水着(PaizaランクA相当)

f:id:n-_-n:20160115001529p:plain

問題の要点

「ある数Nを与えます。N!を求めて、その下位9桁を出力して下さい。ただし右側の0は除きます。」という一見掛け算するだけで終わりそうな簡単な問題。…に見せかけて、正攻法で計算すると変数がオーバーフローする。

POH7のBランク相当問題は2問とも「解けるけど面倒くさい」といった感じだったが、この問題はシンプルさの中にトラップが含まれている良問&難問。

愚直に掛けていくとどうなるか

とりあえずこれを見て欲しい。
1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
11!=39916800
12!=479001600
------★ C# int型(32bit)が表すことのできる最大値 2147483647★---------------------------
------★ C# uint型(符号なし32bit)が表すことのできる最大値 4294967295★------------------
13!=6227020800
14!=87178291200
15!=1307674368000
16!=20922789888000
17!=355687428096000
18!=6402373705728000
19!=121645100408832000
20!=2432902008176640000
------★ C# long型(64bit)が表すことのできる最大値 9223372036854775807★-----------------
------★ C# long型(64bit)が表すことのできる最大値 18446744073709551615★----------------
21!=51090942171709440000
22!=1124000727777607680000
23!=25852016738884976640000
24!=620448401733239439360000
25!=15511210043330985984000000
26!=403291461126605635584000000
27!=10888869450418352160768000000
------★ C# decimal型(128bit)が表すことのできる最大値 79228162514264337593543950335★---
28!=304888344611713860501504000000
29!=8841761993739701954543616000000
30!=265252859812191058636308480000000

出展:階乗の一覧 1~100 | 計算の部屋

はい、たかだか28!を計算しただけでもうC#の変数が表すことのできる最大数を超えてしまう。
求める階乗Nが 1 ≦ N ≦ 1000000 となっていることを考えると、とても耐えられない。

考え方

問題文に出てくる

  • 求める数字は9桁だけで良い
  • 後ろのゼロを取っ払う

という条件は、解法のヒントにもなっている。この2つを駆使しながら階乗の計算をすることで、限られた桁数の中で変数のオーバーフローを防ぎながら計算を続けることができる。

求める数字は9桁だけで良い

左側を削って9桁以下にするというのがひとつ目のヒント。掛け算するたびに1000000000で割った余りを求め、その値を次の計算に使用することでオーバーフローを防ぐことができる。
もう少し般化して説明すると、「ある数の左側を削ってK桁にする」というのは、ある数を10^Kで割った余りを求めればOK。
例えば、12345という5桁の数字の左側を削って3桁にすると345となるが、これは10^3 = 1000で割った余り… 12345/1000 = 12あまり345 といった具合。

後ろのゼロを取っ払う

ふたつ目のヒントを使うと、右側を削って9桁を作った時に、後ろ9桁の右側からゼロが押し寄せてくる問題を回避する事ができる。これを達成するには後ろにつくゼロが何から成り立っているかを考えれば良い。

上記の階乗の計算結果リストで、末尾にゼロが増えるタイミングを良く観察してみよう。
一回目は5!のとき、二回目は10!のときだ。それぞれの階乗を丁寧に書きなおすと…

5! = 5 x 4 x 3 x 2 x 1
10! = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1

ふむ。5 x 2が一つ現れるたび、もしくは10が一つ現れるたびに後ろにゼロが増えるようだ。

三回目は15!のとき。 ここからが厄介な話になってくる。
15! = 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
まってくれ、5 x 210も新たに出現していないじゃないか、と一瞬思うかもしれないが、
この式はすべてが掛け算なので因数分解することができる。12= 2 x 2 x 315 = 5 x 3なので、
1215の因数になっている25が組み合わさって10を作っているというカラクリだ。 10の方も同じ理屈で、203010を(もっと言えば25を)因数に持つので末尾にゼロが増える。

よって、2と5の組み合わせを因数として発見した場合、それらを計算から省いてあげれば末尾に0が付くことはなくなる。

コード

というような考え方をコードに落とすとこんな感じになったデス。
コードでは、2と5は最初の計算ではぶき、最後にまとめて計算してます。
かなり丁寧目に書いたのでifブロックが結構行取ってる…

static void Main(string[] args)
{
    // Get N
    int N = int.Parse(Console.ReadLine().Trim());

    long result = 1;      // 結果出力用
    int count2 = 0, count5 = 0;  // 2と5の出現回数カウンタ
    readonly static int LIMIT = 1000000000; //後ろのゼロを削る用

    // メインルーチン
    bool partial = false;
    for (int i = 1; i <= N; i++)
    {
        // 因数に2か5が含まれている場合、カウンタを更新し、partialフラグを立てる。
        int div = 1;
        if (i % 2 == 0)
        {
            count2 += Count(i, 2);
            partial = true;
        }
        if (i % 5 == 0)
        {
            count5 += Count(i, 5);
            partial = true;
        }

        if(partial == true) 因数に25が含まれている場合、それらを除いた数にする。
        {
            div = CalcDiv(i);
        }

        // 掛け算。partialフラグが立っていれば2と5を覗いた数を掛ける。それ以外ならiを直接掛ける。
        result = partial ? result*div : result*i ;
        result = result % LIMIT; // 一回計算するたびに、ガッツリ0を削る。

        partial = false; // 次のループのためにリセット
    }

    // メインルーチンでスキップした2と5の掛け算
    // 2と5の組み合わせを作り、余った2を全て掛ける
    // 5は余らない(5が1回出現するまでに必ず2回以上2が出現するので、5が余ることは絶対にない)
    for (int i = 0; i < (count2 - count5); i++)
    {
        result *= 2;
        result = result % LIMIT;  // 一回計算するたびに、ガッツリ0を削る。
    }

    Console.WriteLine(result);
    // var debugInput = Console.ReadLine().Trim(); // for debug
}

private static int CalcDiv(int i)
{
    while(i % 2 == 0)
    {
        i /= 2;
    }
    while(i % 5 == 0)
    {
        i /= 5;
    }
    return i;
}

private static int Count(int i, int target)
{
    int counter = 0;
    while (i % target == 0)
    {
        counter++;
        i /= target;
    }
    return counter;
}

一応、GitHubにもコード上げました。 github.com

あとがき

杏ちゃん可愛いよ杏ちゃん・・・

C# 配列の昇順・降順並び替え2種(Arrayを使う方法、LINQを使う方法)

Arrayの静的メソッドを使用

Array.Sortメソッドで配列を操作すると、破壊的変更となる。 → 元の配列を直接イジる。
Array.SortのアルゴリズムはQuickSort。計算時間は平均O(n log n)、ワーストO(n ^ 2)。

昇順の場合

int[] scores = new int[] {1,5,4,2,3};
Array.Sort(scores);
// {1,2,3,4,5} 
// scores = Array.Sort(scores);としなくても変更が掛かる。

降順の場合

int[] scores = new int[] {1,2,3,4,5};
Array.Sort(scores); //{1,2,3,4,5}
Array.Reverse(scores); // {5,4,3,2,1} SortしてからReverseを掛ける。共に破壊的変更。

LINQを使用

LINQで配列を操作すると、操作した結果の配列が返り値となる。→元の配列は直接イジらない。

昇順の場合

int[] scores = new int[] {1,5,4,2,3};
scores = scores.OrderBy(x => x).ToArray(); // {1,2,3,4,5} 
// scores = としないと元の配列は変更されない。

降順の場合

int[] scores = new int[] {1,5,4,2,3};
scores = scores.OrderByDescending(x => x).ToArray(); // {1,2,3,4,5} 
// scores = としないと元の配列は変更されない。

C# 参照型の変数は、値渡しと参照渡し(ref)でどのように違いが出るか

値型、参照型、ref、out

TOACHさんの記事で、値型と参照型それぞれの場合について refとoutの使い分けがわかりやすく書かれています。

C++から移ってきたアナタへ。C#のref, outの使い方について。
toach.click

記事では、

呼び出し元のオブジェクトを書き換える場合、参照型は修飾子なしでもrefでも同じ動作になる

とあります。「じゃあ呼び出し元のオブジェクトを書き換える場合以外」ってどんなパターンなの?というのを検証してみました。

参照型変数の値渡しと参照渡しで結果が同じなるパターン

渡した先での操作対象が参照の指し示す先の実体の場合、
値渡し・参照渡しで違いはありません。
※コード引用させていただきました。

public static void Main(string[] args)
{
    // For reference type object.
    var referenceTargets = new List<string> { "a", "b", "c" };
    const string separator = ", ";

    // [修飾子なしバージョン] アウトプットは a, b, c, No ref and out. (書き換わる)
    AddText(referenceTargets);
    Console.WriteLine(
        "referenceTarget : " +
        string.Join(separator, referenceTargets.Select(target => target.ToString())));

    // [refバージョン] アウトプットは a, b, c, No ref and out., ref (書き換わる)
    AddText(ref referenceTargets);
    Console.WriteLine(
        "referenceTarget : " +
        string.Join(separator, referenceTargets.Select(target => target.ToString())));
}

private static void AddText(List<string> targets)
{
    targets.Add("No ref and out.");
}

private static void AddText(ref List<string> targets)
{
    targets.Add("ref");
}

参照型変数の値渡しと参照渡しで結果が変化するパターン

渡した先での操作対象が参照情報そのものの場合、
値渡し・参照渡し(ref付きの有無)で挙動が変化します。
※コード引用させていただきました。
※一つ目とのコードの違いは、通常バージョンとrefバージョンのaddTextメソッド内に
targets = new List<string> { "e", "f", "g" };を追加しただけです。

public static void Main(string[] args)
{
    // For reference type object.
    var referenceTargets = new List<string> { "a", "b", "c" };
    const string separator = ", ";

    // [修飾子なしバージョン] アウトプットは a, b, c (書き換わらない)
    AddText(referenceTargets);
    Console.WriteLine(
        "referenceTarget : " +
        string.Join(separator, referenceTargets.Select(target => target.ToString())));

    // [refバージョン] アウトプットは e, f, g, ref (書き換わる)
    AddText(ref referenceTargets);
    Console.WriteLine(
        "referenceTarget : " +
        string.Join(separator, referenceTargets.Select(target => target.ToString())));
}

private static void AddText(List<string> targets)
{
    targets = new List<string> { "e", "f", "g" };
    targets.Add("No ref and out.");
}

private static void AddText(ref List<string> targets)
{
    targets = new List<string> { "e", "f", "g" };
    targets.Add("ref");
}

なにがちがうの?

参照型を値渡しした場合、参照の関係はこのようになっています。

(Mainメソッド内)
referenceTargeds -> (referenceTargetsの実体)
(Addメソッド内)
targets -> (referenceTargetsの実体)
★この状態でtargets = new List<string>()すると、targetsの参照先のみが新しく作ったリストに変更される。

一方、参照型を参照渡しした場合、参照の関係はこうです。

※少しわかりにくいですが、参照型を参照渡しをした場合には、渡し元の参照への参照が渡されます。

(Mainメソッド内)
referenceTargeds -> (referenceTargetsの実体)
(Addメソッド内)
targets -> referenceTargets -> (referenceTargetsの実体)
★この状態でtargets = new List<string>()すると、targetsの参照先のreferenceTargetsの参照先が新しく作ったリストに変更される。

結論

ref怖い!!

C#/Linq ワンライナーでstring配列をint配列に変換、int配列をstring配列に変換

Paizaのハッカソンで、stringとして渡されるスペース区切りの数字を
なんやかんやしたいパターンが多かったので備忘録。

結論から言うとLinq最強説です。

※以下コードの使用にはusing System.Linq;が必要です。

string配列をint配列に変換

まずは通常パターン

intArray = stringArray.Select(x => int.Parse(x)).ToArray();

応用で、スペース区切りのConsole入力から直接int配列をつくるパターン。

intArray = Console.ReadLine().Trim().Split(' ').Select(x => int.Parse(x)).ToArray();

int配列をstring配列に変換

stringArray = intArr.Select(x => x.ToString()).ToArray();

ちなみに、Linqメソッドを使わない場合はArray.ConvertAllをつかっても似たようなことができる。