JOIうめレベル8 - Ktya’s blog

少し期間空きました　markov algorithmにハマったりしましたが、問題は結構処理できてます。

レベル8を7割ときましたが同じレベルが設定されていても問題ごとに難易度の差があるように感じられますね…　苦手分野がハッキリしている感じがします。数オリのように分野などはあるんですかね？

JOI 10予選

問題は
https://www.ioi-jp.org/joi/2009/2010-yo-prob_and_sol/2010-yo-t6/2010-yo-t6.html

方向音痴のトナカイ

概要

H*Wのマスにいくつかの家と一つの教会がある。サンタは升目をいずれかの方向にまっすぐ動くことができる（方向転換は基本的にできない）。まっすぐ動いている途中に家（教会は含まない）があると降りることができ、降りた際には方向転換ができる。家に降りると家から煙が出るため、家のあるマスを通過することができなくなる（煙のマスの手前で止まることができる）。サンタは好きなところから出発し、全ての家にプレゼントを配り終えたのちに教会のマスに到達して終了する。プレゼントの配達順の場合の数を求めよ。

H,W<=10,家の個数<=23

解法

スタート地点から順にやると止まった場所に応じて通れなくなるなどの管理ができない。そこで、ゴール（教会）から順に遡って調べる。遡る際に途中に別の家があると、煙で通れなくなるという設定と矛盾する。よって四方向の突き当たりの家のみ調べればよい。

実装

dfsしながら全て回収した時に1足し、不適なものは枝刈りすれば良い。

感想

この予選実は受けてたことを思い出した。問題文だけ読んでやらなかった記憶。当時はプログラミングの本をちょっと読んだだけで問題慣れもしていなかったためこの問題以外も全然できなかったはず。

最初普通のdpしたらMLEくらった。当時はMLE解でも本当は大丈夫だったらしい。

JOI 10春合宿

問題は
https://www.ioi-jp.org/camp/2010/2010-sp-tasks/index.html

Sengoku

概要

L*Lのマス目に見張りを配置する。
(x,y)の位置にいる見張りは|x-i|=|y-j|を満たす(i,j)を見張ることができる。（バツ字に見張る）
見張りの座標が与えられた時1人以上に見張られているマスの個数を求めよ。
L<=10^8,N<=10^5

解法

y=-x+c,y=x+cの二種類のみ。まず片方の種類のみ(傾き-1)を集計する。全て平行なのでそれぞれ個別に数えて足せば良い。
次に傾き1の直線について、前述と同様に個別の個数を数えたのちに、既に引いた傾き-1の直線との交わる個数を求めて引けば良い。
偶奇で交わるかどうか変わる点に注意しながら、cの正負に注意して計算する。内容としてはc>0でc~2*L-cの部分と交わるので、累積和を利用することで各直線に対してO(1)で計算できる。

実装

各計算を丁寧に。

感想

最初偶奇に気づけなかった。易し目なのですぐ片付けられるようにしたい。

a+b problem

概要

(x_i y_i)なる数列で左の桁から順にx_1がy_1個,x_2がy_2個,…,x_nがy_n個並ぶ整数をあらわすとする。
上記の表記方法で二つの整数が与えられる時それらの和を上記の方法で表記して出力せよ。
n<=20000,0<=x_i<=9,y_i<=100000000

解法

二つの整数の区切り目を合わせて、二つの整数でy_iが同一になるようにする。その後各種繰り上がりに注意して計算する。
最後にx_i=x_(i+1)となる部分をマージする。

実装

各区間の和の形に注意。

感想

合ってるはずだがデバッグ中。。。

DNA synthesizer

概要

A,T,G,CからなるDNA鎖が二本ある時、共通部分を一つにまとめて結合することができる。
N種類のDNAがあり、それらをいくつか使用して結合して一つのDNAを作成する時、結合個数の最小値を求めよ。
N<=50000 お題のDNAの長さ<=150000 元のDNAの長さ<=20

解法

元のDNAの種類は多いが、長さが短いことに着目する。
お題のDNAのi文字目での最小値をdp[i]する。後ろからa文字がN種類のDNAのどれかと一致している、というようなaの最大値を求め、
dp[i]=min_{j}(dp[i-j]+1)を計算する。

実装

文字の一致を見てるとTLEしたので数値に変換して行う。（良いやり方あるの？）

感想

解法は単純。後の記事でも書くけど、最近のJOIの方が発想が難しくて過去のJOIは制限との戦いが難しい感じ。