幅優先探索の一般的な罠

幅優先探索でTLEする一般的な罠の解説です。
こういうグリッドを幅優先する問題で起こりやすいですね。
C: 幅優先探索 - AtCoder Beginner Contest 007 | AtCoder


簡単のためこのような迷路を考えます。(#壁、.通行可)

/abcdef
1######
2####G#
3###..#
4##...#
5#...##
6#S.###
7######

この迷路の幅優先探索は本来こうあるべきです

{(b,6)}
->{(b,5),(c,6)}
->{(c,5)}
->{(c,4),(d,5)}
->{(d,4)}
->{(e,4),(d,3)}

ところが、このようなコードを書くと

struct Point {
	int y, x;
};
char map[100][100];             //HW '.'通行可、'#'通行不可
bool visited[100][100] = {};    //HW 確認したらtrueに
int  dist[100][100];            //HW Sからの距離

que.push(S);
dist[S.y][S.x] = 0; visited[S.y][S.x] = true;
while (!que.empty()) {
	Point now = que.front(); que.pop();
	visited[now.y][now.x] = true;//見たよ!(実はこれがマズイ)
	const int diff[] = { 1,0,-1,0,1 };
	for (int i = 0; i < 4; ++i) {
		int nexty = now.y + diff[i], nextx = now.x + diff[i + 1];
		if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) {
			//まだ見ていない
			que.push(Point{ nexty , nextx });
			dist[nexty][nextx] = dist[now.y][now.x] + 1;
		}
	}
}
cout << dist[G.y][G.x] << endl;

queの中身がこうなってしまいます。

{(b,6)}
->{(b,5),(c,6)}
->{(c,5),(c,5)}//ん?
->{(c,4),(d,5),(c,4),(d,5)}
->{(d,4),(d,4),(d,4),(d,4)}
->{(e,4),(d,3),(e,4),(d,3),(e,4),(d,3),(e,4),(d,3)}//あれ?

このように指数的に増えていってしまうので、TLEしてしまいます。
なぜこのようになるのかというと、
・(b,5)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
・(c,6)を見ているとき、(c,5)はまだ行ったことが無いのでqueに追加します
という動作になってしまっているからです。

これを解消するには、同じものを二回以上見ないように、「そこはもう調べることになっている」という段階で枝狩りしてやります。

struct Point {
	int y, x;
};
char map[100][100];             //HW '.'通行可、'#'通行不可
bool visited[100][100] = {};    //HW 確認したらtrueに
int  dist[100][100];            //HW Sからの距離

que.push(S);
dist[S.y][S.x] = 0; visited[S.y][S.x] = true;
while (!que.empty()) {
	Point now = que.front(); que.pop();
	const int diff[] = { 1,0,-1,0,1 };
	for (int i = 0; i < 4; ++i) {
		int nexty = now.y + diff[i], nextx = now.x + diff[i + 1];
		if (map[nexty][nextx] == '.' && visited[nexty][nextx] == false) {
			//まだ見ていない
			que.push(Point{ nexty , nextx });
			dist[nexty][nextx] = dist[now.y][now.x] + 1;
			visited[nexty][nextx] = true;//これから見るよ!(変更箇所)
		}
	}
}
cout << dist[G.y][G.x] << endl;

visitedに代入するタイミングを変えただけですね。

セグ木テンプレ

C++11用オレオレセグ木テンプレです。
「変更するコードここから」の下を書き換えて使います。

segment_tree<int, 1000> seg;

で要素int,大きさ1000のセグ木が出来ます。2の累乗には勝手に拡張するので1024でなくて良いです。
これをそのまま使うのではなく、これは一例と思っておいて自分用にカスタマイズするのが良いかと思います。

#include <cstdint>
inline constexpr uint32_t get_min2pow(uint32_t value, uint32_t work = 1) {
	return ((value <= work) ? (work) : (get_min2pow(value, work * 2)));
}
template<typename value_type_, uint32_t N_RAW_MAX>
class segment_tree
{
public:
	using value_type = value_type_;
	static constexpr uint32_t N_MAX = get_min2pow(N_RAW_MAX);
private:
	value_type default_value;
	value_type value[N_MAX * 2 - 1] = {};
	static inline constexpr int32_t getchild(int i) {
		return i * 2 + 1;
	}
	static inline constexpr int32_t getparent(int i) {
		return (i - 1) / 2;
	}
	void Init_impl(int k = 0)
	{
		if (k < N_MAX - 1) {
			//ノード
			auto c1 = getchild(k), c2 = c1 + 1;
			Init_impl(c1);
			Init_impl(c2);
			value[k] = merge(value[c1], value[c2]);
		}
		else {
			//葉
			value[k] = default_value;
		}
	}
	value_type query_impl(int32_t a, int32_t b, int32_t k = 0, int32_t l = 0, int32_t r = N_MAX)const
	{
		if (r <= a || b <= l)return default_value;
		if (a <= l && r <= b)return value[k];
		int m = (l + r) / 2;
		return merge(query_impl(a, b, getchild(k), l, m), query_impl(a, b, getchild(k) + 1, m, r));
	}

public:
	template<typename T, typename FUNC>
	void change(int32_t i, T&& v, FUNC&& operation = std::plus<>{})
	{
		i += N_MAX - 1;
		//葉
		value[i] = std::forward<FUNC>(operation)(std::move(value[i]), std::forward<T>(v));
		i = getparent(i);
		//ノード
		for (;;) {
			auto c1 = getchild(i), c2 = c1 + 1;
			value[i] = merge(value[c1], value[c2]);
			if (i == 0) { break; }
			i = getparent(i);
		}
	}

	//-----------------------------変更するコードここから-----------------------------//
private:
	static inline value_type merge(const value_type& l, const value_type& r)
	{
		ここを書く;
		//RMQ
		return std::min(l, r);
		//RSQ
		return l + r;
}
public:
	inline void init()
	{
		default_value = 例外値を書く;
		//全ての葉にdefault_valueを設定し、親はマージで算出(非効率だけど計算量(N)だし気にしない)
		Init_impl();
	}
	inline value_type query(int32_t a, int32_t b)const
	{
		//デフォルト実装は区間をマージするだけ(たぶんいじることは少ない)
		return query_impl(a, b);
	}
};

使い方追記

segment_tree<int, 1000> seg;
seg.init();//必要です
seg.change(5,10);//5番目の要素に10加算します
seg.change(10,10,[](auto,auto v){return v;});//10番目の要素を10にします
seg.query(0,10);//[0,10)にクエリをします

情報オリンピック布教用チラシ

学校でプログラミング講習なるものをやっていたので、先生に言って受講生に配らせてもらったチラシです。なので、プログラムが少し書けることを前提に累積和を入れてあります。
デザイン能力が無いのでみんなで改善してね(?)
(配布の際は1,2ページを表面、3,4ページを裏面として、B4で印刷しました)

AGC011 A Airport Bus:実装の解説

A: Airport Bus - AtCoder Grand Contest 011 | AtCoder

解法:早く着いた人からバスに乗せていけば良いです。
以下、実装のテク。

  • バスには必ず一人以上乗っている。そのバスの出発時刻は保存しておく。

とします。 始めに、1番目の人をバスに乗せます(まだ誰もバスに乗っていないので例外処理)

i番目の人について、今搭乗中のバスの出発時刻より

  • 後にi番目の人が到着するなら、今のバスは出発させて、新しいバスにその人を乗せる
  • 先にi番目の人が到着するなら、
    • バスがいっぱいなら、今のバスは出発させて、新しいバスにその人を乗せる
    • バスに空きがあるなら、今のバスに乗る

最後に、最後のバスを出発させる。(このバスには一人以上必ず乗っている)

Tのソートを忘れないようにしてください。

僕のコード:Submission #1156589 - AtCoder Grand Contest 011 | AtCoder
このコードだと出発時刻じゃなくて搭乗はじめの時間を保存してますがまあ大体同じです。

SRM 245 Div2 Med (Problem 600) Flush:日本語訳のようなもの

フラッシュ

eiya君はフラッシュというカードゲームをしています。このゲームは、手札の中の同じマークのカードの枚数の最大値が得点になります。例えば、手札にスペード5枚、ハート2枚、他0枚の場合、5点です。eiya君はこのゲームを有利に進めたいです。

 

eiya君は今手札を持っていません。今からデッキからnumber枚のカードを引きます。デッキのカードはマークで4種類に分けることができ、これらはそれぞれS0,S1,S2,S3枚です。このとき、number枚のカードを引き終わった後のeiya君の得点の期待値を求めてください。

 

補足:例えば、1/2の確率で得点が3に、残り1/2の確率で得点が2になるとき、期待値は(0.5*3)+(0.5*2)=2.5です。

クラス定義

  • クラス名:Flush
  • メゾット:size
  • 引数:vector<int> , int
  • 戻り値型:double
  • メゾット宣言:double size(vector<int> S, int number)
(メゾットは必ずpublicにしてください)

制限

  • 実行時間2.000
  • メモリ (MB)64

注意

  • 値は32bit整数に収まらない可能性があります。
  • 答えは絶対誤差or相対誤差で10^-9以下になるようにしてください。

制約

  • |S|==4.
  • 0<=Si<=13
  • 0<=number<=Sの合計

テストケース例

  1. input
    • S { 2, 2, 2, 2 }
    • number 2
    output
    Returns 1.1428571428571428
    note
    始めに一枚引きます。次に1/7の確率で始めに引いたカードと同じマークのカードを引きます。
    得点の期待値は (1/7 * 2) + (6/7 * 1) = 8/7 = 1.1428571428571428です。
  2. input
    • S { 1, 4, 7, 10 }
    • number 22
    output
    Returns 10.0
    note
    全てのカードを引くため、一番大きい枚数の10が答えになります。
  3. input
    • S { 13, 13, 13, 13 }
    • number 49
    output
    Returns 13.0
    note
    48枚引いた段階で、少なくとも一つが13枚になっているか、全て12枚かのどちらかです。そこからさらに一枚引くので、少なくとも一つは13枚になります。
  4. input
    • S { 13, 13, 13, 13 }
    • number 26
    output
    Returns 8.351195960938014
  5. input
    • S { 13, 13, 13, 13 }
    • number 0
    output
    Returns 0.0