abc 139 c,d,e

後日参加した
c
ふつうにシミュレーションするだけなのだが書き方が悪く手間取ってしまった。

# include<iostream>
# include<vector>
# include<algorithm>
# include<string>
# include<map>
# include<math.h>
# include<queue>
# include<deque>
# include<stack>
# include<cstdio>
# include<utility>
# include<set>
# include<list>
# include<cmath>
# include<stdio.h>
# include<string.h>
# include<iomanip>
# include<cstdio>
# include<cstdlib>
# include<cstring>
using namespace std;
# define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
# define REP(i, n) FOR(i, 0, n - 1)
# define NREP(i, n) FOR(i, 1, n)
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const ll dx[4] = { 0, -1, 1, 0 };
const ll dy[4] = { -1, 0, 0, 1 };
const int INF = 1e9 + 7;
const ll inf = 1LL << 50;
int gcd(int x, int y) {
	if (x < y)swap(x, y);
	if (y == 0)return x;
	return gcd(y, x%y);
}
void mul(ll a, ll b) {
	a = a * b % INF;
}
///////////////////////////////////////

int main() {
	int N; cin >> N;
	int h[100100];
	for (int i = 0; i < N; ++i)cin >> h[i];
	int ans = 0;
	for (int i = 0; i < N - 1;) {
		int cnt = 0;
		while (h[i] >= h[i + 1]) {
			if (i == N - 1) {
				break;
			}
			cnt++;
			i++;
		}
		ans = max(ans, cnt);
		i++;
	}
	cout << ans << endl;
	return 0;
}

このような書き方でも通るがwhile文の中でiがN-1になってしまった時にbreakする処理を書き忘れてしまいバグらせてしまった。し、ほかの人のコードを見てもfor(int i=0;i<N-1;++i)の部分は変えないほうがいいというような印象を受けた以下修正コード

int main() {
	int N; cin >> N;
	int h[100100];
	for (int i = 0; i < N; ++i)cin >> h[i];
	int ans = 0;
	int cnt = 0;
	for (int i = 0; i < N - 1;i++) {
		if (h[i] >= h[i + 1]) {
			cnt++;
		}
		else {
			cnt = 0;
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
	return 0;
}

abc d
N*(N-1)/2なのだが証明ができなかった。

証明:i=1,2,,,Nについてiが順列のxi番目に登場するとするとする。すると目的関数（最大化したいもの)は、(x1 mod 1)+(x2 mod 2)+(x3 mod 3),,,,(xN mod N)になる。各項に着目するとそれぞれの項は最大でも0,1,,,,N-1になるがi>=2についてxi=i-1とし、x1=N実際に(N mod 1)+(1 mod 2)+,,,+((N-1) mod N)=0+1+,,,N-1とできるため目的関数の最大値は0+1+,,,+N-1=N*(N-1)/2となる。

自明だった、、

E

//Nチームで総当たり戦を行う。各チーム戦う相手の順番が決まっているものとする
//各チーム1日で１試合しか行えない。異なるチームは同日に並行して試合を行える
//総当たり戦を完了するまでに必要な最小日数は何日か
//試合が行えるものからどんどん行えばよい日数の効率的な数え方を考える
//愚直に全チーム見て試合できそうなところを貪欲に行うとすると間に合わない
//そこで２日目以降は前日に試合の実施状況に変化があった人のみ次の試合が可能か判定する
int N;
deque<int>A[1010];//両端キュー
int step[1010];//step[i]>numだったらその日iチームは試合を行えない
int M;
int main() {
	int i, j, k, l, r, x, y; string s;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N - 1; ++j) {
			cin >> x;
			A[i].push_back(x - 1);
		}
	}
	M = N * (N - 1) / 2;
	queue<int>Q;
	for (int i = 0; i < N; ++i)Q.push(i);
	int num = 0;
	while (Q.size()) {
		//このループ一回ごとに一日で行える試合を処理していく
		int ok = 0;
		queue<int>Q2;
		while (Q.size()) {
			i = Q.front();
			Q.pop();
			if (step[i] <= num && A[i].size() && A[A[i].front()].front() == i && step[A[i].front()] <= num) {
				step[i] = step[A[i].front()] = num + 1;
				Q2.push(i);
				Q2.push(A[i].front());
				A[A[i].front()].pop_front();
				A[i].pop_front();
				M--;
			}
		}
		num++;//日数カウント
		if (M == 0)break;//全試合終了
		swap(Q, Q2);
	}
	if (M)cout << -1 << endl;
	else cout << num << endl;
	return 0;
}

他人のコード写経。理屈はわかるけどこれを本番に書ける実装力はまだないな、、
dfsと有向グラフ版、トポロジカルソートでの解き方もあるらしい