ABC137
A
A + B, A - B, A * Bの最大値を計算する。
C#だと、以下のようにMath.Maxを入れ子にして記述することになるが、関数を定義していると便利。
// 3つの値の最大値を求める。 Math.Max(A+B, Math.Max(A-B, A*B)); // 次のような関数を定義しておくと、記述が単純になる。 static T Max (params T[] a) => a.Max (); Max(A+B, A-B, A*B);
B
黒で塗られている石はX - K + 1からX + K -1で、かつ座標が-1000000から1000000の範囲に収まっているものなので、条件に気をつけて猫写するだけ。
ただし、スペース区切りで一行に答えを出力する問題では最後に無駄なスペースが出力されてしまうのが気持ち悪いので、まず最初に配列にまとめて記録してstring.Joinで文字列にするようにする。
これも関数を定義しておくと楽。
// 関数定義、区切り文字がしていされなければ空白にする。 static void Dbgs (IEnumerable a, string split = " ") => Console.WriteLine(string.Join (split, a)); int[] a = new int[5] {"1", "2", "3", "4", "5"}; // 1 2 3 4 5
C
Nこの文字列の中にアナグラムが何組あるかを求める。
(1) 各文字列をソートして、正規化する。 (2) 正規化した後の各文字列がそれぞれ何個あるかを数える。 (3) 正規化した後にある文字列がn個あれば、アナグラムであるようなiとjの組み合わせはn (n-1) /2こあるはずなので足し合わせて答えを出す。
気をつけなければならないのは、(2)の数え上げをソートを利用してやろうとするとTLEになることがあるので(N <= 10 ^5のO(N log N)なのでセーフじゃないかと思ったのだけど)、Dictionaryを利用すること。
また、n * (n-1)の計算はintでやるとオーバーフローを起こすので、意識的にlongを利用すること。
int a = //大きな値 long ans = a * a;
はC#ではオーバーフローになるので、注意。(longに代入しているのだから気を効かせてほしいといつも思う)
D
M日以内に報酬を受け取らなければならないという制約を考えると、M-i日後にやる意味のある仕事は、i日以内に報酬をもらえる仕事だけです。
後ろから考えていくと、
(i = 1日目) 1日以内に終わる仕事の中で、一番儲かる仕事をする。
(i = 2日目) 2日以内に終わる仕事の中で、まだ実行されていない最も儲かる仕事をする。
(i = 3日目) 3日以内に終わる仕事の中で、まだ実行されていない最も儲かる仕事をする。
となります。これは直感的にはかなり難しくてD問題をACすることができませんでした。
理由としては、i = 1日目に一番儲かる仕事を選択することが唯一の正解ではないパターンがある点でしょうか・・・。
すっと納得できる気はしないので、一旦このようなパターンがあることを覚えておくのが良い気がします。
これまでの中で最も大きな（あるいは小さな）値を選択していくという問題にはPriorityQueueというデータ構造が適していて、PushとPopにそれぞれO(log N)で操作可能です。
C#には、PriorityQueueがないので、自前で実装する必要がありますが・・・。
E
以降 解けてません。
