【C#】パ研合宿2019 第3日「パ研杯2019」 C - カラオケ をC#で解いてみた【AtCoder】
デリゲートとFunc
Funcという素晴らしい機能がある。
まずC#には、デリゲートという変数にメソッドを格納するというよくわからない機能があるのだが、それを使いやすくしてくれるのがFuncというクラスである。
このクラスの説明はネットの海にいっぱい詳しいものが転がっているので割愛するが、このFuncもといデリゲートの真価は「メソッドの実行を任意に操作できる」という点にあるのではないだろうか。
とある競技プログラミングの問題に投稿されていた解答をもとに自分でコードアナライズをしてみた結果を以下に記す。
Console.ReadLine()を適切なタイミングで実行し、複雑な標準入力の値を見事にコントロールしているのが分かる。
このソースを書いた人は天才だ…！
問題文はこちら↓
atcoder.jp
サンプルプログラム
static void solve()
{
//入力パラメーターなし(引数なし)のデリゲート
//標準入力を読みとり、Splitしてint型の配列に代入する
Func<int[]> read = () => Console.ReadLine().Split()
Select(int.Parse).ToArray();
//デリゲートを実行し、結果を変数に代入
//この読み取りでは1ライン目(NとMの値)を読み取る
var h = read();
//N(生徒数)とM(選べる曲数)を変数に代入
int n = h[0], m = h[1];
//2行目以降を読み取り
//長さがNの配列を用意し、すべてのコレクションに対し、
//デリゲートのメソッドを実行する
var a = new int[n].Select(_ => read()).ToArray();
//Long型で0を代入する
var M = 0L;
//曲数だけループ
for(int j = 0; j < m; j++)
{
//現在の曲+1(次の曲)から曲数だけループ
for (int k = j + 1; k < m; k++)
{
//0からn(生徒数)までの配列の範囲で、曲の得点を
//それぞれ比較し、一番大きい得点を算出
//各生徒の最大得点が出揃ったところでSumで合計する。
//出てきた値はMに代入
//i = Rangeのループ数 j = 曲1 k = 曲2
M = Math.Max(M, Enumerable.Range(0, n)
.Sum(i => (long)Math.Max(a[i][j], a[i][k])));
}
}
}
【C#】フォルダ内のテキストファイルの中身をひとつのファイルに全部書き込みするプログラム
プログラムのおすそわけ
AtCoderのテストケース漁ってたら拡張子のついてないテキストデータが小分けで大量に出てきたので、
一個ずつ拡張子をつけて開くのも面倒くさいからひとつに合体させるプログラムを作ってみた。
サンプルプログラム
static void Main(string[] args)
{
Console.WriteLine("フォルダを読み込み、フォルダ内のテキストデータをマージします。");
Console.WriteLine("読み込みたいフォルダパスを入力して何かキーを押して下さい。");
string DesktopFolderPath = System.Environment.GetFolderPath(System.Environment.SpecialFolder.Desktop) + @"\MergedText";
string FolderPath = "";
FolderPath = Console.ReadLine();
Console.WriteLine("フォルダの読み込みを開始します。");
Console.WriteLine("フォルダ内のテキストデータをマージしています。");
string[] files = System.IO.Directory.GetFiles(FolderPath, "*", System.IO.SearchOption.AllDirectories);
System.IO.Directory.CreateDirectory(DesktopFolderPath);
foreach(var item in files)
{
using (StreamWriter sw = new StreamWriter(DesktopFolderPath + @"\MergedText.txt", true,Encoding.GetEncoding("utf-8")))
{
using (StreamReader sr = new StreamReader(item))
{
string s = sr.ReadToEnd().Trim();
sw.WriteLine(s);
}
}
}
Console.WriteLine("テキストデータのマージが完了しました。何かキーを押して終了して下さい。");
Console.ReadKey();
return;
}
解説
まとめたいデータが置かれているフォルダパスを入力すると、デスクトップに「MergedText」というフォルダができる。
名前は正直適当なので恥ずかしい( ˘ω˘ )
その中に、データが順番に書き込みされたテキストデータが入っている。
まとめたいデータは拡張子がなくてもOK。
【C#】AtCoder Beginner Contest122 B - ATCoder をC#で解いてみた【AtCoder】
サンプルプログラム
static void Main(string[] args)
{
var S = Console.ReadLine();
List<string> ACGT = new List<string> { "A", "C", "G", "T" };
bool[] b = new bool[S.Length];
var ans = 0;
for (int i = 1; i <= S.Length; i++)
{
//退避
var _b = b;
foreach (var item in ACGT)
{
if (Convert.ToString(S[i - 1]) == item)
{
_b[i - 1] = true;
b = _b;
break;
}
}
//ACGT以外の文字だったら
if (_b[i - 1] == false)
{
ans = Math.Max(ans, _b.Count(p => p));
b = new bool[S.Length];
}
}
ans = Math.Max(ans, b.Count(p => p));
Console.WriteLine(ans);
}
軽く解説
入力した文字の文字数分のbool型配列を作り、初期値は全てfalseとする。
一文字ずつA、C、G、Tが含まれているかを調べ、含まれていたらtrueにする。
含まれていなかったらfalseとし、ansにその時点でのtrueの数を記録する。
bool配列をリセットし、次の文字からまた順番に検査していく。
falseが出てくるたびにansと比べ、最終的に一番大きい数を残し、出力する。
使い方、合ってるかしら('ω')
【C#】ワーシャルフロイド法【アルゴリズム研究】
ワーシャルフロイド法？
アルゴリズムの一種…らしい。
ワーシャル–フロイド法（英: Warshall–Floyd Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるスティーブン・ワーシャル（英語版）とロバート・フロイドにちなむ（2人はそれぞれ独立に考案）。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド–ワーシャル法とも呼ばれる。 from Wikipedia
何言ってるかわからんね＼(^o^)／
こんなよくわからないアルゴリズムに手を出した理由は、AtCoder Beginner Contest 180のE問題「Traveling Salesman among Aerial Cities」にある。
いわゆる巡回セールスマン問題という有名なアルゴリズムの問題らしい。
前から名前だけは聞いていたけど実際に解くのはこれが初めてだった。
当然、問題文を見てもチンプンカンプン。
太古の魔術書でも読んでる気分になる。
今回は手も足も出ない状態なので、いきなりネットの先人のソースを参考にするところからスタート。
ソースを写経し、処理を順番に追ってみるけど…
わからん＼(^o^)／
それでも頑張って調査を続けてたらタイトルにもある「ワーシャルフロイド法」を使っているらしいことがわかった。
すごく丁寧に説明してくれてるサイトがあったのでソースを拝借し、自分なりにまとめてみることにした。
ワーシャルフロイド法のサンプルプログラム
static void Main(string[] args)
{
Solve(0, 4); // 3
Solve(0, 3); // 2
Solve(1, 2); // 2
Solve(1, 3); // 1
Solve(1, 4); // 2
}
/// <summary>
/// アルゴリズム本体
/// </summary>
/// <param name="start">始点のパラメータ</param>
/// <param name="goal">終点のパラメータ</param>
static void Solve(int start, int goal)
{
//各辺の入力データ
//データ保存用のEdge構造体のインスタンスを入れられる、ジェネリッククラスを生成
var edges = new List<Edge>();
//値(地点)を入力していく
edges.Add(new Edge(0, 1, 2)); //始点0、終点1、コスト2
edges.Add(new Edge(0, 2, 1));
edges.Add(new Edge(1, 3, 1));
edges.Add(new Edge(1, 2, 2));
edges.Add(new Edge(2, 3, 1));
edges.Add(new Edge(2, 4, 3));
edges.Add(new Edge(3, 4, 1));
// 頂点iからjへの最短距離を格納するDP
// 初期値は大きな値(INF)を入れておく
// 同じ頂点への距離は0にする
//DP:動的計画法(Dynamic Programming)。アルゴリズムの一種。対象となる問題を複数の部分問題に分割し、
//部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。
var INF = 999999999;
//コストを格納する二次元配列。5,5を設定する。
var DP = new int[5, 5];
for(int i = 0; i < 5; i++)
{
for(int j = 0; j < 5; j++)
{
//すべてのコストに初期値999999999を設定しておく
DP[i, j] = INF;
}
//同じ頂点への距離は0にする
DP[i, i] = 0;
}
//1つの辺で直接つながる時の距離
foreach(var e in edges)
{
//DP[始点,終点] = コスト(距離)
DP[e.From, e.To] = e.Cost;
}
//頂点iからjへの距離と、i → k → jと、kを経由する距離を比べる
for(int k = 0; k < 5; k++)
{
for(int i = 0; i < 5; i++)
{
for(int j = 0; j < 5; j++)
{
//i,jのコストとi,k + k,jのコストを比較し、小さいほうを格納する
DP[i, j] = Math.Min(DP[i, j], DP[i, k] + DP[k, j]);
}
}
}
//dp の中に頂点間の距離が格納されている
//先にコストをすべて計算した上で、最後に引数の値で答え合わせをするイメージ
//INFの場合は点を結ぶ辺が存在しない、到達できない
var ans = DP[start, goal];
Console.WriteLine(ans);
}
/// <summary>
/// 各辺のデータ(始点、終点、コスト)を格納するクラス
/// </summary>
struct Edge
{
public int From { get; set; }
public int To { get; set; }
public int Cost { get; set; }
public Edge(int f,int t,int c)
{
this.From = f;
this.To = t;
this.Cost = c;
}
}
}
【C#】AtCoder Beginner Contest180 D - Takahashi_Unevolved をC#で解いてみた【AtCoder】
※この解答は個人の見解の為、参考程度にご覧ください。
問題文
コメント
ゲームのパラメータ調整ですごく使いそうな感じのアルゴリズム。
難しかったけど、解いてて楽しかった。
最初自分で書いたコードは、サンプルテストケースはうまくいったけど他のテストケースはWA出しまくってどうしようもなかった。
結構うまく書けたと思ったのになあ…。
ネットで天才エンジニアの人が書いたの参考にプログラムを書き直した。
プログラムの勉強は
①まず自分で書いてみる。
➁ネットのすごい人のを参考に書いてみる。
➂分からない処理は分かるまで調べる。
④自分のコードとミックスしてみる。
が、結構自分の中でイイ感じである。
自分で書いてみたコード
static void Main(string[] args)
{
var input = Console.ReadLine().Split(" ");
var X_Power = long.Parse(input[0]);
var Y_EvolLevel = long.Parse(input[1]);
var A_doublePower = long.Parse(input[2]);
var B_addPower = long.Parse(input[3]);
long Experience = 0;
List<long> list = new List<long>();
for (int i = 1; i <= Y_EvolLevel; i++)
{
//基礎パワーを退避
var x = X_Power;
//ループの数だけパワーを倍増
x = x * (A_doublePower * i);
Experience++;
//値チェック
if (x > Y_EvolLevel)
{
Experience--;
list.Add(Experience);
break;
}
//ループの数だけパワーを倍増
for (int j = 1; j <= Y_EvolLevel; i++)
{
if (x + B_addPower * j < Y_EvolLevel)
{
Experience++;
x += B_addPower * j;
}
else if (x + B_addPower * j == Y_EvolLevel)
{
Experience++;
break;
}
else
{
break;
}
}
list.Add(Experience);
Experience = 0;
}
list.Sort();
var count = list.Count;
Console.WriteLine(list[count - 1]);
}
解答例
static void Main(string[] args)
{
var input = Console.ReadLine().Split(" ");
var X = int.Parse(input[0]);
var Y = int.Parse(input[1]);
var A = int.Parse(input[2]);
var B = int.Parse(input[3]);
long Experience = 0;
while (true)
{
//加算値より強さが大きい時
//倍化しつくした残りの値で、まだ加算の余地がある場合にここにくる
if (X >= B)
{
//経験値に加算 (進化レベル - 1 - 強さ(値を反映させた現在の強さ)) / 加算値
//-1しないと進化レベルぴったりになるので避ける
Experience += (Y - 1 - X) / B;
break;
}
//強さを倍化させた値が進化レベルに届いていない時
if (X * A < Y)
{
//経験値に1を加算
Experience ++;
//倍化させた値を強さに反映
X = X * A;
}
//進化レベルに届いてしまったら倍化した値を反映させず、加算値を残り全清算
else
{
//経験値に加算 (進化レベル - 1 - 強さ) / 加算値
Experience += (Y - 1 - X) / B;
break;
}
}
Console.WriteLine(Experience);
}
【C#】AtCoder Beginner Contest180 C - Cream puff をC#で解いてみた【AtCoder】
※この解答は個人の見解の為、参考程度にご覧ください。
〇問題文
N 個のシュークリームがあります。
シュークリームを分割することなく平等に分けることができるような人数としてあり得るものを全て求めてください。
簡単に言うと素因数分解しろって問題。
めっちゃ簡単やんけ！と思いきや、安直にループで全値走査するとでかい値のテストケースの時にタイムアウトを起こす…。
そこはほら、競技プログラミングだからね。ちゃんと効率のいいアルゴリズムを使おうね。
〇解答例
static void Main(string[] args)
{
//大きな値のテストケースにそなえ、Long型にする
var N = long.Parse(Console.ReadLine());
List<long> ans = new List<long>();
//約数列挙というアルゴリズムを使う
//ある値が割り切れる(約数である)のならば、その累乗した値も約数である
//for文の条件で、i * iを採用したのは上記の約数列挙の理屈に基づいたもの
//Nに値が近づくまで走査を繰り返す
//この手法は普通のループに比べて計算量が少なくて済む
for(long i = 1; i*i <= N; i++)
{
//Nがiで割り切れる場合、リストに値を追加する(約数である)
if(N % i == 0)
{
ans.Add(i);
//さらにiがN÷iの値と同一ではない時は、N÷iの値をリストに追加する
//ex)N=720、i=2のとき、N÷i=360となるのでリストに追加する
//Nと昇順と降順からそれぞれ計算を進めていくイメージ
if(i != N/i)
{
ans.Add(N / i);
}
}
}
//約数のリストアップが終わったら昇順にソートしてあげる
ans.Sort();
//String.Joimクラスを使ってコレクションの要素を\n(改行)でくっつけ、出力する
Console.WriteLine(string.Join("\n", ans));
}
【C#】AtCoder Beginner Contest180 B - Various distances をC#で解いてみた【AtCoder】
※この解答は個人の見解の為、参考程度にご覧ください。
〇解答例
static void Main(string[] args){
var N = int.Parse(Console.ReadLine());
//LinQでLong型のIEnumarableクラスを作成する
var X = Console.ReadLine().Split(' ').Select(e => long.Parse(e));
//マンハッタン距離、ユークリッド距離、チェビシェフ距離を格納する変数を作成
long mh = 0; long yu = 0; long ch = 0;
foreach(var item in X)
{
//Xに格納した値の絶対値を順番に取り出す
var i = Math.Abs(item);
//マンハッタン距離：地点Aから地点Bまで、碁盤の目に沿ったかのような距離
//カクカクしている ※詳しくはググってね
//計算方法：値を後ろへ順番に加算する
mh += i;
//ユークリッド距離：一番メジャーな距離。地点Aから地点Bまでの直線距離を平方根の原理を使って算出
//計算方法：値を累乗したものを後ろへ順番に加算し、合計を平方根で計算する
yu += i * i;
//チェビシェフ距離：地点Aから地点Bまで、チェスや将棋のようにマス目移動するかのような距離
//つまりファイアーエムブレム
//計算方法：Math.Max()を使い、入力した引数の最大値をとる
ch = Math.Max(ch, i);
}
Console.WriteLine(mh); //マンハッタン距離を出力
Console.WriteLine(Math.Sqrt(yu)); //Math.Sqrtを使って平方根を計算してユークリッド距離を出力
Console.WriteLine(ch); //チェビシェフ距離を出力
}
