読者です 読者をやめる 読者になる 読者になる

RUPCあとで解いた

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;
	}
}

F Farey Sequence

Wikipedia安定。もしくはシミュレーションしてOEISか。使えないと難易度いきなり上がる。

ソースをなくしてしまったけど、ややエラトステネスっぽい↓みたいな方法をとると一気にφ関数求めれる。まあTL的にrose鯖強いので、1つ1つ包除原理で求めても通る。

500 Internal Server Error

G Water Clock

幾何恐いのであまり見ていない。あーいう図が出てきた時点で泡吹いて死ぬ。出題者には申し訳ないと思へど。


H Oh, My Goat!

別記事にした

AOJ 2288 Oh, My Goat! - kyuridenamidaのチラ裏


I Custom Painting Master

これはさらに見るだけで泡吹くレベル。曲線は精神にヤバイ。