owned this note
owned this note
Published
Linked with GitHub
# ICPC2017 模擬予選
### トーク欄
コード提出前にここに貼るなどしますかす ←急にDisってんなこいつ
dekita
↑プロ
## 解法
### A
めいろ
それぞれの難易度について、推薦度最大のを持ってれば良さそう
とりあえず解きます
### B
らずひるど
L以上のあたいの時からD秒間いもす O(N)
これ解きます
### C
いずらいと
各参加者の得点の最大と最小の差の最大値を求めれば解ける
やるだけっぽい
誤読してた!w←ウケる
DP?
わからずといったかんじです
一人の最大得点を求めた時の残りの人の最小得点を求めたい…
### D
めいろ
にぶたんっぽい
ぼくもにぶたんっぽさを感じました
判定にO(nm)かかってしまうきがするので課題はそこですか
どんよくに判定したらなんか行けた
不可能とM以上の違いを区別していなかった
### E
らずひるど
かけきくけこかこ幾何殺す
させしすせそさそスルーします
多分グラフ構築してN^2ダイクストラ
グラフ構築が無理なので終了
### F
いずらいと
よくわからない 制約が小さい
やるだけ説ある
なんかこれも最大マッチングの気配を感じませんか?
うまいこと2部マッチングに持ち込むのかな
フロー全然知らないマンです…
### G
めいろ
条件を満たす塊ごとに分けて組み合わせエイで行けるかなあ
基本的にはペアのやつしか、一緒に出しちゃいけない割当には関係しない
### H
らずひるど
問題が頭に入らない
最大マッチング問題の雰囲気を感じた
問題を 読み間違えて おりました(575)(Hじゃなかった)
迷路くんの問題です
わからない(チーン)
dfsしながら到達可能か調べて行く感じで枝刈りくらいしか思いつかなかった
無理そう
## コード
### A
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
int N, M;
while(cin >> N >> M && N && M){
int max_v[101] = {}; //max_v[i] := 難易度iの問題の推薦度の最大値
for(int i = 0;i < N;i++){
int d, v;
cin >> d >> v; d--;
max_v[d] = max(max_v[d], v);
}
int res = 0;
for(int i = 0;i < M;i++){
res += max_v[i];
}
cout << res << endl;
}
return 0;
}
```
### B
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int T, D, L;
while (cin >> T >> D >> L, T + D + L) {
int imos[101010] = {0};
int x;
for (int i = 1; i <= T; ++i) {
cin >> x;
if (x >= L) {
imos[i + 1]++;
imos[i + D + 1]--;
}
}
for (int i = 1; i <= T; ++i) {
imos[i] += imos[i - 1];
}
int ans = 0;
for (int i = 0; i <= T; ++i) {
if (imos[i]) ans++;
}
cout << ans << endl;
}
}
```
### C
解けてない
頑張れ
複数データセットなのでaが危険
こうですか?
↑そうですね、すみません
○
えぇ... はい
草
かっこが対応してなかった 直しました
直ってなかった 直しました2
なんかDPの気配を感じませんか
なにをDPするんだろう(いやそこが本質なんだよな)
O(M^2) で解けそう(非DP)←O(N^2)だったのでダメです
や、これローカル実行でOKなんだっけ←おk
↑というかローカルで実行ですね
サンプルが合いました
```cpp
#include <bits/stdc++.h>
using namespace std;
signed main()
{
int n, m;
while (cin >> n >> m, n + m) {
int only[10010] = {0};
int S[1010] = {0};
int a[10010] = {0};
for (int i = 0; i < m; ++i) {
cin >> S[i];
int k; cin >> k;
if (k == 1) {
int c; cin >> c;
--c;
only[c] += S[i];
a[c] += S[i];
} else {
for (int j = 0; j < k; ++j) {
int c; cin >> c;
c--;
a[c] += S[i];
}
}
}
int ans = -1;
for (int i = 0; i < n; ++i) { // i = 最大にする人
int ma = a[i];
int mi = 2e9;
for (int j = 0; j < n; ++j) { // j = 最小にする人
if (j == i) continue;
mi = min(mi, only[j]);
}
ans = max(ans, ma - mi + 1);
}
cout << ans << endl;
}
}
```
### D
```cpp
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0;i < (n);i++)
int N, M;
int s[114514];
bool ok(int X){
int res = 0;
int now = 1;
if(now+X <= s[0]) return false;
REP(i, N-1){
if(now+X > s[N-1])
return res+1 < M;
while(now-X < s[i] && abs(s[i]-now) < abs(s[i+1]-now) && now+X <= s[N-1]){
res++;
now += max(1, X-abs(now-s[i]));
}
if(now-X >= s[i] && now+X <= s[i+1]){
res += min(s[N-1]-X+1, s[i+1]-X+1)-now;
now = min(s[N-1]-X+1, s[i+1]-X+1);
}
}
return res+1 < M;
}
int main(void){
while(cin >> N >> M && N && M){
REP(i, N)
cin >> s[i];
int l = 1, r = s[N-1]+1, m;
while(r-l > 1){
m = (l+r)/2;
if(ok(m)){
r = m;
}else{
l = m;
}
}
bool correct = false;
for(int i = r+1;i >= max(1, l-1);i--){
if(!ok(i) && ok(i+1)){
cout << i << endl;
correct = true;
break;
}
}
if(!correct)
cout << -1 << endl;
}
}
```
### E
```cpp
```
### F
```cpp
```
### G
```cpp
```
### H
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m;
char maze[16][20000];
char c[1010][16][16];
const int dy[4] = {0, 1, -1, 0};
const int dx[4] = {1, 0, 0, -1};
// v番目のcを時計回りに回転
void rotate(int v) {
char p[16][16];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
p[i][j] = c[v][i][j];
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
c[v][j][n - 1 - i] = p[i][j];
}
}
}
// x が v * n + 1に到達できたらtrue
bool izryt(int v, int y = 0, int x = 0) {
if (maze[y][x] == '#') return false;
if (x == v * n + 1) return true;
for (int i = 0; i < 4; ++i) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || n <= ny) continue;
if (izryt(v, ny, nx)) return true;
}
return false;
}
// v番目のcをmazeに回転させながらマージ
bool dfs(int v = 0) {
if (v == m) return true;
// 回転数4
for (int i = 0; i < 4; ++i) {
// mazeにコピー
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
maze[j][v * n + 1 + k] = c[v][i][j];
}
}
// 次に到達できたらtrue
if (izryt(v)) {
if (dfs(v + 1)) return true;
}
rotate(v);
}
return false;
}
int main() {
while (cin >> n >> m, n + m) {
// ただの初期化です
for (int i = 0; i < 16; ++i)
maze[i][0] = maze[i][n * m + 1] = '.';
for (int i = 1; i < 16; ++i)
for (int j = 0; j < 20000; ++j)
maze[i][j] = '#';
// 入力
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
for (int k = 0; k < n; ++k)
cin >> c[i][j][k];
cout << (dfs() ? "Yes" : "No") << endl;
}
}
```