RUPCあとで解いた - kyuridenamidaのブログ

PCKの悲しい処理をしていて貴重なコンテストであるRUPCに参加できなかったので、解いてみた。

自分の実力にはちょうどよいコンテストだった気がします。幾何は読んでません。あとリーディングハード多かったです。

A Swap Cipher

これはPCK開始直前に解いたんだけど、パニくって時間食った。しかも1WAした。

逆順に舐めるっていうのに気づかなくて悩んでた。むず。

ソースなくした

B Problem B

読んだけど頭が悪いのでよくわからなかった。とばし。

C Seishun 18 Kippu

途中で合流するとしか思えなかった問題文でした。サンプルがどうしても意味が分からなかったので参加者のブログで意図を汲み取る。2D好きな人が動く気ないので大激怒。

WFで通るらしく、やはりWFの定数項の軽さあまり舐めないほうがいいらしい。これからコンテストにおいてどうしようかな。反省。

ソースなくしたけどダイクストラで解いた。WFで解こうか悩んだがやめた。

D The Legendary Sword

厨二な問題文で胸焼けしてしまった。まあサンプル見ると分かりやすい。

>数字は1以上の整数であり、間の数字に抜けはないとしてよい。

がトラップかと思ってた。S-3-4-5-6-Gとかいう悪質なケースがあると思っていたということ。

とりあえずw+h<=100より50*50が最大なので2500個くらい確保したらよいことが分かる。あと盤面で情報は持たずに、数字毎に複数ある座標保持しておく。

マンハッタン距離とかほげほげする。まあ簡単なパチモンクリーチャーみたいな感じ。

実装楽なメモ化再帰安定。SとGを0番目とn+1番目にして解くとさらに楽だった(小学生並みの解法)

学校に忘れた。かなしい。

E Anipero

DPする。最初サンプル勘違いしてて、シークレットに出ることもできるが一般で出ることもできるパターンがあると思っていて複雑な実装してMLE。かなしい。結局DPした。汚いソース。これはソースある。

#include <iostream>
#include <map>
#include <cstring>
using namespace std;

int x[100],y[100],sx[100],sy[100],n;

int lim , N , M , X;

int dp[2][1001][101];
int main(){
	while(cin >> lim >> N >> M >> X && lim){
		for(int i = 0 ; i < 2 ; i++)
			for(int j = 0 ; j <= lim ; j++)
				for(int k = 0 ; k <= M ; k++)
					dp[i][j][k] = -99999999;
		for(int i = 0 ; i < N ; i++){
			string t; cin >> t;
			cin >> sx[i] >> sy[i];
		}
		for(int i = 0 ; i < M ; i++){
			string t; cin >> t;
			cin >> x[i] >> y[i];
		}
		dp[0][0][0] = 0;
		
		for(int i = 0 ; i < M ; i++){
			for(int j = 0 ; j <= lim ; j++){
				for(int k = 0 ; k <= M ; k++){
					dp[i&1^1][j][k] = dp[i&1][j][k];
				}
			}
			for(int j = 0 ; j+x[i]  <= lim ; j++){
				for(int k = 0 ; k < M ; k++){
					dp[i&1^1][j+x[i]][k+1] = max( dp[i&1^1][j+x[i]][k+1] , dp[i&1][j][k] + y[i]);
				}
			}
		}
		int memory[1001]={0};
		for(int w = 0 ; w <= lim ; w++){
			for(int z = X ; z <= M ; z++){
				memory[w] = max(w?memory[w-1]:0,max(memory[w],dp[M&1][w][z]));
			}
		}
		int ans = 0;
		for(int i = 0 ; i < N ; i++)
			for(int j = i+1 ; j < N ; j++){
				int rem = lim - sx[i] - sx[j];
				if(rem>=0) ans = max(ans,sy[i]+sy[j]+memory[rem]);
			}
		for(int i = 0 ; i < N ; i++){
			int rem = lim - sx[i];
			if(rem>=0) ans = max(ans,sy[i]+memory[rem]);
		}
		cout << ans << endl;
	}
}