ARC060 E 高橋君とホテル ダブリングの気持ちになる

ARC060 E 高橋君とホテル

問題概要

リンク参照

考察

  • 制約を見ると二分探索が必要な雰囲気を醸し出しているので意識する
  • 一番初めに考えたのが,今いるホテルからL日以内に行ける次のホテルを二分探索で求めていくこと.でもこれはL=1とかだと確実に破滅するのでこういう考察はダメっぽい
  • ん~困った,(ここで解説を見る)・・・・ダブリング(未知の言葉)
  • そこで,こちらのブログを見に行く

satanic0258.hatenablog.com

  • なるほど,今回だと今いる頂点からN回移動したときのホテルが知りたいみたいな感じに思えるとダブリングが見えてきそうなことが分かってきた
  • このブログ,すごくわかりやすくて理解しやすかった(あとは類題解いて練習しておきたい)
  • 700点精進,ためにはなるけど難しい・・・・

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll, ll> lltpl;



/******************************************************************************************/


const ll MOD = 1e9 + 7;



template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


int dp[20][100005];//dp[i][j]:=j番目の頂点から2^i日以内に到達できる最右のホテル

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> x(n);
	for (int i = 0; i < n; i++)
	{
		cin >> x[i];
	}

	int L, Q;
	cin >> L >> Q;
	
	for (int i = 0; i < n; i++)
	{
		dp[0][i] = upper_bound(x.begin(), x.end(), x[i] + L) - x.begin() - 1;
	}


	for (int i = 0; i < 19; i++)
	{
		for (int j = 0; j < n; j++)
		{
			dp[i + 1][j] = dp[i][dp[i][j]];
		}
	}

	for (int i = 0; i < Q; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if (a > b) {
			swap(a, b);
		}

		int ans = 0;
		for (int i = 19; i >= 0; i--)
		{
			if (dp[i][a] < b) {
				a = dp[i][a];
				ans += 1 << i;
			}
		}
		ans++;
		cout << ans << endl;
	}

	return 0;
}

ゆるふわオンサイト参加記

ゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状(長い...)記録

FORCIA様にお邪魔して🦍の挑戦状を受けてきました

コンテスト結果

D,E,F全部バグらせてGも方針はすぐ見える問題だったのに時間が足りなくて草.バグらせるのをやめたい.そして人々みんな強い.

懇親会

会ったことがない人(Twitter上では絡みがあるけど)とお話ししてやっぱこの人たち強くてやべぇってなることしかできなかった....
ん~いろいろあるけど,とりあえずじょえさん中本食べ過ぎで心配になってきた笑

まとめ

今回自分の実力でコンテスト中に椅子を温めることが多いのかな?と思っていたのですが,問題量が多い,そしてバグる,その結果2時間常にやることがあって非常に満足度の高いコンテストでした.(prdさん,mastuさんありがとうございました)

ん~次も行きたい!!!

2次会

お肉うますぎた!!(ご馳走さまでした!!!)

ARC061 E すぬけ君の地下鉄旅行 01BFSに帰着

ARC061 E すぬけ君の地下鉄旅行

問題概要

リンク参照

考察

  • 見た感じ最短経路問題
  • ただし,単純な最短経路問題ではなく,会社の情報が必要.これは,乗り換え時にコストがかかるため
  • 同じ会社の地下鉄を使う場合:コストがかからないのでコスト0の辺を張る
  • 違う会社の地下鉄に乗り換える場合:コスト1がかかる.この時点でコスト0または1の辺のみを張ればいいので01BFSが見えてくる.(頂点,会社)を持つので拡張01BFS的な名前でもつくのかしら?
  • 乗り換える際は,コスト0の辺を頂点-1(仮の頂点,改札を出るイメージ)に張り,頂点-1からコスト1の辺を改札を出た頂点に張ればよい(賢すぎでは,これ思いつくの)
  • こういうの解けるようになりたいね

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<queue>
#include<set>
#include<iomanip>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> P;
typedef long long int ll;
typedef pair<ll,ll> LLP;
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
#define INF 1000000007
#define MOD 1000000007
#define ARRAY_MAX 100005



typedef struct edge{
    pair<int,int> to;//今いる位置、会社
    int cost;//移動にかかるコスト
}EDGE;

int n,m;
map<P,vector<EDGE> > G;
set<P> used;

int bfs(){

    deque<EDGE> deq;
    deq.push_back(EDGE{P(0,-1),0});
    int ans = -1;

    while(!deq.empty()){
        EDGE es = deq.front();
        deq.pop_front();
        if(used.find(es.to) != used.end()){
            //もう使ったので調べない
            continue;
        }
        used.insert(es.to);
        if(es.to == P(n-1,-1)){
            //目的地に着いた
            //つまり、駅nの改札を出たところなら
            ans = es.cost;
            break;
        }
        for(auto itr:G[es.to]){
            //次の駅の候補を調べる
            if(used.find(itr.to) != used.end()){
                //次の駅がすでに調べられているなら調べない
                continue;
            }
            if(itr.cost == 0){
                deq.push_front({itr.to,es.cost});
            }else{
                deq.push_back({itr.to,es.cost+1});
            }
        }       
    }
    return ans;
}



int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    cin >> n >> m;
    REP(i,m){
        int p,q,c;
        cin >> p >> q >> c;
        p--;
        q--;
        //同じ会社の間にコスト0の辺を張る
        G[P(p,c)].push_back((EDGE){P(q,c),0});
        G[P(q,c)].push_back((EDGE){P(p,c),0});


        //駅番号-1は駅から改札を出ることを表す,コスト0の辺を張る
        G[P(p,c)].push_back((EDGE){P(p,-1),0});
        G[P(q,c)].push_back((EDGE){P(q,-1),0});

        
        //改札を出て別の会社の駅に入る時にコスト1かかるとする,コスト1の辺を張る
        //途中で別の会社を使って再びもとの会社を使う時にもコストはかかる
        G[P(p,-1)].push_back((EDGE){P(q,c),1});
        G[P(q,-1)].push_back((EDGE){P(p,c),1});
    }

    int ans = bfs();
    cout << ans << endl;

    return 0;
}

ABC048 D An Ordinary Game 苦手なんじゃ(´・ω・`)

ABC048 D An Ordinary Game 苦手なんじゃ(´・ω・`)

問題概要

リンク参照

考察

  • ゲーム問題苦手すぎる
  • えーーおそらくこういう問題は簡単なケースを実験してそこから類推していく感じだと(これ直感で解ける人天才では?)
  • ゲーム系問題が考察により奇偶判定になる場合もあるのでそこらへんも頭に浮かべながら進める
  • "abc","aba","abca","abcd"くらいのケースが基本パターンになりそう
  • 「奇数長と先頭と末尾が違う」,「奇数長と先頭と末尾が同じ」,「偶数長と先頭と末尾が同じ」,「偶数長と先頭と末尾が違う」に分かれる
  • 勝つ人はそれぞれ先手,後手,後手,先手になる
  • 間に1文字追加されたら勝者は反転するように見える(実験から分かってきた~(≧◇≦))
  • これをうまく判定できる演算になんと,XORがある(・∀・)
  • 「先頭と末尾の文字が同じ」XOR「奇数長である」が偽ならば後手必勝となる
  • 非常に🌲びしい

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<climits>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;


/******************************************************************************************/


int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	string s;
	cin >> s;
	
	bool flag1 = (s[0] == s.back());
	bool flag2 = (s.size() % 2 == 1);

	if(flag1^flag2){
		cout << "First" << endl;
	}
	else
	{
		cout << "Second" << endl;
	}


	return 0;
}

ABC126 E 1 or 2 グラフに見えるか??

ABC126 E 1 or 2

問題概要

リンク参照

考察

  • A_{X_i}A_{Y_i}のどちらかが分かればもう片方も分かることに気がついた
  • これをグラフの連結成分になっていると見ると,答えが連結成分の個数だということが見えてきた
  • 連結成分の個数はUnion-Findを使って実装すればよいので実装する
  • サンプルも優しくて解きやすい感じ
  • Union-Findのライブラリを改修したい(切実)

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };




/******************************************************************************************/


//繋げる方向を一方向にする
typedef struct union_find{
    
    vector<int> pa;//親
    vector<int> ra;//木の深さ
    vector<int> siz;
    //n要素で初期化
    void init(int n){
        pa.resize(n);
        ra.resize(n);
        siz.resize(n);
        for(int i = 0;i < n;i++){
            pa[i] = i;/*各ノードに番号を振る,この時par[x]=xとなる時は木の根となる*/
            ra[i] = 0LL;/*各ノード自体の高さは0*/
            siz[i] = 1LL;
        }
    }
    //木の根を求める
    int find(int x){
        if(pa[x] == x){
            return x;/*根ならそのノードの番号を返す*/
        }else{
            return pa[x] = find(pa[x]);/*根でないならさらにノードの根を探す*/
        }
    }

    //xとyの属する集合を併合する
    void unite(int x,int y){
        x = find(x);//xの根の番号を探す
        y = find(y);//yの根の番号を探す
        if(x == y){//一致すればつながっている
            return;
        }
        pa[y] = x;
        siz[x] += siz[y];
    }

    //xとyが同じ集合に属するか判定
    bool same(int x,int y){
        return find(x) == find(y);//同じ集合なら1、違うなら0が返る
    }
}UF;



int main(){

	int n, m;
	cin >> n >> m;
	int ans = 0;

	vector<int> x(m), y(m), z(m);
	UF tree;
	tree.init(n + 10);
	
	for (int i = 0; i < m; i++){
		cin >> x[i] >> y[i] >> z[i];
		x[i]--;
		y[i]--;
		tree.unite(x[i], y[i]);
	}

	set<int> st;
	for (int i = 0; i < n; i++)
	{
		st.insert(tree.find(i));
	}
	cout << st.size() << endl;


	return 0;
}

yukicoder No.875 Range Mindex Query 手こずった・・・

yukicoder No.875 Range Mindex Query

問題概要

リンク参照

考察

  • 問題文を素直にセグ木で実装すれば通る
  • 普段のセグ木にインデックス情報を持たせる必要があるのでpair型要素のセグ木を用意してあげる(時間かかってしまった・・・・)

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };




/******************************************************************************************/


//RMQ
//セグ木
struct SegmentTree {

private:
	int N;
	vector<pii> node;//0-index
public:

	SegmentTree(int siz) {
		N = 1;
		while (N < siz) {
			N *= 2;
		}
		node.resize(2 * N - 1, pii(INF,0));
	}

	void build(vector<pii>& dat) {
		for (int i = 0; i < dat.size(); i++) {
			node[i + N - 1] = dat[i];
		}
		for (int i = N - 2; i >= 0; i--) {
			if (node[2 * i + 1].first >= node[2 * i + 2].first) {
				node[i] = node[2 * i + 2];
			}
			else
			{
				node[i] = node[2 * i + 1];
			}
		}
	}

	void update(int k, int x) {
		k += N - 1;
		node[k].first = x;
		while (k > 0) {
			k = (k - 1) / 2;//親
			if (node[2 * k + 1].first >= node[2 * k + 2].first) {
				node[k] = node[2 * k + 2];
			}
			else
			{
				node[k] = node[2 * k + 1];
			}
		}
	}

	//[a,b)
	pii getMin(int a, int b) {
		return getMin(a, b, 0, 0, N);
	}

	pii getMin(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return pii(INF,-1);
		}
		if (a <= l && r <= b) {
			return node[k];
		}
		pii vl = getMin(a, b, k * 2 + 1, l, (l + r) / 2);
		pii vr = getMin(a, b, k * 2 + 2, (l + r) / 2, r);
		
		if (vl.first >= vr.first) {
			return vr;
		}
		else
		{
			return vl;
		}
	}
	
};


int main(){

	int n, q;
	cin >> n >> q;
	vector<pii> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i].first;
		a[i].second = i;
	}

	SegmentTree segtree(n);
	segtree.build(a);
	

	for (int i = 0; i < q; i++)
	{
		int h, l, r;
		cin >> h >> l >> r;
		l--;
		r--;
		if (h == 1) {
			//swap
			pii left = segtree.getMin(l, l + 1);
			pii right = segtree.getMin(r, r + 1);
			swap(left.second, right.second);
		
			segtree.update(l, right.first);
			segtree.update(r, left.first);
		}
		else
		{
			//min
			cout << segtree.getMin(l, r + 1).second+1 << endl;
		}
	}

	return 0;
}

ABC081 D Non-decreasing 簡単なケースから考えてみたら解けた(・∀・)

ABC081 D Non-decreasing

問題概要

リンク参照

考察

  • とりあえず適当なサンプルをいじる
  • 分からん
  • とりあえず全部正の数だとして考えると累積和とれば良いことに気が付く
  • 全部負数の場合についても同様
  • 問題は正負両方存在する場合→全部正 or 全部負数にしてしまえば累積和取って終了なことに気が付く
  • 正数のmaxと負数の絶対値maxを比較して,大きいほうの符号に直してしまえばよい
  • 自力ACなのはえらい(・∀・)

ソースコード

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


#define ARRAY_MAX 100005
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };




/******************************************************************************************/

ll sum[200005];


int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> a(n);
	int mini = 0;
	int mini_idx = 0;
	int maxi = 0;
	int maxi_idx = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		if (a[i] >= 0) {
			if (maxi < a[i]) {
				maxi = a[i];
				maxi_idx = i + 1;
			}
		}
		else
		{
			if (mini > a[i]) {
				mini = a[i];
				mini_idx = i + 1;
			}
		}
	}

	int cnt = 0;
	vector<pii> ans;
	if (abs(maxi) > abs(mini)) {
		cnt = maxi;

		//正にする
		for (int i = 0; i < n; i++)
		{
			if (a[i] < 0) {
				a[i] += cnt;
				ans.push_back(pii(maxi_idx, i + 1));
			}
		}

		//累積和の感じ

		for (int i = 0; i < n - 1; i++)
		{
			ans.push_back(pii(i + 1, i + 2));
		}

	}
	else
	{
		cnt = mini;
		//負にする
		for (int i = 0; i < n; i++)
		{
			if (a[i] > 0) {
				a[i] += cnt;
				ans.push_back(pii(mini_idx, i + 1));
			}
		}

		for (int i = n - 1; i > 0; i--)
		{
			ans.push_back(pii(i + 1, i));
		}
	}
	

	cout << ans.size() << endl;
	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i].first << " " << ans[i].second << endl;
	}

	return 0;
}