たくあんポリポリ

勉強したことを載せていきます。最近、技術系の記事はZennに書いています。(https://zenn.dev/chittai)

【AtCoder】【C#】AtCoder Beginner Contest 079 D-Wall

ABC079のD問題、Wallを解きました。自分の解答でACできたのですが、想定解答をみたらワーシャルフロイドを使用していたので(自分の解答では使用していない)、次回同じような状況になった時にちゃんとワーシャルフロイドを使用できるようにポイントをまとめます。

最初は自分の解法の説明で、最後にポイントをまとめています。

続きを読む

【AtCoder】【C#】AtCoder Beginner Contest 148 の反省

AtCoder Beginner Contest 148のコンテストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。

続きを読む

【C#】文字列を整数値に変換する方法(int.Parse / int.TrayParse)

AtCoderなどの問題で、標準入力から受けた文字列Sを整数に変換するとき、普段は int.Parse(S); で変換しているのですが、そもそもエラー処理として変換できない場合はどのように処理するの調べてみました。

続きを読む

【AtCoder】【C#】AtCoder Beginner Contest 147 の反省

AtCoder Beginner Contest 147のコンテストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。

続きを読む

【AtCoder】【C#】三井住友信託銀行プログラミングコンテスト2019の反省

だいぶ遅くなりましたが、三井住友信託銀行プログラミングコンテスト2019のコンテンストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。

続きを読む

【AtCoder】【C#】組み合わせのすべてのパターンを利用する方法

n個からr個取り出すパターンを計算する時は、nCrで計算が可能です。例えば、5個の中から3個取り出すときは10通りです。今回は、このように10通りの組み合わせをすべて出力するための方法を説明します。

続きを読む

【AtCoder】【C#】グラフ問題でのノード同士の接続状態の管理、経路問題での通過したノードを管理する方法の紹介

今回のタイトルですが、題材となっているのは下記の問題です。

atcoder.jp

続きを読む

【AtCoder】【C#】幅優先探索の実装~その②~ AtCoder Beginner Contest 007 C問題より

以前、下記記事でも書いたように幅優先探索を実装しました。題材として、AtCoderの問題を使用しました。ですが、結果はほぼTLEにて終了。当時は原因がわからず放置していたのですが、蟻本で再度、幅優先探索について勉強する機会ができたので、あらためて前回の課題部分を解決した実装をしてみました。

この記事の主題は、主にC#における幅優先探索実装の一例の紹介です。基本的には幅優先探索アルゴリズムは理解している上で話しを進めています。

c-taquna.hatenablog.com

はじめに

幅優先探索の実装の説明に入る前に、前回の記事について簡単にまとめておきます。

問題へのリンク

問題へのリンクを張っておきます。 atcoder.jp

過去の記事について

過去記事のリンクは最初の方に張ってあるので、そちらを参照してください。

前回記事の課題について

まず、問題となったのは最初の2ケース以外TLEになっていることです。最初の2ケースはうまくいっているので、計算量に問題があるものと考えられます。この計算量がなぜ多くなっているのか、どうやって減らすのかが今回の問題でした。

本論

前回の課題で問題となった点と、その解決方法

今回、問題だったのは一度経由した点の処理をしていなかったことが問題でした。当時はアルゴリズムの勉強を始めたばかりだったので(という言い訳、、)、今となってな当たり前な処理ができていませんでした。

今回、壁が "#"で経由できる点が"."で与えられます。今回の実装は次の点の候補が"."だったらさらにそこから4方向を調べるといったものでした。下記のような感じで書いていました。

if (次のマス == '.') { q.Enqueue(Tuple.Create(次のマスのx, 次のマスのy, 今まで経由したマス + 1)); }

ただ、これだと何度も同じマスが調べられてしまうので、一度経由したマスは#に変更するようにしました。

if (次のマス == '.') { 次のマス = '#'; q.Enqueue(Tuple.Create(次のマスのx, 次のマスのy, 今まで経由したマス + 1)); }

これで一度経由されたマスはもう計算対象にならないので計算量がぐっと減らせます。この実装で気をつけたいのはキューに入れる前に#で埋めないといけないという点ですね。

実装

上記の実装で前回の問題は解決できたのですが、下記実装のメモをあわせて残しておこうと思います。

Tupleの使用

複数の値をまとめてキューに入れたい時は、Tupleのキューを作成して入れると良いと思います。こんな感じです。

Queue<Tuple<int, int, int>> tq = new Queue<Tuple<int, int, int>>();
q.Enqueue(Tuple.Create(次のマスのx, 次のマスのy, 今まで経由したマス + 1)); 

各マスの周辺を調べる時の実装方法

あるマスから、四方のマスを確認する時の実装です。下記のようにやるときれいに書けます。

int[] vx = { 0, 1, 0, -1 };
int[] vy = { 1, 0, -1, 0 };

for (int i = 0; i < 4; i++)
{
    int nx = x + vx[i];
    int ny = y + vy[i];
    if ((0 <= nx && nx < C) && (0 <= ny && ny < R) && map[nx, ny] == '.')
    {
        map[nx, ny] = '#';
        tq.Enqueue(Tuple.Create(nx, ny, step + 1));
    }
}

【AtCoder】【C#】DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 の反省

ここでは、DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選(以下、DDCC)のコンテンストに参加して、どのように考え解いたのか、なぜ解けたのか、なぜ解けなかったのかを反省として書き残しておきたいと思います。

続きを読む