JOI2012本選2番

dp[ap=Aの何枚目か][bp=Bの何枚目か]でDPした。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[5010][5010];
int ac[5010],bc[5010];
int rec(int ap,int bp){
	if(ap<0||bp<0)
		return 0;
	else if(dp[ap][bp]!=-1)
		return dp[ap][bp];
	else{
		int r=rec(ap-1,bp);
		if(ac[ap]==bc[bp])
			r=max(r,rec(ap-1,bp-1)+1);
		return dp[ap][bp]=r;
	}
}
int main(){
	int an,bn;
	scanf("%d%d",&an,&bn);
	for(int i=0;i<an;i++)
		scanf("%d",ac+i);
	for(int i=0;i<bn;i++)
		scanf("%d",bc+i);
	memset(dp,-1,sizeof(dp));
	int ans=0;
	for(int i=0;i<an;i++)
		for(int j=0;j<bn;j++)
			ans=max(ans,rec(i,j));
	printf("%d\n",ans);
	return 0;
}

JOI2012本選1番

解説を聞いてから自分のやっていたことがRunLength圧縮と同じであると気づいた。

#include <stdio.h>
#include <vector>
using namespace std;
char in[10000000+10];
int main(){
	scanf("%s",in);
	vector<int> ch,sq;
	int c=in[0],s=1;
	for(int i=1;in[i]!=0&&in[i]!='\n';i++){
		if(c!=in[i]){
			ch.push_back(c);
			sq.push_back(s);
			c=in[i];
			s=1;
		}else{
			s++;
		}
	}
	ch.push_back(c);
	sq.push_back(s);
	int ans=0;
	for(int i=0;i+2<(int)ch.size();i++){
		if(ch[i]=='J'&&ch[i+1]=='O'&&ch[i+2]=='I'&&sq[i+1]<=min(sq[i],sq[i+2]))
			ans=max(ans,min(sq[i],sq[i+1]));
	}
	printf("%d\n",ans);
	return 0;
}

JOI2012本選まとめ

↑の大会に参加してきました。
実力を限界まで発揮できたと思います。
合宿は問題を楽しむだけにしようと思います。

JOI2011本選5番

kについて二分探索した後、その判定を頑張ってO(n)で出来るようにする。

#include <stdio.h>
#include <utility>
#include <set>
#include <algorithm>
#include <vector>
#define MAX_V 1000100

using namespace std;

int n;
int ai[MAX_V],can[MAX_V],bi2ai[MAX_V];
pair<int,int> bi[MAX_V];

int ok(int k)
{
	if(k==0)
		return 1;
	double sumA=0;
	for(int i=0;i<n;i++)
		can[i]=1;
	for(int i=0;i<k;i++)
		sumA+=ai[i];
	int lastA=k-1;
	for(int b=0;b+k<=n;b++)
	{
		if(sumA/(double)k<=(double)bi[b].first)
			return 1;
		int tP=bi2ai[b];
		can[tP]=0;
		if(tP<=lastA)
		{
			sumA-=ai[tP];
			lastA++;
			if(lastA>=n)
				return 0;
			while(!can[lastA])
				lastA++;
			sumA+=ai[lastA];
		}
	}
	return 0;
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		ai[i]=a;
		can[i]=1;
		bi2ai[i]=-1;
		bi[i]=make_pair(b,-a);
	}
	sort(ai,ai+n);
	sort(bi,bi+n);
	for(int i=0;i<n;i++)
	{
		int a=-bi[i].second;
		int tB=lower_bound(ai,ai+n,a)-ai;
		int tE=upper_bound(ai,ai+n,a)-ai;
		int tP;
		for(tP=tB;tP<tE;tP++)
			if(can[tP])
				break;
		can[tP]=0;
		bi2ai[i]=tP;
	}
	int b=0,c=n;
	while(1<c-b)
	{
		int m=(b+c)/2;
		if(ok(m))
			b=m;
		else
			c=m;
	}
	if(ok(c))
		printf("%d\n",c);
	else
		printf("%d\n",b);
	return 0;
}

SuperCon2011に参加しました

２０１１年８月２２日(月) 〜 ２６日(金)にかけて大阪大学豊中キャンパスで
SuperCon2011にチームMKとして参加してきました。
　
今回の課題は「https://www.cp.cmc.osaka-u.ac.jp/supercon/naklon.html」。
リンクをクリックして表示されるのはSIZE＝８のものですが
実際の本選はSIZE＝２５０という巨大なくろんなので全探索はできません。
　
それではどうするか。
僕達のチーム（主に僕）は２つの方針を考えました。
１：１０００手ほど乱択しそれを何度か繰り替えして最もよいものを選ぶことを何度か繰り返す
２：５手ほど全探索して評価関数で評価して最も良い手を選ぶ。
　
１は相方に実装してもらったのですがあまり結果が芳しくなかったので
僕は２を頑張っていました。
　
３日目の昼頃に評価関数を得点÷落ちた玉に変えた所
非常に結果が良かったので最後までその方針で行きました
　
結果は５位でした。
２位から５位まではほとんど同じ方針だったということなので悔しいです

Haskellで数式をパースする

使い方
　:load で読み込んだ後
　myEquation "1+2*3"

import Text.ParserCombinators.Parsec

myDigit :: Parser Char
myDigit = oneOf ['0'..'9']

myNumberString :: Parser String
myNumberString = do
	c<-myDigit
	do
			cs <- myNumberString
			return (c:cs)
		<|> return [c]

myNumber :: Parser Integer
myNumber = do
	s<-myNumberString
	return (read s)

myPlusMinus :: Parser Char
myPlusMinus = oneOf "+-"

myMultiDiv :: Parser Char
myMultiDiv = oneOf "*/"

myCalc '+' left right = (left+right)
myCalc '-' left right = (left-right)
myCalc '*' left right = (left*right)
myCalc '/' _ 0 = 0
myCalc '/' left right = (left `div` right)

myEquation :: Parser Integer
myEquation = do{ left<-myFactor; rest left }
		where
			rest l = do{ op<-myPlusMinus
					;r<-myFactor
					;rest (myCalc op l r)
					}
				<|> return l
{-<|> do{ op<-myPlusMinus
		;right<-myEquation
		;return (myCalc op x right
		}-}

myFactor :: Parser Integer
--myFactor = do{ x<-myTerm; rest x}
myFactor = do {left<-myTerm; rest left }
		where
			rest l = do{ op<-myMultiDiv
					;r<-myTerm
					;rest (myCalc op l r)
					}
				<|> return l
				{-
		left<-myFactor
		op<-myMultiDiv
		right<-myTerm
		return (myCalc op left right)
	<|>	myTerm-}

myTerm :: Parser Integer
myTerm = do
		char '('
		x<-myEquation
		char ')'
		return x
	<|> myNumber

{-

myExpr2List String->[String]
myExpr2List "" = ""
myExpr2List x:xs = if myPlusMinus 

myFactor :: Parser Integer
myFactor =
	do
		char '('
		x<-myExpr
		char ')'
		return x
	<|>	myExpr

myExpr :: Parser Integer
myExpr = do
		left<-myNumber
		do
				op<-myPlusMinus
				right<-myFactor
				return (myCalc op left right)
			<|> return left
	<|> myFactor
-}

HaskellでHTMLをパースする

使い方
　hoge.hsに下のコードを保存する。
　runghc "hoge.hs" "target.html" ※ダブルクオーテーションは必要

　このままでは空行が大量に含まれているので
　runghc "hoge.hs" "target.html" | sed '/^ *$/d'
　すると良い

--sed '/^ *$/d'
import Text.ParserCombinators.Parsec
import System.Environment

data MyTag = MakeMyTag {tagName::String,tagContent::[String]} deriving (Eq,Show)

testMyTag = MakeMyTag "aa" ["bb","cc"]

data MyHTMLContent = MakeContentChild { myLeftTag::MyTag,myContentMain::[MyHTMLContent],myRightTag::MyTag }
	| MakeTagSelf MyTag
	| MakePlainText { myText::String }
	| MakeComment
	deriving (Eq,Show)

testHTMLContent1 = (MakePlainText "dd")
testHTMLContent2 = (MakeTagSelf testMyTag)
testHTMLContent3 = (MakeContentChild testMyTag [testHTMLContent1,testHTMLContent2] testMyTag)

outputHTML (MakeComment) n = ""
outputHTML (MakePlainText "") n = ""
outputHTML (MakePlainText s) n = (sTab n++s++"\n")
outputHTML (MakeTagSelf x) n = ""
outputHTML (MakeContentChild l con r) n = sCon con (n+1)
		
sTab 0 = ""
sTab n = "  "++sTab (n-1)

sCon [] _ = "" 
sCon (x:xs) n = (outputHTML x n++sCon xs n)

main = do
	inStr<-getArgs
	tmp <- parseFromFile myHTML (head inStr)
	case tmp of
		Left err -> do {print "error"; }
		Right xs -> do {putStrLn (func xs); }

func :: [MyHTMLContent]->String
func [] = ""
func (x:xs) = (outputHTML x 0)++(func xs)

isNotEqual c = if c=='='
	then False
	else True

myDigit :: Parser Char
myDigit = oneOf ['0'..'9']

myNumberString :: Parser String
myNumberString = do
	c<-myDigit
	do
			cs <- myNumberString
			return (c:cs)
		<|> return [c]

myTagContentLeft :: Parser String
myTagContentLeft = many1 (noneOf "=>/")
-- myTagContentLeft = many1 (satisfy (\c -> c /= '='))
--myTagContentLeft = many1 (alphaNum <|> char ':')
{-where
		rest = do{ x<-satisfy (\c -> c /= '=')
				; xs<-rest
				; return (x:xs) 
				}
			<|> return ""
-}

myTagContentRight :: Parser String
myTagContentRight = do
		lD<-char '"'
		mD<-inC
		rD<-char '"'
		return ([lD]++mD++[rD])
	<|> myNumberString
		where

			inC = do{ x<-satisfy (\c -> c /= '"')
					; xs<-inC
					; return (x:xs)
					}
				<|> return ""

myTagContent :: Parser String
myTagContent = do
	left<-myTagContentLeft
	char '='
	right<-myTagContentRight
	return (left++"="++right)

myTagName :: Parser String
myTagName = many1 alphaNum

myEndTag :: Parser MyTag
myEndTag = do
	string "</"
	many space
	name<-myTagName
	many space
	char '>'
	return (MakeMyTag name [])

myBeginTag :: Parser MyTag
myBeginTag = do
	char '<'
	name<-myTagName
	many space
	tagContent<-many p
	char '>'
	return (MakeMyTag name tagContent)
		where
			p = do
				r<-myTagContent
				many space
				return r

mySelfTag :: Parser MyTag
mySelfTag = do
	char '<'
	name<-myTagName
	many space
	tagContent<-many p
	string "/>"
	return (MakeMyTag name tagContent)
		where
			p = do
				r<-myTagContent
				many space
				return r

myComment :: Parser MyHTMLContent
myComment = do
		string "<!--"
		rest "aa"
		char '>'
		return MakeComment
	-- <?> "myComment"
	
	where 
		rest before =
			if before == "--"
			then return ()
			else do
				x<-anyChar
				rest (tail before++[x])
				
myContent :: Parser MyHTMLContent
myContent = do {p<-many1 (satisfy (\c-> c/='<')); return ( MakePlainText p)}
	<|> myBeginAndEndTag
		<|> do  {t<-try mySelfTag; return (MakeTagSelf t)}
		<|> try myComment
		<?> "myContent"

{--myContent = try( do {b<-myBeginTag; l<-myContentList; e<-myEndTag; return  (MakeContentChild b l e)})
		<|> try( do  {t<-mySelfTag; return (MakeTagSelf t)})
		<|>  do {p<-many1 (satisfy (\c-> c/='<')); return ( MakePlainText p)}--}

myBeginAndEndTag :: Parser MyHTMLContent
myBeginAndEndTag = do
	b<-try myBeginTag
	l<-myContentList
	e<-myEndTag
	if tagName b == tagName e 
		then return (MakeContentChild b l e)
		else fail $ "tag don't match "++tagName b++" and "++tagName e
	
myContentList :: Parser [MyHTMLContent]
myContentList = (do	{ r<-myContent; l<-myContentList; return ([r]++l)})
			<|> do return []
--myContentList = try (do	{r<-myContent; many myComment; l<-myContentList; return ([r]++l)})

myHTML :: Parser [MyHTMLContent]
myHTML = do
	x <- myContentList
	eof
	return x