UTPC 2011
出てきました。
600点で25位となかなか満足できる結果でした。
問題は、文章、質ともに非常に良い物でとても楽しかったです。
A,Bはあまりにもやるだけなので飛ばして、C以降のちょっとでも考えた問題について書く。
ソースは競技プログラミングのテンプレートとして、これを用いているので以下のコードでは省略。
#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<map> #include<set> #include<queue> #include<cstdio> #include<climits> #include<cmath> #include<cstring> #include<string> #include<sstream> #include<numeric> #include<cassert> #define f first #define s second #define mp make_pair #define REP(i,n) for(int i=0; i<(int)(n); i++) #define rep(i,s,n) for(int i=(s); i<(int)(n); i++) #define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++) #define ALL(c) (c).begin(), (c).end() #define IN(x,s,g) ((x) >= (s) && (x) < (g)) #define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h))) #define print(x) printf("%d\n",x) using namespace std; typedef unsigned int uint; typedef long long ll; const int _dx[] = {0,1,0,-1}; const int _dy[] = {-1,0,1,0};
問題 C - iwi
…iwi… （…は [, ], {, }, (, )のいずれか）
という文字列が与えられる。
これらの部分列をとり、左右対称な文字列をつくると、最大何文字の部分列が取れるか。
という問題。
iwiの左右の文字について、右の文字を反転させておき、
競技プログラミング御用達の最長共通部分列で計算するだけ。
以下コード。
int memo[20][20]; string s1,s2; int solve(int a, int b){ if(a == s1.size() || b == s2.size()) return 0; if(memo[a][b] != -1) return memo[a][b]; int ret = 0; ret = max(ret, solve(a+1, b)); ret = max(ret, solve(a, b+1)); if(s1[a] == s2[b]) ret = max(ret, 1 + solve(a+1, b+1)); return memo[a][b] = ret; } int main(){ string str; char m[256]; m['['] = ']'; m[']'] = '['; m['{'] = '}'; m['}'] = '{'; m['('] = ')'; m[')'] = '('; cin >> str; int pos = str.find("iwi"); REP(i,20) REP(j,20) memo[i][j] = -1; s1 = str.substr(0, pos); s2 = str.substr(pos+3); reverse(ALL(s2)); REP(i,s2.size()) s2[i] = m[s2[i]]; print(3 + 2 * solve(0, 0)); return 0; }
問題 D - 停止問題
独自のプログラミング言語で記述された、プログラムが停止する可能性があるかを調べる問題。
詳細は原文を読んでください。
Cまでの簡単さ的に、シミュレーションするだけだと思ったのだが、書いている途中で、
- '?' … 実行の向きが上下左右のいずれかにランダムに等確率で変更される．
と書いてあり、それではできないことに気づく。
でも、メモリ、現在位置、向いている方向、でメモ化してDFSすればいいだけなので、あまり変更の必要が無くて助かった。
以下コード
enum dir{ Dup = 0, Dright = 1, Ddown = 2, Dleft = 3 }; bool memo[16][4][20][20]; vector<string> g; int r, c; bool solve(int m, int d, int y, int x){ if(memo[m][d][y][x]) return false; memo[m][d][y][x] = true; switch(g[y][x]){ case '<': d = Dleft; break; case '>': d = Dright; break; case '^': d = Dup; break; case 'v': d = Ddown; break; case '_': if(m == 0) d = Dright; else d = Dleft; break; case '|': if(m == 0) d = Ddown; else d = Dup; break; case '?': REP(i,4){ int xx = (x + c + _dx[i]) % c; int yy = (y + r + _dy[i]) % r; if(solve(m, i, yy, xx)) return true; } return false; case '.': break; case '@': return true; break; case '+': m = (m + 1) % 16; break; case '-': m = (m + 16 - 1) % 16; break; default: if(!isdigit(g[y][x])){ printf("error %c\n", g[y][x]); exit(0); } m = g[y][x] - '0'; break; } x = (x + c + _dx[d]) % c; y = (y + r + _dy[d]) % r; return solve(m, d, y, x); } int main(){ cin >> r >> c; g = vector<string>(r); REP(i,r) cin>>g[i]; puts(solve(0, Dright, 0, 0) ? "YES" : "NO"); return 0; }
問題 E - ファーストアクセプタンス
簡単に説明すると、
問題ごとに締切り(何分後までみないな)と、自分がやるとかかる時間(何分かかるみたいな)が分かっている。このとき最大何個の締切りを守れるか。
という問題。
最初は、ビットDPのようなものをするのかと思ったが、問題数が1 ≤ N ≤ 1000となっており、全然ムリ。
PKUで解いた、牛が積み重なっていくみたいな問題に似ている気がするので、貪欲に近い方法でできるような気がする。
ということで、とりあえず締切りが近い順番にソートしてみる。
考えていると、次のことに気づく。
もし、AとBの締切りが、「Aの締切り→Bの締切り」という順番だとする。するとB→Aの順番に問題を解いて、かつ両方締切りに間に合うとすると(締切りに間に合わない問題はそもそも解かなくていい)、A→Bの順番に説いても両方締切りに間に合う。これは、仮定からBとAを両方解いてもAの締切りより早く解けているので自明。
つまり、締切りが近い問題から順番に解くかとかないかを決めていけば良い。
あとは、今までに解いた問題数ごとに、最短時間をDPで計算していく感じ。
以下コード。
pair<int,int> ba[1010]; int memo[2][1010]; int main(){ int n = getInt(); REP(i,n){ ba[i].s = getInt(); ba[i].f = getInt(); } sort(ba, ba+n); int *now = memo[0]; int *next = memo[1]; REP(i,n) now[i] = INT_MAX; now[0] = 0; REP(i,n){ REP(j,n+1) next[j] = INT_MAX; REP(j,n){ if(now[j] != INT_MAX){ int t = now[j] + ba[i].s; next[j] = min(next[j], now[j]); if(t <= ba[i].f) next[j+1] = min(next[j+1], t); } } swap(next, now); } int ans = 0; REP(i,n+1) if(now[i] != INT_MAX) ans = i; print(ans); return 0; }
多分普段なら解けるかも微妙なレベルの問題だが、なんか割と早く解けた。調子良かったのかも。
問題 G - プログラミングコンテストチャレンジブック
整数がたくさん与えられ、そっから６つの整数を選び(重複無し)、三角形を２つ作る。このときそれらの整数の和の最大値は？という問題。
和を最大にしたいので、とりあえず入力列を大きい順にソートしておく。
まず前提として、三角形の辺の長さを長い順にa, b, cとすると
a - b < c
を満たさないと三角形が作れない。
つまり、a - bは小さいほうがよく、cは大きいほうが良い。
つまり、b, cは大きいほうがよい。
Aa, Ab, Acを三角形Aに使う整数、Ba, Bb, Bcを三角形Bに使う整数、Oをその他の整数として、
O・・・O Aa Ab Ba O O Bb Bc Ac O・・・O
になったとする。
これでA, Bともに三角形が作れたとすると、上記の性質から
O・・・O Aa Ab Ba Bb Bc Ac O O O・・・O
でも三角形が作れる。つまり、選んでくる整数は6つ連続している場所だけでいい。
と思ってしまったのが間違いで、これでWAを２，３回食らった。
実は離れている場所でも三角形は作れて、どういう場合かというと、
O・・・O Aa Ab Ac O O Ba Bb Bc O・・・O
のような場合である。Aが３つ連続、Bが３つ連続という場合には間が離れる場合がある。
こっちのほうが先に思い浮かびそうなもんだが、何故かなかなか気付かなかった。
あとは、この２つの場合で、最大になるパターンを探してくるだけ。
以下コード
ll a[100000]; ll memo[100000]; int main(){ int n; cin >> n; REP(i,n) cin>>a[i]; sort(a, a+n, greater<ll>()); ll ans = 0; for(int i = 0; i + 5 < n; i++){ int arr[6] = {0, 0, 0, 1, 1, 1}; ll *aa = &a[i]; do{ ll t1[3]; int tt1 = 0; ll t2[3]; int tt2 = 0; REP(i,6){ if(arr[i] == 0) t1[tt1++] = aa[i]; else t2[tt2++] = aa[i]; } if(t1[0] - t1[1] < t1[2] && t2[0] - t2[1] < t2[2]){ ans = 0; REP(j,6) ans += aa[j]; goto end; } }while(next_permutation(arr, arr+6)); } end:; for(int i = 0; i + 2 < n; i++){ ll *aa = &a[i]; if(aa[0] - aa[1] < aa[2]){ memo[i] = aa[0] + aa[1] + aa[2]; }else{ memo[i] = 0; } } for(int i = 0; i + 5 < n; i++){ if(memo[i] != 0){ for(int j = i + 3; j + 2 < n; j++){ if(memo[j] != 0){ ans = max(ans, memo[i] + memo[j]); goto end2; } } } } end2: cout << ans << endl; return 0; }
なお、memoは完全にいらない。
本番はもう一つ勘違いしていて、goto end2;ができず、全パターン試さないといけないと思っていたために書いた無駄コード。
F - 全域木
完全グラフから、枝を重複しない全域木を何個つくれるかという問題。
シーケンスの操作だけでできないか、と考えていたが結局できなかった。
解説にあった再帰的な解法は、途中で一瞬頭をよぎったが、どこで分割するかなど複雑な問題がありそうでやめてしまった。
問題 I - ビット演算
f(x) = y
という対応を何個か与えられたときに、+, -, *, |, &, ^, ~の演算だけで関数を作れという問題。
例えば
f(1)=2, f(2) = 4
が与えられたときには、(x*2)を返せば良い。
なお数値は、xか32bit unsiged integerのどちらか。
最初の方針は、対応は８個までで掛け算を使えるというところから、
f(x) = a * (x**7) + b (x**6) + ... + h (x**k は xのk乗)
の形にできると思い、連立方程式をとくプログラムを書く。
どう考えても、係数が小数になります本当に(ry
つぎの方針は、
if(x==a) return b
else ...
をビット演算でやろうとする。
つまり(x==a)*b + (x==c)*d ...
のような式をかえしたい、そのためには==を上記の演算子でやらなければならない。
0 => 1
0以外 => 0
にするビット演算が思い浮かばない。というか不可能な気が(ry
という感じで結局解けませんでした。
それ以外の問題
読んだけど、全く方針が立たなかった。
