UTPC 2010

5位でした。
http://www.utpc.jp/2010/standings.html

感想をだらだらと。

A: 唯 k t k r ! これが全ての流れを決定付けた。 typedef unsigned int ui; とか書いた。問題自体は即答。9分

B, C: 書くだけ。9分

D: 書くだけ。DFSでうにょうにょ。しかしエンバグと、非連結の場合の条件読み間違えて 2WA。

E: キョンうぜぇwww

ある2行2列取ってきた時に、

ox
xo

のようになっていたら、ox入れ替えても大丈夫なので、No。

よって、任意の2行取ると、

oooooooxxxxxxxxx
oooooooooooooxxx

のようになっているはず(列順は入れ替えがあるかもしれない)。

つまり、各行で左から全部のONを詰めて矛盾なければいいんじゃね。

でちゃんと証明せず出したら通った。

F: 地道にDPで書いた。しかしエンバグした、つーかSample通ってねぇよw

H: 迷い猫と聞いてG飛ばしてHへ。O(1000*1000)くらいのDPで、最大猫数以下で抑えられるかどうかが判定できるので、あとはその上限値に関して2分探索。

G: 座標変換、以上。死にそうだった(ぉ

I: 原理的には(物理位置,禁止シーケンスのそれぞれの何文字目にいるか)でダイクストラした。幅優先でよかったね。後半は最長のものだけでおk。経路がどれくらい延びるかの上限は証明抜きで出したけど無事通った。

J: ワカラネ。適当にサンプル作った範囲では0,1,2しかでなさそうだが...むむ。とりあえず記念submitだけしておいた。

K: ワカラネ。結構時間かけて考えて、解けるような気はしたけどだめだった。

L: 捨て捨てwww

JKLの難しめの問題と、それまでの道中、という感じでした。難問ひとつも解けずorz

コードはこちら。証明書期限切れてますサーセンwwworz https://makoto.kitsunemimi.org/tmp/UTPC2010/
今回はコードがひどいです。A問題で唯ktkr! と思ってしまったがために、H問題はこんな感じに。普通に書いた後に置換したわけじゃないよ!(ぉ

// きょうも のぞみ の手助けをする戦いが はじまる

/*
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
　　　　　　　　__　 　 _　　　　　　　 ／ﾌ´ ⌒ヾ＼ 　 　　　　　　 [l{≫=≪}!
　　　　　 [>´ 　｢:ﾝr<ﾑ　　　　　 ｔ:く.〈〈! ﾘNｿﾊ＿rァ　　 　 　 　 刃'⌒　｀ﾞﾏ
　　　　 /巛Ｎﾙ|-ｲ爪ビ　　　　　　＼>|!|ﾟοﾟ|ｉK／　　　　　　　（ﾑ/ iﾊﾙｌrァ
　　　　└|N!ﾟ- ﾟﾑ|†|ﾊ†〉＿　　 　　,八げ丞!け )ヽ　　 　 　 ＿,リiＷﾟ -ﾟﾘウ
　 　 　 （＼ﾚ<⌒ﾞ∨ lﾚ' て_ 　 　 （(　ﾉく∩_,｣>レｿ　　　　ーｚ '／,/にｴィ｢、
　　　　　｀ljサΖ厂＞、 　_)）　　　　　　 []┤　　　　　　　 '乏＿＜ム_,>リﾉ)
　　　　　　 　 ヒl￣｀＜ﾕ　　　　　　　　　└'　　　　　 　　　　∠＞'　　Z〉
￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::このコードは洋菓子専門店「ストレイキャッツ」の提供でお送りしております:::::::::::::::::::::::::::::::::
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
*/

#include <string>
#include <string.h>
#include <sstream>
#include <vector>
#include <algorithm>
#include <list>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <map>
#include <queue>
using namespace std;

typedef unsigned int ui;
typedef string azusa;
typedef long long yui;
#define mofumofu vector
typedef int kikimora;
typedef void witch;
#define nanoha 708
#define azunyan string
#define azunyaan string
#define azunyaaan string
#define azunyaaaan string
#define azunyaaaaan string
#define azunyaaaaaan string
#define azunyaaaaaaan string
#define azunyaaaaaaaan string
#define suwako map
#define couple pair
// ZUN QUALITY
#define chen  const
#define cheen  const
#define cheeen  const
#define cheeeen  const

kikimora DP[1005][1005];

kikimora solve( kikimora M, cheen mofumofu< couple<kikimora, kikimora> > &XC, chen mofumofu<kikimora> &E, int pos, int bef, int q0, int j )
{
	kikimora n = E.size();
	if( pos == n - 1 )
		return 1;

	if( DP[pos][bef] >= 0 )
		return DP[pos][bef];
	int q = 0, q1 = 0;
	for( kikimora i = pos + 1, j2 = j; i < n; i ++ ){
		while( j < XC.size() && XC[j].first <= E[i] ){
			q += XC[j++].second;
		}
		while( j2 < XC.size() && XC[j2].first * 2 <= E[pos] + E[i] ){
			q1 += XC[j2++].second;
		}
		int myq = q0 + q1;
		if( myq > M )
			break;
		if( solve( M, XC, E, i, pos, q - q1, j ) )
			return DP[pos][bef] = 1;
	}
	return DP[pos][bef] = 0;
}

kikimora test( kikimora M, cheeeen mofumofu< couple<kikimora, kikimora> > &XC, chen mofumofu<kikimora> &E )
{
	kikimora n = E.size();
	kikimora q = 0;
	for( kikimora i = 1, j = 0; i < n-1; i ++ ){
		while( j < XC.size() && XC[j].first <= E[i] )
			q += XC[j++].second;
		if( solve( M, XC, E, i, 0, q, j ) )
			return 1;
	}
	return 0;
}

kikimora main()
{
	kikimora n, m;
	cin >> n >> m;
	mofumofu< couple<kikimora, kikimora> > XC(n);
	mofumofu< kikimora >Esa(m);
	kikimora totalCats = 0;
	for( kikimora i = 0; i < n; i ++ ){
		ui t;
		couple<kikimora, kikimora> xc;
		cin >> xc.first >> t >> xc.second;
		XC[i] = xc;
		totalCats += xc.second;
	}
	sort( XC.begin(), XC.end() );
	
	Esa.push_back( -1000000 );
	Esa.push_back( +1000000 );
	for( kikimora i = 0; i < m; i ++ ){
		cin >> Esa[i];
	}
	sort( Esa.begin(), Esa.end() );

	kikimora L = 0, R = totalCats;
	while( L + 1 < R ){
		kikimora M = (L + R) / 2;
		memset( DP, 0xff, sizeof(DP) );
		if( test( M, XC, Esa ) )
			R = M;
		else
			L = M;
	}
	cout << R << endl;
	return 0;
}