ICPC2018アジア地区横浜大会参加記

今年で3回目ですね。

今年はmamumamuとEuldernaと参加しました。

会場は横浜産貿ホールです、もう少し地方でもいいんですよ？観光したいね。

１日目

チームの皆さんはぬくぬくしてるそうです pic.twitter.com/X4M2PRhcfL

— seica (@seica_at_se) December 8, 2018

集団行動が得意なのでチームが集まった

— seica (@seica_at_se) December 8, 2018

集合AC、偉い。

辞書を現地で買う人#色々な人

— seica (@seica_at_se) December 8, 2018

出発前に探したんですがなかったので、サークルとして１個あってもいいよねということで辞書を買いました、来年も買ったりしてそう。

この時割とどうかしていて、関内を歩き回りながらひたすら騒いでいた覚えがあります。チームの二人はこんなのと一緒で大変そうだなあ()

ちなみに関内は「かんない」って読むそうですよ。

pic.twitter.com/IHbqidji8t

— seica (@seica_at_se) December 8, 2018

ご飯に困ったらラーメンみたいなところがある、地味に高いんだけどね。

会場について、TLでよく見る人たちと雑談をしてました。
去年までは他大学に知り合いがほとんどいなかったので、１年で随分と変わったなあなどと思いつつ。

今年はスタッフにもよく見る人がいました、なんだここは実家か？
といってもコンテストが終わるまではスタッフと会話しすぎるのは微妙っぽいので１言２言のあいさつくらいでしたが。

時間をつぶしていたらpracticeの時間に、海外のコンテストならかなり慎重にシステム等を調べるべきなのかもしれないんですが結構雑にやってました、大丈夫でしょみたいな。
clarを投げる方法はちゃんと確認しました。どうやらジャッチの方はカルフォルニアロールが好きだそうです。

チーム紹介、なかなかうまくできませんね。コンテンツ力が足りなさそう。
英語で人を笑わせるの難しいですね。え？そうゆう場じゃない？なるほどなあ。

１日目のスケジュールが終わった後、明日があるので早いうちにホテルに行こうということになりましたが、会場どっちに出ればいいんだっけ。
うーん、「関内わかんない！」

ホテルについてすぐシャワーを浴びてゆっくりしていました。
ABCがあるのでそれ出たら寝ようかなんで思ってたんですが転寝してしまい、起きたら９時30分。ありゃりゃ(まあunratedなので普通に出るんですが)。
本番前最後の競プロなのにDではまってしまって険しい。前日にこれは嫌だなあなんてやっていたんですが、サークルの後輩が２人全完しているのを観測できめでたい気分になりました。来年は弊学から２チーム出したいね。

２日目

pic.twitter.com/4MCZAVPY1C

— seica (@seica_at_se) December 8, 2018

いや寝れてないけど。

遠足前の子供をしていました、全然寝れない。

朝早いのは厳しいですね。コンテスト21時に始まってもいいくらい。

３年目のアジア大会、頑張るぞ！

～～～～ここからコンテスト～～～～

最初に私がテンプレート映している間にA問題をmamumamuに読んでもらいます、概要を聞くとやるだけなのでやりました->AC。
B問題を聞くと これ かと思ったんですがちと違うみたい。
Cが簡単だということなのでそっちを先にやることに。
Cはそれぞれの時間さえ持っていれば前からならせばいいねということで実装して提出->WA
えーなんで…うん、配列のサイズが足りませんね、ごめんなさい。->AC
B問題配列vについてv[j] + (v[j] - v[i])があるかどうかを求められればいいね。O(n^2 log n)は通るんじゃないの？->TLE
えーん＞＜
unordered_mapにしても通らないね。
とかやってたらEuldernaが改善案を出してきました。一回聞いてわからなかったんですがやってもらったらAC。unordered_mapで改善されるケースを初めてレベルで見た。疑ってごめんね。

ABC終わって次はDGかなと見ていたんですが何も生えない。
D答え実は17桁とかで済みませんか？済みませんね、考える文字列は連結ではないのでそれはそう。
G右からと左からの転倒数求めたらできません。それもそう。
Gは計算順序を決めたいな、頂点決めて上からやったらいけませんか？->WA
最大値が一つとは限らないんですね。困った、時間だけが過ぎていく。
そんなときEuldernaが下からやったら一意ではと。
なるほどなあ、セグ木はさっき書いてたんだよね->AC

ここまでで４時間とちょっと。えー時間かけすぎ。Gもっと早く解けたでしょこのすっとこどっこい。

残り30分ちょいとかになってDがDPでやってから復元すれば行けることが分かった。
急いで書く。
急いで書いていたら復元方法良くなくって答えが出ない。マジか…

～～～～コンテスト終了～～～～

なーんか去年もE問題をおんなじ流れで通せなかったなあ。せいかちゃん成長して。
コンテスト終了間際だからこそしっかり詰めてミスなくやるのが大切なんだよね？
今回に関して言えば自分でまともな解法はやせてないので余計につらかった。

今年も４完がボリュームゾーンでしたね。
ここを抜けるの難しすぎる。

今年もYes/Noやるのかなと思ってたら順位表解凍されてて結果見えちゃった。
28位ですって、まあ妥当なんだろうなあ。

懇親会はTLの人たちとひたすら雑をしていました、楽しいですね。
無限にやっていたい。

終わった後は競プロ音ゲー部の活動をしていました。
今回はixmelさん碧黴さんがいるのでボルテする人が多い、うれしい。

３日目

参加記書くのだれてきた。

D問題は通しておきたいなということでやってたんですが家で通せず。
集合場所に移動する中でスマホで通しました。

キレそう pic.twitter.com/GHzGW0yS55

— seica (@seica_at_se) December 9, 2018

今年はindeed -> bitFlyer -> MUJIN の３社。
MUJIN 面白かったです。イケイケのベンチャーいいね。

３日目はixmelさんやTMさん、Tikeさんあたりと話したり話さなかったりしながら企業見学していました。

AOJ携帯でやるには向いて無さすぎる

— seica (@seica_at_se) December 9, 2018

これはDPの復元を説明する図 pic.twitter.com/diQsSWcdcV

— seica (@seica_at_se) December 10, 2018

これはD問題、Kの話を少し聞いたんですが私が解けそうな感じではなかった気がする。

企業見学終わった後はいつものように音ゲー。Tikeさん指上手かった(ixmelさんは言わずもがな、その精度はどこから来るんですか)

書くの疲れたのでそろそろ終わりにします(おいおい)

まとめ

来年でおそらく最後になるんじゃないかなあ。
悔いのないようにしたいですね、まずとりあえず黄色になろうね。

JAG夏合宿2018

JAGの夏合宿に参加しました。参加記かくぞー
だいぶ忘れているのでこれは参加記ではなく創作ということにしておきます。
JAG夏合宿に参加したSeicaの物語書くぞー

写真撮影5級 pic.twitter.com/78dE6b5Y16

— seica (@seica_at_se) September 15, 2018

DAY1

オリセンに向かいます。
参宮橋の松屋でご飯を。

pic.twitter.com/GN0KNgednW

— seica (@seica_at_se) September 15, 2018

てぃーいけちゃんじゃーん

— seica (@seica_at_se) September 15, 2018

チームでは私だけの参加だったので、三日とも一緒に出てくれる人を探さないとなあなんて考えつつ、自己紹介フェーズ。

？？？「これはティッピーで、これはキスショットです」

— beet (@beet_aizu) September 15, 2018

自己紹介から戦いは始まっています、私も何か考えようかな？

コンテスト

一日目は olpheさん(@_olphe ) と ferinさん(@ferin_tech15 ) と組みました。(以下敬称略)
私は最初にCを読み、imosすれば簡単じゃーんということでささっと通したのち(1WA)
Eの方へ…うーん、英語が読めない()
ferin に介護してもらいつつ内容把握したのち、半径にぶたんだ～ってのはすぐに見つけたもののなかなか通らない。
多角形が円の中心を含んでいないときの処理がうまくいかないまま詰まってしまいました。

わからんのでとりあえずあ私はFやっていた olphe に合流。
再帰構造になっていることに気が付いたら olphe が通してくれました。本質っぽいことを言うとACしてくれるの頼もしい。

Eは通せませんでした、途中で雑に ferin になげてしまってましたね、うーん、申し訳ない。結果はABCDF５完

アフター

チェックインを済ませ、お風呂行ったり、100円ロッカーに200円とられたりしながらAGCに備えます。

部屋でも遺憾無くぽんこつっぷりを披露してる

— seica (@seica_at_se) September 15, 2018

AGCはACの２完でした。B難しい。人々がC解いているのを見たのでCに行ったら解けたという感じ。
(結構雑書いて通していたので後の感想戦でぼろが出た)

DAY2

朝

目覚ましをかけたはずなんですが、ならない？
とか思っていたら無意識のうちに消していたそう、恐ろしい。
目覚ましの曲で意図せずにイントロクイズになっていたみたいです。(リステはいいぞー)

あさ pic.twitter.com/y87ee9kS9e

— seica (@seica_at_se) September 15, 2018

いい朝ですね(リステはいいぞー)

コンテスト

二日目は mel さん(@mel_fall524 )と eiya さん(@eiya5498513 )と。(以下k)
今回は mel が実装担当をしてくれるとのことでわたしとeiya が英語と考察の方を担当することに(英語厳しい＞＜)

A問題は読んでも解法が出てこなかったので mel にありのままを伝えたところ実装とACが帰ってきました。
うん、このまま全部の問題概要だけ伝えていこうね(おいおい)

Bは任せてCに移りますが、Cが解けない。

解けない。みんなで考えてみます。

解けない。え～、四角形だけ特別じゃないの？

解けない。他のチームが結構通しているんだけどなあ。チームにはほかの問題を考えてもらったりいます。

解けない。数学か～？競プロやらせて＞＜(これは完全に八つ当たり)

解けた。角度を決める要素に注目するのがポイントでしたね。解法を mel に伝えて通してもらいます。

次～、EもしくはHという感じ。
Hに関しては文字列の判定上手くいかず。
Eはa+b=cを満たす組み合わせの探索で詰まっていて、Eはbitsetでいけね？となったのですが。
TLEが取れない。むりぃ～＞＜。
ということでコンテストが終了。ABC３完です。

のちに話していたところ、非ゼロ判定の時にcountを使うのは重い、anyで十分とのことで、そこを変えたら通りました。
定数倍は大事。N大きいもんね。(まあ、想定はFFTなんですが、FFTは全然出てきませんでした、あの子の使い方がいまいち理解できていない)

アフター

そうそう、時々思うんですが何かあったときに一芸できる何かを持っておくといざというときに役立ちますよね。
アイドルマスターシンデレラガールズスターライトステージなんかで踊りの練習をしてみるのもよさそうですね。

DAY3

朝

今朝は割とちゃんと起きれました、疲れがたまってる気もしますね。

IBMTシャツ
働いたら負けTシャツ(パジャマ)
かざりTシャツ
働いたら負けTシャツ(パジャマ)
次はなんでしょう？
そう、湊くんTシャツです。

— seica (@seica_at_se) September 16, 2018

コンテスト

三日目はFunamiYui(@1119_2916 サンチーム)の一員になりました。FunamiYuiはいいぞー

開始前の小話①

Tike「Seicaちゃんエディタなに使える～？」
Seica「Vim以外なら大体？」
Tike「ア」

エディタ宗教は厳しい、このあと私はEmacsで自分の進捗を吹き飛ばすといういつものをやりました。

開始前の小話②

Seica「それであれがね～」
Seica「あれがあれで～」
合宿に来て言語野の壊れた私はこそあど言葉ばかり使っていたせいで『代名詞の代名詞Seica』という称号を得ることができました(自分で言ったんだけどね)

なんてことをしているうちにコンテスト開始。
私は最初にCを、うんうんいつものDPですね。(進捗が飛ぶ)
うんうん！いつものDPだね！！(AC)

Aに少し手間取っていたみたいですが何とか通り、順位表的には次はJっぽいですが。

Tike「J?J読んでますよ！！…あ、読んでなかったｗ」
Seica「トイレ行ってきま～す」

奇数長の閉路が欲しい、べつに閉路いらなくない？偶奇だけ持てばよさそう。みたいな感じですらすら話が進みACできました。
Jはとてもよかったですね、チームで問題を解くことができました。

次はI、S = 10^5と言いつつ探索の性質上かなり適当に回してもTLは大丈夫なんじゃないかということで
矩形の縦について、よこについて、(1,1)を基準に何個ずらすかについてを回してみたところAC、計算量解析？よくわかんないけど通ったからヨシ！(ここでキレッキレのポーズ)

そのあとFに取り掛かりましたが、必勝法がうまく整理できずそのまま終わり。ABCIJ５完。

アフター

この後は流れ解散となったのでこたつがめさん(@kotatsugame_t )と mel さんと新宿のゲーセンに行きました。

pic.twitter.com/sNQSJVlgPd

— seica (@seica_at_se) September 17, 2018

音ゲーﾑｽﾞｶｼｲ。

そののち、melさんとラーメンを食べて帰宅～
久しぶりにガツッと来るラーメン食べた気もする(ちょっと前に食べた気もする)

ねこちゃんとデート♡ pic.twitter.com/i63IzTGulS

— seica (@seica_at_se) September 17, 2018

まとめ

最近全然競技プログラミングできていなかったのでそうゆう面ではかなりいい刺激になりました。
同じ趣味を持つ仲間で集まってワイワイやるのもやはり楽しいです。

積極的にこうゆうイベントに参加するようになってからまだ一年足らずという感じですが、すっかり日常になっている気がしますね、感慨深い。
次回もぜひ参加したいところです。次はもうちょい解けるようになっていたいなあ。

AOJ 2642 Dinner

問題

Dinner | Aizu Online Judge

感想

これねー。

適当な基準を付けてソートするやーつ、ド典型ですが、むつかしいです。

自炊をするかどうかで自炊パワーが変動するので、ある日に自炊をしたら？しなかったら？みたいなのを考えてみたりします。

また、簡単なため、極端な例から見るとよさそうですね(すべて自炊、すべて外食みたいな)。

という第一感を持ち進めていくと。

すべて外食で済ませるというのをベースに、ある日自炊したときのscore変動についての評価が他の日をどうしたかを考えずにできることがわかります。

どういうことかというと、

i日目(0-index)に自炊した場合、他が全て外食だったとするとscoreの変動が-C_i + (Q - i) * pとなります。(この式をＡとします)

これをもとに複数日間自炊したときを考えると。

(k日間自炊したとすると)各日についてのＡが計算できていれば最後にk * (k - 1) * pを足すだけで計算でき、これはどの日に自炊したかに関係なく一定なので、結局各日にちについてＡのみを基準に自炊する日を決めてしまえることがわかります。(自炊したk日間を手前から見ていくと、二日目の自炊によるscore変化がA + 2 * p、三日目がA + 4 * p…となるのがわかるはず。)

そこまでわかれば、各日にちについてのAを計算してしまってから、大きい順に並べて、i日間自炊した際のscoreを見ていけば良さそうなのがわかりますね。

コード

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG_MODE
    #define DBG(n) n;
#else
    #define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007
 
typedef long long ll;
typedef pair<ll,ll> P;
 
int main(){
     
    ll n,q,p;cin >> n >> p >> q;
    vector<ll> v;
    ll sum = 0;
    REP(i,n){
        ll c;cin >> c;
        sum += c;
        v.PB(- c + (q - i) * p);
    }
     
    sort(ALL(v),greater<ll>());
     
    ll ans = sum;
         
    REP(i,n){
        sum += v[i];
        ans = max(ans,sum + i * (i + 1) * p);
    }
     
    cout << ans << endl;
     
    return 0;
}

ARC100 E - Or Plus Max

漂うインフレ感...？(適当いってます)

問題

E - Or Plus Max

感想

高速ゼータ変換初めて使いましたが。

ある集合Aに対して、A⊆Bを満たすBすべてに対する処理(逆も可)を各集合に対してうまく行うものという感覚でいいのかな？

詳しくはこの方の記事を参照くださいな。
d.hatena.ne.jp

この知識(もしくはO(n^3)の部分集合の列挙)が前提の問題ですね。

問題の考察ポイントに関してですが、

(上記の知識があると)x⊆Kを満たすA_xのうち大きいもの二つを見つけるのは簡単であるのはわかるため。

(i or j) <= K を満たす A_i + A_j の最大

を

ma[q] := (i or j) ⊆ K を満たすA_i + A_j の最大
としてから
max(ma[i])(1 <= i <= k)

と言い換えるところですね。
扱いやすい形に変えてあげましょうという話でした。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

pair<ll,ll> ans[1 << 20];
ll ret[1 << 20];

pair<ll,ll> toptwo(pair<ll,ll> A,pair<ll,ll> B){
	ll fir = max(A.FI,B.FI);
	ll sec = max(min(A.FI,B.FI),max(A.SE,B.SE));
	return MP(fir,sec);
}	

int main(){
	
	int n;cin >> n;
	
	REP(i,1<<n){
		ll tmp;cin >> tmp;
		ans[i].FI = tmp;
	}
	
	REP(i,n){
		for(int j = 0;j < (1<<n);j++){
			if(j & (1 << i)){
				ans[j] = toptwo(ans[j],ans[j^(1<<i)]);
			}
		}
	}
	
	REP(i,1<<n){
		ret[i] = ans[i].FI + ans[i].SE;
	}
	
	REP(i,1<<n){
		ret[i+1] = max(ret[i+1],ret[i]);
	}
	
	for(int i = 1;i < (1<<n);i++){
		cout << ret[i] << endl;
	}
	
	return 0;
}

ARC100 D - Equal Cut

ARCももう三桁回数開いてるんですね。

問題

D - Equal Cut

感想

本番中全く頭が働いていませんでしたが、、、。

数列を四つに分ける(= 数列に仕切りを三つ入れる)というのですが、普通にやると間に合わないので一つ固定したときにどうなるかを見てみます。

状態を1つ進めるといい、という感覚ですね。今回どこを固定するかというと(端っこというのも考えたくなりますが)真ん中の仕切りを決めるのがよさそうですね。

では真ん中を決めたときに、そのあとどうするかという話ですが。

右の部分と左の部分、それぞれなるべく二つの差が小さくなるように分けるのがベストです。

最も均等になるように分けた際の二つの数列の和がそれぞれA、B(A < Bとします)だった時、Aの中の要素を1つBに移す操作はAが余計小さく、またBが余計大きく成るだけで無駄です。

また、Bの中の中の要素を1つAに移す操作を考えたとき、もともとAとBの差が最小になるようにとっているので、その要素の値はabs(A-B)以上です。したがってこの場合BがもとのAより小さく、AがもとのBより大きく成り、やはり無駄になることがわかります。

それがわかってしまうとそんなにむつかしくないですね。

[1,i]の要素の中で二つに区切る場所はiに対して広義単調増加ですね、[i,n]に関しても同じなので尺取り法が使えます。

と、言うことで。

[1,i]、[i,n]の各範囲について最適な分け方を求めてから(O(n)) ,

真ん中の区切りについて全探索(O(n))

となります。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

pair<ll,ll> L[222222];
pair<ll,ll> R[222222];

int main(){
	
	int n;cin >> n;
	
	vector<ll> v(n);
	vector<ll> sv(n);
	
	REP(i,n){
		cin >> v[i];
		sv[i] = v[i];
	}
	
	REP(i,n-1)sv[i+1] += sv[i];
	
	ll now_s = v[0];
	ll now_p = 0;
	for(ll i = 1;i < n;i++){
		while(now_p < i-1 && abs(2*now_s-sv[i]) > abs(2*(now_s+v[now_p+1]) - sv[i])){
			now_p++;
			now_s += v[now_p];
		}
		L[i] = MP(now_s,sv[i] - now_s);
	}
	
	now_p = n-1;
	now_s = v[n-1];
	
	for(ll i = n-2;i > 0;i--){
		while(now_p > i+1 && abs(2*now_s-(sv[n-1]-sv[i-1])) > abs(2*(now_s+v[now_p-1]) - (sv[n-1]-sv[i-1]))){
			now_p--;
			now_s += v[now_p];
		}
		R[i] = MP(now_s,(sv[n-1] - sv[i-1]) - now_s);
	}
	
	ll ans = LLINF;
	
	for(int i = 1;i < n-2;i++){
		ll ma = max(max(L[i].FI,L[i].SE),max(R[i+1].FI,R[i+1].SE));
		ll mi = min(min(L[i].FI,L[i].SE),min(R[i+1].FI,R[i+1].SE));
		ans = min(ans,ma - mi);
	}
	
	cout << ans << endl;
	
	return 0;
}

尺取り、慣れてきた感があります。

AOJ1185 Patisserie ACM

問題

Patisserie ACMACM洋菓子店 | Aizu Online Judge

感想

面白いですねこれ。(ほんとに感想)

一見して何もわからないけれど。すっごく簡単に言うと。

• 折るということについて考える(必要条件・共通項を見つける)と凹みのところが大事な点(2*2の範囲のうち3個がチョコのところ)とわかる

• (最適について考えると)大事な点が(垂直・水平な)線で結べると嬉しい + 交差していると無理 　がわかる

• グラフに置き換えると独立集合の問題に変わる + 二分グラフとなる

• 二部マッチングで解ける。

という感じ。

大事な点に関しては、折り目はチョコを折る時は必ずその点を通る直線になっていること、という話ですね。

その次が、答えがすべての大事な点をカバーできる直線の数 + 1になるわけなんですが、一つの直線で二つの点をカバーできると嬉しいねという話

実装はそんなにむつかしくないし時間も厳しくないので適当にやりました。

コード

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;
typedef complex<double> point;

struct segment : public vector<point> {
	segment(const point &a, const point &b) {
		push_back(a); push_back(b);
	}
};

double cross(const point& a, const point& b) {
	return imag(conj(a)*b);
}

double dot(const point& a, const point& b) {
	return real(conj(a)*b);
}

int ccw(point a, point b, point c) {
	b -= a; c -= a;
	if (cross(b, c) > 0)   return +1;       // counter clockwise
	if (cross(b, c) < 0)   return -1;       // clockwise
	if (dot(b, c) < 0)     return +2;       // c--a--b on line
	if (norm(b) < norm(c)) return -2;       // a--b--c on line
	return 0;
}

bool intersectSS(const segment &s, const segment &t) {
	return ccw(s[0], s[1], t[0])*ccw(s[0], s[1], t[1]) <= 0 &&
		ccw(t[0], t[1], s[0])*ccw(t[0], t[1], s[1]) <= 0;
}


char mp[111][111];
bool check[111][111];

int h,w;

#define MAX_V 22222
vector<int> v[MAX_V];
int match[MAX_V];
bool used[MAX_V];
vector<segment> segs;

void add_edge(int a,int b){
	v[a].PB(b);
	v[b].PB(a);
}

bool matchdfs(int a){
	used[a] = true;
	for(int i = 0;i < v[a].size();i++)	{
		int u = v[a][i],w = match[u];
		if(w < 0 || !used[w] && matchdfs(w)){
			match[u] = a;
			match[a] = u;
			return true;
		}
	}
	return false;
}

//二部マッチング
int two_matching_max(int l){
	int res = 0;
	memset(match,-1,sizeof(match));
	REP(v,l){
		if(match[v] < 0){
			memset(used,0,sizeof(used));
			if(matchdfs(v))res++;
		}
	}
	return res;
}

bool isOUT(int y,int x){
	if(x < 0 || y < 0 || x >= w || y >= h)return true;
	return false;
}

int main(){
	
	while(cin >> h >> w,h|w){
		int checkcount = 0;
		REP(i,MAX_V)v[i].clear();
		segs.clear();
		REP(i,111)REP(j,111)check[i][j] = false;
		REP(i,111)REP(j,111)mp[i][j] = '.';
		
		REP(i,h)REP(j,w)cin >> mp[i][j];
		
		REP(i,h-1){
			REP(j,w-1){
				int cou = 0;
				REP(x,2)REP(y,2)if(mp[i+y][j+x] == '#')cou++;
				if(cou == 3){
					checkcount++;
					check[i][j] = true;
				}
			}
		}
		
		REP(i,h-1){
			REP(j,w-1){
				if(check[i][j]){
					int y = i + 1;
					int x = j;
					while(1){
						if(isOUT(y,x))break;
						if(mp[y][x] != '#' || mp[y][x+1] != '#')break;
						if(check[y][x]){
							segs.PB(segment(point(i,j),point(y,x)));
							break;
						}
						y++;
					}
					DBG(cout << "!" << endl;)
					y = i;
					x = j + 1;
					while(1){
						if(isOUT(y,x))break;
						if(mp[y][x] != '#' || mp[y+1][x] != '#')break;
						if(check[y][x]){
							segs.PB(segment(point(i,j),point(y,x)));
							break;
						}
						x++;
					}
				}
			}
		}
		
		REP(i,segs.size()){
			for(int j = i + 1;j < segs.size();j++){
				if(intersectSS(segs[i],segs[j])){
					 add_edge(i,j);
				 }
			}
		}
		
		int ans = checkcount - (segs.size() - two_matching_max(MAX_V)) + 1;
		cout << ans << endl;
		
	}
	
	return 0;
}

AOJ1620 Boolean Expression Compressor

去年はちんぷんかんぷんでしたが。
解けるようになるもんですね。

問題文

Boolean Expression Compressor | Aizu Online Judge

感想

えー、ごり押しです。

文字列の長さが16までなので全部見てみます。

すべての文字列に対してabcdがそれぞれ0,1の場合、つまり16通りの結果を調べてメモ化。
同じ結果の出るものについては最小の文字列長を記憶します。

さて、本番なら二分探索してしまえばいいですが、今回は8秒以内に納めないといけないので少し高速化します。

まず調べる文字列長は15までにします(16文字の論理式は実際に求めるやるか15字以内のどれかしか答えになり得ない)。
また'-'の記号は二つ以上並べるのは無駄なのでこれもやめます。

また、文字列をいじくったり文字列でdfsするとき、なるべく文字列のインスタンスを作らない方が早くなりますね(グローバルにおいて使いまわす等)。

ということでなんとか1.3秒ほどに納めることができました。

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

set<string> s;
int dp[1 << 16];
int place;
char sstr[20];

int dfs2(){
	if(sstr[place] == '-'){
		place++;
		return 1 - dfs2();
	}
	else if(sstr[place] == '('){
		place++;
		int a = dfs2();
		char c = sstr[place];
		place++;
		int b = dfs2();
		place++;
		if(c == '^')return a ^ b;
		else return a & b;
	}
	else{
		return sstr[place++] - '0';
	}
}

int f(){
	place = 0;
	return dfs2();
}

int investigate(string str){
	int ret = 0;
	REP(i,(1<<4)){
		REP(j,str.size()){
			if(str[j] >= 'a' && str[j] <= 'd'){
				sstr[j] = (char)('0' + ((i & (1 << (str[j] - 'a')))>0));
			}
			else{
				sstr[j] = str[j];
			}
		}
		ret |= (f() << i);
	}
	return dp[ret] = min(dp[ret],(int)str.size());
}


void check(string str){
	int cou = 0;
	REP(i,str.size()){
		if(str[i] == 'X')cou++;
	}
	int num = 1;
	REP(i,cou)num *= 6;
	REP(i,num){
		string now = "";
		int tmp = i;
		REP(j,str.size()){
			if(str[j] == 'X'){
				int seica = tmp % 6;
				if(seica < 4){
					now += (char)('a' + seica);
				}
				else{
					now += (char)('0' + (seica - 4));
				}
				tmp /= 6;
			}
			else{
				now += str[j];
			}
		}
		investigate(now);
	}
}

void dfs(string str){
	if(str.size() > 15 || s.count(str))return;
	s.insert(str);
	check(str);
	REP(i,str.size()){
		if(str[i] == 'X'){
			dfs(str.substr(0,max(0LL,i)) + "(X*X)" + str.substr(i+1));
			dfs(str.substr(0,max(0LL,i)) + "(X^X)" + str.substr(i+1));
			if(!(i > 0 && str[i-1] == '-'))dfs(str.substr(0,max(0LL,i)) + "-X" + str.substr(i+1));
		}
	}
}	
	

int main(){
	REP(i,1<<16)dp[i] = INF;
	dfs("X");
	string str;
	while(cin >> str,str[0] != '.'){
		cout << investigate(str) << endl;
	}
	return 0;
}

一回全部'X'で作ってから割り振るということをしています。これがいいのか悪いのかはわからないね。書きやすいと私は思ったけど。