競技プログラミング記

はじめまして，Ktyaという者です．

今回練習日記ということでこのブログを作るに至りました．

実はブログという観点で話しますと　

Ｋ茶の日記 - livedoor Blog（ブログ）

が存在するのですが， ちょっと区切りをつけようという意味と少し真面目に取り組んでみるかという意気込みも込めてここで新しく作成するに至りました．

競技プログラミングに対する考え方としてはお遊びパズルのイメージが大半で，暇な時にコンテストに出て話題についていくのを楽しむという感じで取り組んでいたので，非常に易しい問題（他意はない）は解けるつもりです．

 

一応人に読まれるのを前提には書くつもりですが，自分のような「比較的長いことやっているが実力が全くない」という経歴の人はあまりいないと思うので 多分参考になる人は殆どいないと思います．したがって自分向けのものが大半になるでしょう．

 

そもそもなぜ練習しようと思ったのかという話ですが，さすがにもうちょっと自分でも納得のいく実力をつけたいなとこの間久々にまじめにコンテストに出て思ったのが発端です． とくにコンテスト形式の練習をしてても後半の難しい問題を放置しがちなので，こういう記す場を設けることで強制力を働かせようという企みです． 前述の通り，自分の納得がいくまでというのがポイントだと思ってます．

よろしくお願いします．

JOIうめ レベル8 (その3)

JOI11,12更新予定

JOI 11予選

問題は

歩くサンタクロース

概要

H*Wのマスにいくつか家がある。
サンタクロースはまずスタート地点を決める。その後、以下の行動をとる。
・家に訪れスタート地点に戻る。
・最後に訪れる家がゴール
サンタクロースは格子状にのみ移動する（マンハッタン距離）
この時サンタクロースの移動距離の最小値とそれを達成するときのスタート地点を求めよ。

H,W<=10^9,家の個数<=10^5

解法

マンハッタン距離なのでx軸とy軸を一度別々に考える。
また、最後に訪れる家は一度除外して考えると、スタート地点と各家の座標の差の和を最小にする問題となり、これは座標の中央値を選ぶことで最小値が達成できる。したがって、x軸、y軸の中央値をとると良い。
最後に除外した家について考える。中央値より一つ小さい点、一つ大きい点のどれかが最終的な座標になるため、これら(高々9点)に対して移動距離の最小値を計算する（距離の総和*2-最も遠い家の距離)。

実装

とくに。

感想

最初厳密解を求めようとして場合分けが煩雑になりそうになったが定数倍が多少伸びても問題ない。よく忘れる。

JOIうめ レベル8

少し期間空きました　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は制限との戦いが難しい感じ。

 

SLP 2017 Cうめ　その2

SLP SLP_2017

SLP 2017 C4 (IMO 2017 Problem 5)

概要

Nを2以上の整数とする。互いに背の高さが異なるN(N+1)人の人が一列に並んでいる。N(N+1)がどのように並んでいても、ここからN(N-1)人退場して残った2N人について以下が成立するようにできることを示せ。
(2N人の中で)2k-1番背の高い人と2k番目に背の高い人が隣り合う。(k=1~N)

証明

N(N+1)人を最初からN+1人ずつに分ける。各グループをG_1~G_Nと名前をつける。
ここで、より強く以下の条件を付加して示す。
条件:選択する2N人は各グループから二人ずつ選択しなくてはならない。

帰納法を用いる。
N=2の時、身長の高い3人のうち2人が属する方のグループで該当する2人を選択し、残ったグループには身長の低い人が2人以上いるので、そこから2人選択すれば良い。
N>2の時、身長の一番高い人から順に属するグループを調べていき、初めて所属グループが被った人のペアを考え、それぞれa番目,b番目(b>a)に身長が高いとする。(それぞれAさん、Bさんと呼ぶ）
この2人を選び、Bさんよりも身長の高い人および選んだ2人の所属グループに属する人を全員退場させる。さらに、この退場において退場者が1人もいないグループがある場合、グループ内で一番背の高い人を退場させる。
今、AさんとBさんの選び方から、この選び方で各グループからはちょうどひとりずつ退場している状態であるため、N人のグループがN-1個あることになる。また、残った人は全員Bさんよりも身長が低いことになるため、帰納法により示される。

感想

着眼点の悪い帰納法でいろいろ網羅的に条件を扱おうとして破滅　を繰り返したのちに条件を思いついてこの証明にたどり着いた。
帰納法を走らせるため大きい順に構成するとこんな感じになる。
他にもたくさん方法はありそう。

SLP 2017 Cうめ

SLP SLP_2017

問題:
https://www.imo-official.org/problems/IMO2017SL.pdf

SLP 2017 C1

概要

二つの辺の長さが奇数である長方形Rを、各辺の長さが整数となる長方形に分割する（分割後の長方形の辺はRのどれかの辺と平行になることを使ってよい）。
この時、分割後の長方形の中で、Rの各辺との距離がすべて奇数もしくはすべて偶数になるものが存在することを示せ。

証明

長方形をA*Bのグリッドだと思い、各マスを長方形Rの一番左上が黒となるように市松模様に塗る。代位の長方形の切断は、
Rを分割した後の長方形のうち、四すみの色の構成について考えると、(黒,白)=(4,0),(2,2),(0,4)のみである（これはビットで考えた時にで考えた時に左上xor左下xor右上xor右下=0となることから従う)
分割後の長方形について、「Rの各辺との距離が全て奇数もしくは全て偶数」であることと「四すみの色が同色」であることは同値である。
これは「（分割後の長方形の）二つの辺の長さが奇数である」という命題を間に挟めばすぐに示される。

分割後の長方形の中で、Rの各辺との距離がすべて奇数もしくはすべて偶数になるものが存在しないと仮定する。
一つ前の同値な命題により、分割後の長方形の中で、四すみの色が同色のものが存在しないと言うことになり、これは分割後の長方形の四すみは全て黒と白が２つずつ存在することになる。
一方、四すみの色の構成が(黒,白)=(2,2)の時、辺のどちらかは偶数なるため、面積は偶数になる。したがって、分割後の長方形は全て面積が偶数になり、それらを足し合わせたRの面積も偶数となる。
しかしRの各辺は奇数なのでRの面積は奇数となるので矛盾。したがって、分割後の長方形の中で、Rの各辺との距離がすべて奇数もしくはすべて偶数になるものが存在する。

感想

塗り分け、分類、言い換え、適切な指標（今回は面積）とよくあるテクをふんだんに使う感じで解ける。多分うまく帰納法を瀬一定してやっても解ける。
競プロ風にするにはプラスアルファの要素が欲しいか。

SLP 2017 C2

概要

nを正整数として、n個の文字a、n個の文字b、n個の文字cからなる長さ3nの文字列をカメレオン文字列と呼ぶことにする。
任意のカメレオン文字列Xに対してあるカメレオン文字列Yであって、XからYに文字列の互換で変形するのに3*(n^2)/2以上のステップがかかるものが存在することを示せ。

証明

(方針としてはある同じ文字を寄せて計算する)
カメレオンXに対して、n個の文字aの左から見た位置をa_1,\lodts ,a_nとおく。また、S=\sum a_iとおく。
これらを全て左端に寄せるのにかかる操作数は最小でS-(n+1)n/2、全て右端に寄せるのにかかる操作数は最小で(3n+1)n-S-(n+1)n/2となり、この二つの和は2n^2なので、片方はn^2以上となる。等号が成立するのはS=n(3n+1)/2の時である。したがって、操作がかかる方に寄せればn^2回かかる。残った文字列を同じ方向に寄せるとき、bの座標の和をTとおくと、bを寄せるコストはT-n(n+1)/2、cを寄せるコストはn(2n+1)-T-n(n+1)/2となるので、先ほど同様に和をとるとn^2となるため、どちらかはn^2/2以上となる。これらを足し合わせて\frac{3n^2}{2}となる。

感想

方針の見当がつきにくい。
証明も少し正確性に欠けるものになっている（転倒数の議論の辺）
近いセッティングの転倒数計算の問題は作れそうだしたくさんありそう。

SLP 2017 C3

概要

9個の箱に数字を書く操作をする。最初にはどの箱にも何も数字が書かれていない。操作は以下のどちらかを選ぶ。
①2ベキを何も書いていない箱に書き込む
②同じ数の書かれている箱のペアに対して、片方を2倍の数にし、もう片方の数字を消す。
この時、1個の箱に2^nが書かれていて残りの箱には何も書かれていない　と言う状態にするのに必要な操作の回数の最大値を求めよ。

証明

後日更新

感想

JOIうめ

JOI

JOI 09春合宿

問題は
JOI 2008-2009 春季トレーニング合宿 問題

Pyramid

概要

H*WのマスにN個のピラミッドが建っている。各ピラミッドは座標x_i,y_iを頂点として周囲のマスに行くに従い高さが１下がる構造をしている。異なる重なっている部分は高さが高い方が採用される。
全てのマスの高さの合計を出力せよ。

解法

頂点の石の高さを一旦メモし、各添字が増える方向に高さを更新し、その後各添字が減る方向に高さを更新する。
各頂点でピラミッドが建っていると考えて良いため、この操作で各マスでの高さが求まる。

実装

単純なループ

感想

気づけなかった。ただそれだけ。

Abduction

概要

H*Wのマスがあり、(1,1)から(H,W)へマス内で動き回る。今、動いた方向の情報がM個与えられ、曲がってからは1マス以上動く。
ゴールにたどり着く方法は何通りあるか。mod100000で答えよ。

解法

曲がる情報を見た後各マスへ行く方法をdpする。この方法だとH*W*Mかかるので、不適切。各更新は縦と横の情報のみ見れば良いことがわかるのでMAX(H,W)*Mで終わる。これにより計算量が削減できる。

実装

解法の通り。

感想

実験すれば気付ける。実験なしでも気づきたい。

Advertisement

概要

有効グラフがある。ある頂点を選ぶと、そこからいける点へ広告を配布する。
全ての頂点に広告が行き渡るために必要な頂点数の最小値を求めよ。

解法

強連結成分分解(SCC)し、同じ成分を同値類としてグラフを再構成する。
入次数が0の点の個数を数える。

実装

SCCの実装に注意。その後は代表点によりグラフを作り、入次数が0の点をカウントする。

感想

SCCさえ実装できれば終わり。

Distribution

概要

各点に数字の書かれた根付き木が与えられる。（各点で人を表し、親が上司であると考える。）
根にはm枚の紙があり、これを葉方向（部下方向）へ配布していく。紙は分裂せず、1枚以上読んだ人の数字が全体に加算される（読んだ枚数によらず、その人の持っている数字を加算する）とき、合計値の最大値を求めよ。

解法

dfsにより、葉までのコストの最大値が求まる。最大値を求めた後に、最大値を辿る経路のコストを0にする。
これをM回繰り返すことによりO(NM)で求まる。

実装

dfsをひたすらくりかえす。来た道はparentを管理し、葉から道を復元することで達成できる。

感想

最初dpを考えて迷走したが、Mが意外と小さいことに着目したら試すだけで良いことに気づき、解けた。

SLP2018 Cうめ

SLP SLP_2018

SLP 2018 C6

概要

aとbを異なる正整数とする。何も数字が描かれていない黒板に対して以下の操作を無限回行う。

①　黒板に同じ数字が書かれているときどちらかをa増やし、もう片方をb増やす。

②　①ができないとき、新しく0を二つ書く。

ここで、どのように①の操作を行っても②の操作を行う回数は必ず有限回になることを示せ。

以下後日更新

証明

g=gcd(a,b)としたときに、全ての数をgで割ることでg=1として一般性を失わない。
①の操作を有限回、②の操作をN+1回行った直後の状態を考える。
f(N,x)で本状態に至るまでに黒板にxが書かれた回数をあらわすことにする。xが負の時は0として、第二変数は整数全体で定義する。黒板にxが書かれるためにはその前にx-aが二個もしくはx-bが二個書かれている必要があり、一度x-aのペアを使用すると片方はx-a+bとなり、操作の方法より、書かれている数が減ることはないため、以下の式が成立する。(式Aとする)
f(N,x)=\lfloor\frac{f(N,x-a)}{2}\rfloor +\lfloor \frac{f(N,x-b)}{2}\rfloor
f(N,0)=2Nに注意する。

次を示す。
「k,Mをk\leq Mを満たす整数とする。特にMは正整数とする。 f(N,ka+(M-k)b)\geq \frac{2N}{2^M}-2が成立する。」
証明：Mに関する帰納法を行う。M=0の時は f(N,0)=2*Nになので従う。
前述の式Aにより、M>0の時、
f(N,ka+(M-k)b)\geq \lfloor\frac{f(N,(k-1)a+(M-k)b)}{2}\rfloor +\lfloor \frac{f(N,ka+(M-k-1)b)}{2}\rfloor

となり、帰納法から従う。

本不等式により、N\geq 2^Mのときにf(N,ka+(M-k)b)\geq 2が成立する。
また有名な事実として、(aとbは互いに素としているので)ab-a-bより大きい数はna+mb(n,mは0以上の整数)であらわすことができる。
これにより、y=ab-a-bとして、y+1,y+1,\ldots, y+a+bはna+mb(n,mは0以上の整数)という形で表すことができる。y+k = n_{k}a+m_{k}bと表せるとして、N=2^{\max{n_k+m_k}}とすれば、f(N,x)\geq 2がx=y+1~y+a+bで成立する。一方で式Aを繰り返し用いると、yより大きな数全てについてf(N,x)\geq 2が成立することが得られるが、操作①も操作②も有限回であることに矛盾する。
以上より、N　\leq 2^{\max{n_k+m_k}} すなわちNが有限であることが示される。

感想

数学色が強い問題。
黒板に書かれた数字視点でxになる回数を指標とするのは思いついた。
実は操作順によらず②の操作回数が一定であることが証明できるらしい。この部分込みの解説2をいずれ書きたい。
これをプログラムで求める問題はありそう。