新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。もう新人じゃないかも…

学習記録:C#、プログラミングコンテスト攻略ガイド

[学習記録] C#

内容

.NET Framework
  • Visual Studioにおける用語
      • ソリューション:複数プロジェクトをまとめたもの
      • プロジェクト:関連する複数プロジェクトをグループとして管理
      • アセンブリ:だいたいソリューション単位を表す
  • よく使うショートカットキー
Ctrl + Shift + N 新規プロジェクト
Ctrl + Shift + A 新しい項目の追加
Shift + Alt + C クラスの追加
Ctrl + Tab タブの移動
Ctrl + - 前に戻る
Ctrl + Shift + - 次へ進む
Ctrl + . (クラス名にカーソルがあるとき)usingの追加
ctrl + F5 デバッグ無しで実行
Ctrl + J インテリセンスの表示
Alt + Shift + ↑/↓ 矩形選択
Ctrl + E, C 選択範囲のコメント
Ctrl + E, U 選択範囲のコメントを解除
Ctrl + Shift + V クリップボードリングの切り替え
Ctrl + Shift + ↑/↓ 強調表示された参照
Ctrl + K, F 選択範囲のインデントをそろえる
Ctrl + K, X スニペットの挿入
F11 ステップイン:呼び出したメソッド内についても1文ずつ実行(呼び出し先に遷移)
F10 ステップオーバー:メソッド呼び出しについてはまとめて実行(遷移しない)
Shift + F11 ステップアウト:現在実行中のメソッドを最後まで実行(呼び出し元に遷移)
C#Javaとの違い)
  • データ型
    • 符号有り無しがある。符号なしはuを付ける(ulongなど)
      • ただしbyteのみは標準が符号なし、符号ありbyteはsbyte
    • C#における型には、System名前空間の型が対応づけられている。intはInt32に対応。
      • 複数言語に対応するため。言語には存在しない型も、System名前空間にあれば使用できる
      • ex) int(C#):Int32(System):Integer(VB)
      • ex) なし(C#):DateTime(System):Date(VB)
  • switch文
    • フォールスルー禁止
    • breakかgotoが必要、defaultでも必須なことに注意
switch(num) {
  case 1 :
    method();
    break;  // breakが無いとエラーになる
  case 2 :
  case 3 :
    // 複数ケースで同じことをやりたい場合は上記のようにする
    method();
    break;
  default:
    break;  // breakが無いとエラーになる
}
  • 型変換
    • 文字列への変換:ToString()、日付や金額などの書式設定が可能
    • 文字列からの変換:Parse()、TryParse()、Convert()など
int num = 10000;
Console.WriteLine(num.ToString("C")); // \10,000(通貨表示)

Console.WriteLine(num.ToString("#,0")); // 10,000(桁区切り記号)
string str = "10000";

// 変換に失敗するとFormatExceptionなどが発生
int num = int.Parse(str);

// 変換に失敗するとfalseが返る
bool flag = int.TryParse(str, out num);
  • 配列
    • 宣言時の[]はデータ型の直後に書く
    • 多次元配列は[ , ](Javaとは違い、配列の配列ではない)
int[] num = new int[5];

// 下はエラーになる
// int num[] = new int[5];

int[,] num2 = new int[4, 5];
  • foreach
    • Javaではfor文の特殊な書き方として実装されていたが、C#ではforeach構文が存在
foreach (var num in array)
{
  ...                
}
  • クラスの拡張
    • 基本クラスと派生クラス:いわゆるスーパークラスとサブクラス
    • base:Javaでいうsuper
    • :(コロン):extends
    • 基本クラスのコンストラクタの呼び出し:これも:(コロン)を使う。メソッド宣言のあとにコロンを付け、引数を書く
    • sealed:final(派生禁止)
    • virtual/override修飾子:オーバーライドするメソッドに必須の修飾子
    class A
    {
        public A()
        {
            Console.WriteLine("A");
        }

        virtual void print()
        {
            Console.WriteLine("print A");
        }
    }

    class B : A
    {
        public B() : base()
        {
            Console.WriteLine("B");
        }

        override void print()
        {
            Console.WriteLine("print B");
        }
    }
  • フィールド・プロパティ・コンストラクタメソッド
    • プロパティ:フィールドのようにアクセスできるが、読み書き時の処理を指定できる
    • internal修飾子:同一アセンブリ内からのみ参照可
    • protected修飾子:派生クラス内からのみ(Javaでは同じパッケージ内もしくは継承関係のあるサブクラスからのみ)
    class A
    {
        int num;
        public int Num {
            get
            {
                return num;
            }
            set 
            {
                if (num > 0)
                {
                    num = value;
                }
            }
        }
    }
  • 特殊な引数
    • ref/out:参照渡しするためのキーワード
    • 名前付き引数:呼び出し時に名前を指定することで、順番を入れ替えてもOK
    • 省略可能な引数:引数のデフォルト値を指定できる、デフォルト値のある引数は省略可
        static void hoge(ref int arg1, out int arg2)
        {
            // outの変数に値を設定する前に参照するとエラーになる
            // int n = arg2;
            arg1 = 5;
            arg2 = 10;
        }
        static void huga(int arg1, string arg2 = "huga") { }

        static void Main(string[] args)
        {
            // 通常のメソッド呼び出し
            huga(99, "string");

            // 名前を指定して順序を入れ替えることが可能
            huga(arg2: "huga", arg1: 99);

            // 2盤目の引数は省略可能
            huga(50);
        }
  • string
    • ==で比較可能
    • String.Empty:長さ0の文字列
    • Formatメソッド:文字列の書式指定が可能
  • 構造体
    • ほぼクラスと同じようなことができるが、確保される領域がスタック領域であることが異なる
    • 基本データ型も構造体で作られている
  • 例外
    • throws句がない(必ずcatchしなければいけない例外がないので)
    • catch句がなくてもOK(tryとfinallyのみでも可)
    • catch句の()内で例外クラスの変数名を省略可(catch句内で例外の持つ情報を使わない場合)
    • catchした例外の再スロー:throw;で良い
    • 例外をなるべく起こさないようにする、というのが基本方針
      • 業務フローでは例外をなるべく使わない。業務フローにおける例外は戻り値などで表現
  • その他
    • namespace:いわゆるpackage。ただし論理的なグルーピング(フォルダ階層でない)
    • using:いわゆるimport。*は不要で、using System; のように書く
    • Mainメソッド:mainメソッド
    • ビルド:コンパイルのこと。

[学習記録] プログラミングコンテスト攻略ガイド

内容

第5章:全探索
  • 数学的な問題を見た瞬間に数学的知識が必要だと思い込んでしまう
    • 数学的な知識で工夫はできるが、とても難しい問題を除けば大体全探索で解ける
    • まずは全てをしらみつぶしに探せば良いという発想を持つ
    • 「なるべく分岐を少なくする」のもミスを無くすテクニックの一つ
  • 全探索のパターン
    • 1)すべてのパターンを調べ、最も良い解を探す
    • 2)すべてのパターンを調べ、条件を満たすものが何通りあるか調べる
  • 問題1:楽しいパーティ
    • 問題概要
      • 人は2つの話題にのみ興味を持つ
      • 楽しいパーティとは、参加者全員が共通の話題を持つことである
      • 文字列配列firstとsecondがあり、i番目の友人が興味を持つ話題はfirst[i]とsecond[i]で与えられる
      • 友人をパーティに招くとき、楽しいパーティとなる場合に招ける最大の人数を求めよ
    • 解答
      • 話題を順々に選択し、何人がその話題に興味を持っているか数える
      • 一番多い数を返せばOK
      • 同じ話題を繰り返し数えないようにするとなお良い
      • 連想配列(String, intのMapなど)を使えばすっきりと書ける
      • 始めに全ての話題について初期化し、その後各話題first[i]とsecond[i]について連想配列のintの方を増やしていくだけ
  • 問題2:暗号化
    • 問題概要
      • int型の配列が与えられるので、その中の数字の一つを増加させ、変更後の配列内の数字の全ての積を最大化する
      • 最大化された積を求めよ
    • 解き方
      • まずは全探索。配列内の数字を1つずつ選択し、その値を1増やして積を求める>その中の最大値を返す
      • この問題では配列内で最小の数字を増やせば良いので、配列をソートして先頭の数字を増やせば良い
  • 問題3:おもしろい数字
    • 問題概要
      • int型のbaseが与えられるので、base進数でn(2〜base-1)の倍数が、各桁の合計もnの倍数となるようなnを全て求めよ
      • ex) 10進数では、3の倍数の数字(126)の各桁の合計(1+2+6=9)は3の倍数となる。9の倍数も同様なので{3, 9}が答え
      • とりあえず3桁の数字で上の性質が確かめられれば良いものとする
    • 自分の書いたプログラムは以下
static int[] RetNum(int baseNum) {
    var list = new List<int>();
    Boolean flag;
    for (int x = 2; x < baseNum; x++)
    {
        flag = true;

        for (int num100 = 1; num100 < baseNum; num100++)
        {
            for (int num10 = 1; num10 < baseNum; num10++)
            {
                for (int num1 = 1; num1 < baseNum; num1++)
                {
                    int num = num100 * baseNum * baseNum + num10 * baseNum + num1;
                    if (num % x == 0 && (num100 + num10 + num1) % x != 0)
                    {
                        flag = false;
                    }
                }
            }
        }
        if (flag)
        {
            list.Add(x);
        }
    }

    int[] array = list.ToArray();

    return array;
}
  • 解き方
    • nを決定
    • 各桁の数字をfor文で決定
    • 各桁の数字を繋いだ数がbaseで割り切れ、かつ各桁の和がbaseで割り切れなかった場合、このnは答えから除外してbreak
    • for文を全て抜けたnについて、配列に格納し、この配列を返す
    • 応用
      • 数学的に考えれば、答えは(base - 1)およびその約数
      • a * n^2 + b * n + cを変形して、a * (n - 1)^2 + (b - 2a) * (n-1) + (a + b + c)
      • (a + b + c)が(n - 1)の倍数なら、この式全体が(n - 1)の倍数になる
  • 問題4:回文
    • 問題概要
      • ある文字列sの後ろに0文字以上の文字列を追加し、回文を作る
      • 回文が最も短い場合の長さを返す
    • 解き方
      • 最長でも2n-1(nはsの長さ)文字で回文が作成できる(abc -> abcba)
      • とはいえ、2n-1文字以下の文字列や回文を全て考えるのは計算量が大きすぎる(計算量については後の章で解説)
      • ここで、「出来上がった回文の文字列」を考えるのではなく、「回文の文字列長」に注目する
      • 実際に回文を作る必要は無く、「この文字数で回文が作れるか」を考えて文字数を返せば良い
    • アルゴリズム
      • 1)まず文字列の長さiを決める(iはs.lengthから開始)
      • 2)文字列の各文字について、対称となる位置に文字が存在し、違う文字であればその文字数では回文は作れない
      • 3)回文を作れた場合の文字数を返す
    • 例:abcccc
      • 1)文字数 i = 6
      • 2)文字列の0文字目はa。対称となる位置はi - j - 1の5文字目であるc。a != cなので回文は作れない
      • 3)文字数 i = 7
      • 4)文字列の0文字目はa。対称となる位置は6文字目だが、これは存在しない(=aを付け加える)のでOK
      • 5)文字列の1文字目はb。対称となる位置は5文字目だが、これはcなので回文は作れない
      • 6)文字数 i = 8
      • 7)文字列の0文字目はa。対称となる位置は7文字目だが、これは存在しない(=aを付け加える)のでOK
      • 8)文字列の1文字目はb。対称となる位置は6文字目だが、これは存在しない(=bを付け加える)のでOK
      • 9)文字列の2文字目はc。対称となる位置は5文字目だが、これはcなのでOK
      • 10)文字列の3文字目はc。対称となる位置は4文字目だが、これはcなのでOK
      • 11)回文になったので処理終了。答えは8文字