2016-11-24

ACM-ICPC 2016 国内予選 D : ダルマ落とし

問題

配列の隣り合った2つ要素の差が1以下であれば，その2つ要素を消すことができる．
この操作を繰り返す時，最適に消していくと，最大何個要素を消せるか．

例：{1,3,2,1}が与えられたとき
{1,3,2,1} -> {1,1} -> {}　　⇐4個消せる
{1,3,2,1} -> {1,3}　　　　⇐先に右端の要素の2,1を消すと，2個しか消せない

制約

配列の長さ <= 300
1 <= 要素の値 <= 1000

Daruma Otoshi | Aizu Online Judge

方針

dp[ l ][ r ] := [ l , r ]の区間で最大いくつ取り出せるか
とすると，

ある幅dに対して，
① {1,2,3,4} -> {x,x,o,o}
dp[ l ][ l + d ]より小さい区間のdpが求まっているとすると，
dp[ l ][ l + d ] = max{ dp[ l ][ k ] + dp[ k + 1 ][ l + d ] }
となりそう．

② {1,3,3,1} -> {1,x,x,1} -> {o,x,x,o}
dp[ l ][ l + d ] = d + 1　（oの間のxの要素が全部消えてる）
かつ
abs( x[ l - 1] - x[ l + d + 1] ) <= 1　（端にあるoの要素の差が1以下）
であれば，
dp[ l - 1 ][ l + d + 1 ] = d + 1 + 2　（間の要素数+2）
となりそう．

良い感じにループを回す．

コード

#include <bits/stdc++.h>
using namespace std;

bool solve(){
	int n;
	cin >> n;
	if(n == 0)return false;
	vector<int> x(n);
	for(int i=0;i<n;i++)
		cin >> x[i];

	vector<vector<int>> dp(n+1,vector<int>(n+1));
	for(int i=0;i<n-1;i++){
		if( abs( x[i] - x[i+1] ) <= 1 )
			dp[i][i+1] = 2;
	}

	for(int d=1;d<n;d++){
		for(int l=0;l<n;l++){
			if( l + d >= n )continue;
			for(int r=l;r<l+d;r++){
				dp[l][l+d] = max(dp[l][l+d], dp[l][r] + dp[r+1][l+d]);
			}
			if( l - 1 >= 0 && l + d + 1 < n){
				if( dp[l][l+d] == d + 1 && abs( x[l-1] - x[l+d+1] ) <= 1 ){
					dp[l-1][l+d+1] = max(dp[l-1][l+d+1] ,dp[l][l+d] + 2);
				}
			}
		}
	}
	cout << dp[0][n-1] << endl;
	return true;
}

int main(void){
	while(solve()){}
	return 0;
}

半年放置したらなんとか解けた．

2016-06-25

ICPC国内予選参加記 2016

ICPC国内予選に参加しました。
順位は、95位でした。

今年はあんまり参加する気はなかったのですが、ICPCが近づくとやっぱり出たくなりました。
チームメンバー集めは、4月ぐらいから始めて、5月頃メンバーが決まって、それから週1ぐらいで過去問を解いて練習。

僕以外は初参加だったのですが、A,B,Cまでは一人一問比較的スムーズに解くことができたので、
一応、最低限の目標は達成できたかなと思います。

その後は、D問題に絞ってウンウン唸っているだけでした。
区間DPだろうなとは思ったのですが、そこから何も思いつきませんでした。
完全に過去の問題の復習不足で、後悔しかないですね。
SRMで出てた括弧の問題とかちゃんと解いとけばなぁとかずっと考えていました。

僕は来年が最後なので、来年はもっと早くメンバーを集めて、ちゃんと復習して、国内予選を突破したいです。

2016-06-18

応用情報技術者試験合格しました

合格しました

応用情報技術者試験についてはリンク参照．
IPA 独立行政法人情報処理推進機構：制度の概要：応用情報技術者試験
得点は，午前・午後共に8割程度で，割りと余裕がありました．

午前

自分は，情報系の学生であるものの，授業でやった基本的な部分ですら，覚えてたり，覚えてなかったりしました．
ということで，基礎を固めるため，適当な対策テキストを借りて，半分ぐらい読みました．

その後，面倒臭くなり試験3日前ぐらいまで放置．
本を読む気力がなかったので，そこからはずっと過去問道場で過去問を解いてました．
応用情報技術者過去問道場｜応用情報技術者試験.com

午前試験は，過去問から結構出てる感じがあり，最悪それだけやってれば受かりそうだと思いました．

午後

対策せず．
全体を読んで，簡単な問題を探して解きました．
これ国語の問題でしょみたいなのもあったので，そんなにガッツリ対策はしなくて平気そうです．
あと，時間的にはかなり余裕があり，そこで焦る必要はないと感じました．

感想

数年振りに資格試験的なものを受けたので，だいぶ緊張しました．
twitterで受験費をつぶやき，固定ツイートにしておくと，モチベが上がるのでオススメです．
次はネスペを目指します．

2016-04-11

ビームサーチの練習用にパズドラAIを組んだ

大学の先輩がパズドラのコンボのAIの話をしていて，そういえば組んだことがないなぁと思い立ち．

目的

パズドラのパズルにおいて，コンボ数をできるだけ大きくするようなパズルのスライドのさせ方を出力する．
今回は，ダメージ等については考慮しません．

方針

ビームサーチを使います．”ビームサーチ”で検索すれば良い記事が沢山出てくると思うので，詳細は割愛．

ビームサーチは下のをそのまま実装しました．

とりあえずビームサーチってこんな感じなんですよ。とりあえずまずこれが解るのが前提。https://t.co/uivkCk4LMD pic.twitter.com/ro4m5WhybE
— chokudai(高橋直大) (@chokudai) 2016年3月27日

状態は，｛”パズルの盤面の状態”，”今動かしている部分の座標”，”何手動かしたか”｝とし，パズルを1手動かした状態を遷移状態としています（上下左右で4つの状態に遷移）．
コンボ数をそのまま状態の評価値として扱います．

初期状態は，パズルをスライドさせるスタートの位置を変えたもの，計30個に設定．
また，ビーム幅は40000，最大ターンは12として実行します．

ZobristHashで盤面のハッシュ値を生成し，同じ盤面を2回探索しないようにしています（出来てるかは謎）．

deleteしてないからヤバそうなC++コード
https://ideone.com/MbxQOR

まとめ

サクサクっと作った割には5,6コンボ出るので，凄いと思いました．
適当に作ったので（言い訳），全てにおいて杜撰なコードになっています．

記事の書き始めた時はもっとしっかり書こうと思っていたんだけど，途中で面倒くさくなってしまった．

2016-02-08

グラフ理論系の好きな問題 5選

最近何もする気が起きないので，今までに見た数少ない問題の中で好きだった問題を紹介します（脚注にネタバレ）．

まとめ

グラフ理論系の問題は実装が楽しいものが多くて好きです．
なんか最近の問題が多くて申し訳ない感じになりました．
手を付けてない組み合わせ系の問題に取り組みたい．

以下，問題の解法ネタバレ．

*1:二分探索

*2:最短経路問題

*3:フロー

2016-01-15

2016年の目標

競技プログラミング

・Topcoder/Codeforcesの問題を解く．
・Div1入り

英語

・TOEIC 730点以上
・単語帳やる

その他

・何か2つ作る

課題を締切直前までやらずにいて痛い目を見たので，計画性を持って行動出来るようになりたい．
頑張る．

2015-12-31

2015年振り返り

こんな目標を立てていたらしい．
2015年の目標 - utsubo’s diary

競技プログラミング

レート等

SRM　(903 -> 1165)
Marathon Match　(? -> 864)
CodeForces　(1440 -> 1702)
CODE FESTIVAL　(138位 -> 91位)
CODE RUNNER　(65位 -> 46位)

目標

SRM Div1 入り　✕（まだだめそう）
オンサイト　◯（CodeFes出れて良かった）
蟻本読了　✕（目標自体を忘れてた）
CF出る　△（5回しか出てない）

若干成長できたのかなぁ．正直，誤差の範囲だと思ってます．
達成率は40％ぐらい．

英語

目標

洋書読む　✕（目標自体を忘れてた）
洋楽聞く　△（聞き流しは多少）

洋楽は前よりかは聞いたから，達成率は20％ぐらい．

その他

目標

何かしらで2つ以上作る　◯（まだまだな部分もあるけど）
ラブライブの声優に1人以上会う　✕（こんなのも立てていた）
大学の特待生制度で15万貰う　△（だめです）

まずまず．

雑記

某社ツアーが最高でした．ほんと感謝．
そろそろ分野絞ってやらないといけないと強く感じます．
各方面に迷惑をかけまくった一年だった．

今年も大変お世話になりました．2016年目標に続きます．

utsubo’s blog

競技プログラミングとか．

ACM-ICPC 2016 国内予選 D : ダルマ落とし

問題

制約

方針

ICPC国内予選参加記 2016

応用情報技術者試験合格しました

合格しました

午前

午後

感想

ビームサーチの練習用にパズドラAIを組んだ

目的

方針

まとめ

グラフ理論系の好きな問題 5選

1. TopCoder Single Round Match 642 Div.2 Hard Tall Shoes

2. Indeedなう A日程 D: Longest Path

3. CODE FESTIVAL 2015 決勝 H: 焼肉の達人

4. CODE FESTIVAL 2015 決勝 I: 風船ツリー

5. dwango プログラミングコンテスト B: コメント

まとめ

2016年の目標

競技プログラミング

英語

その他

2015年振り返り

競技プログラミング

英語

その他

雑記