読者です 読者をやめる 読者になる 読者になる

hogloidのブログ

へなちょこ

解いたものリスト

個人的良問リスト - hogloidのブログ ←4年ぶりに戻ってきました

今回は、主観的面白さでoを0個〜3個つけています。 ☆は自力では解けなかった問題です。 月間更新予定。2017年1月は簡単めのSRMばかりやってたので簡単めのSRMばっかりです。

個人的備忘録のおまけ程度で書いてるのと、あまり真面目に書くとコストが高くなって疲れるので、荒い書き方になっています。おかしな点・分からない点があれば直接訊いてください。

markdown記法を使ったら一部数式が意図しない解釈をされているみたいです(後で直します、あとで…

nothing

529H: 式を適当に変形すると、B,S,#{Big Airport}を固定したらNの上限と下限が求まる形になるからそうやって求める。#{Big Airport}は小さい範囲で動かす(他はかなり自由なので別に求める)
534H: 同じ場所は二度swapしない、とかの考察を進めていくと、欲しい文字を持ってくる&書き換えで済む。 別解多し。o
549H: 全探索してフロー流す。たぶん全探索は色々あるけど、315通り辺の張り方試す(辺を加えながら閉路が生じないかチェック)→辺ごとに高さが1違うかチェック→それが取り方の数の制約を満たしてるかDPでチェック→フロー流せるかチェック をした
550H: (maxCost-(必ず必要な操作のコスト))/33回まで操作できる、としてよい。(s[i]=t[i], s[i]=t[i]+1, s[i]=t[i]+2)(等号はmod3)となる桁の数の3つ組を状態とする遷移が行列で書ける。状態の数は78個ぐらい。あとは、s=tとなる状態を何回訪れたか数えるよう1つ行を加える。
581H: ふつうのbrute-force. 一番上の列を3w通り試して残りは自明に操作が決まるのでそれがvalidか確認し、validなもののminを取る。当時はflipをbit高速化しないと通らない?かも(今やって1.8sec)なので
586H: なんか貪欲っぽく行ける気もする…が収拾つかなくなったのでDP。dp[何番目の文字列まで決めたか][未使用文字][もう使わない文字]:=最小値 みたいにする。遷移で、新たに使う文字、ここでやめにする文字、ここで始めここでやめる文字の数を試す。L_iのうち26以上の数で挟まれたところは消しておき、26以上のiを高々2つにしておくと、「ここで始めここでやめる文字」を非ゼロにするのはその二つのiだけでいいので計算量がよくなる。(C4
(N+C)) オーダーが高次多項式のときありがちだけどあまり何も考えなくても通るっぽい…(実際それで大丈夫そうな気もする)
615H: 簡単すぎィ! 列をつくれるかどうか⇔Rの数-Gの数がどのprefixも0以上M以下、RGの数が2Mの倍数なのでindex,R-G,R+G mod 2M でDP
640H: N2通りの差の素因数を調べればいいが、そのままやるとTLEするので、104.5までの素数についてはその素数でのmodでソートしてmodが同じものの間に素因数を追加、104.5よりでかい素数は1つしか持ち得ないので、それまでの素因数で割っていき1にならなかったらそれが残り。
634H: 2点を結ぶ直線とそれをepsずらしたような分け方のみ考えればいい。1点を原点に固定して、最初は(Y<0 || (Y=0 && X<0))とそれ以外に分けて、ぐるぐる回しながら入れたり出したりする。原点を入れるか入れないかの2通り回せばいい。
645H: 包除原理して、2回できない集合Sを固定する。Sの各元について、2回できないことを決めたので、0回か1回、これをbitDPにして求めていく。DPは[i日使う][1回乗った集合はT]:=通り数、ただし通り数にはS以外のものを遊んだ?回数をカウントする。カウントの仕方はSの部分集合全部についてS以外の部分集合のとり方がいくつあるかを愚直に数える。O(4N*N)
646H: 二分探索して、何位に入るか決め打ち、それより上のチーム・自分以下のチームはすべて勝つことにして、Win/Lose/Drawがいくつあるか求める。 W>=L+(D&1)が必要条件で、加えて自分自身と戦ってしまわないといけないもの除かなければいけないが、W-Lについてはその心配はない(自チームは必ず勝つためそこで組み換えできる) W-D,W-Dも同様。D-Dのみが問題で、2回とも引き分けるチームがありDがその2つだけのときがNG。WLはDDに変えると得になるケースがあるが、↑の理由の通り全部試す必要はなくて2,3個変えればいい 悪問ではないけど嘘じゃないと確信するのが大変で解法自体は思いつきやすく微妙…
679H: 簡単すぎィ!

o

530H: ふつうのDP.よくある、動かすときに決めないで後回しにしておくやつ。 o
532H: ふつうのDP.rowがsimilar⇔ソートした時に一致、なので、ソートした状態で左から決めていく。N行が今のところ同じ、あとM列ある、色はK色使える、色0を今までL個連続して取っている、というキーがあればDPできる。(最後のは同じ色での塗り分けの区別を同一視するため) o
540H: 10=25 で、mod 2に対する答えとmod 5に対する答えを掛け算すればいい。これで見通しが良くなるのであとは前処理(右端が同じ制約を二つに分割、を繰り返す)をしてDPするだけ。 o ☆
559H: たぶん二分探索が楽。[-PI,PI]の数直線上に、どこからどこまでが覆われるかを置いてくやつ。円と円の交点を求めるライブラリがあればヨシ。 o
578H: 切断する辺を決め、rec(v,p1,u,p2):=(p1-v)のv側の部分木、(p2-u)のu側の部分木についての最大値 としてメモ化再帰。毎ステップでは最大重みマッチングする(=>最小費用流に落とす) 負辺だろうが構わず解くライブラリ使ったらその定数倍で落ちた…(できるなら変形したほうがきっと早い)(適当に自明な高速化をしたら通った) o
584H: 最小有向全域木。頭によぎれば帰着は簡単 reachability,loop とかの確認を怠ってはいけない(戒め)けどどうせサンプルにある o
591H: 上からDPしていく。(点とその上1行分にA,Bを到達させることができるかが状態) 斜めに埋めようとしてしまいやたら面倒になったorz o
604H: 無限に置けるかは、ある微小なベクトルがあってその分だけずらしても重ならないようなものがあるかと同値。どちらかが端点でない交点があったらだめ、ある点に3つ以上別の角度から伸びていたらだめ、そうでない場合はなす角とその逆側だけOKなので、共通部分があるか判定する。 o
613H: 行の左右は独立。左の列から順にDPで埋めていく。状態は[i:何列目][i列を含むleftの行のうち、チェッカーおいたのはいくつか][i列を含むrightの行のうち、チェッカーおいたのはいくつか] o
614H: 初期位置が0,0の代わりにゴールを0,0にする。連立方程式を解きたいが、(NM)3かけるとダメなので、グリッドの周縁部だけそれらの間の確率遷移を求め、期待値を求める。初期位置から周縁に行き着く確率を求め、掛け合わせる。 o
617H: それぞれ独立に、Lex.smallestのgreedyに沿って考える。あるprefixがOKかどうかは、それからある文字の埋め方が存在し編集距離をK以下にできる&&それからどう埋めてもK未満である、ということはない 編集距離はDPで o
631H: クエリーの平方分割して、出てくるu,vだけマークする。それ以外の頂点はスキップし、その間の辺の最大値を持つようにする。クエリーに対し、vから登るときにスキップしたグラフを使えばO(B) 前処理もO(N)でできる o
633H: 素因数ごとに考える。ある2数について指数のでかいのはいくつ、小さいのはいくつ、という条件がたくさんつく。これを、ある2数の指数はhoge以下・2数のうち片方の指数はhoge という条件に分解して、1つ目でNGならNG。1つ目はOKだったら、それぞれの数に上限か下限のどっちかを与えるのがよい。辺ごとに、片方を上限にしたら片方を下限にしないといけない(上限と下限が一致する場合を除く)ので、2SATにして解く。 o
635H: 少ないのから順にA,B,C,Dとして、左からA/Bだけ置いてく。dp[Aをいくつ使ったか][Bをいくつ使ったか][A/Bの間または端のうちnon-emptyなものはいくつか]:=通り数 でDPして、最後は適当に求める。 o
642H: prob[i回spinした][場所0のスコア]:=確率、exp[i回spinした][場所0のスコア][K]:=場所Kのスコアの期待値 として求めていく o
653H: 0,1,2に対しRock,Paper,Scissor(R,P,C)をそれぞれいくつ割り当てるかになる。3
3の行列にしてみると、それぞれの列・行に対して値をいくつかに割り当てて、要素は列と行の値の和になるかどうかが必要十分.これはO(m2)で全探索できる(m:最小のカードの数) なんか合わなかったから必要条件集めてO(m3)で候補を全部あげてそれぞれ可能か確認する方針でも通った o
666H: 区間としてカウントするのは、入っていてかつ他の小さい区間に入っていないもののみとしてよい。すべての区間について、[いくつ左に1が続いてるか][今までの1の数の偶奇]の状態組についてこれをこれに移すのがいくらあるか求める。行列累乗とかを使う。 o
668H: DP.一番内側でないカッコは1回しか通れないことに注目。(∵内側のカッコを出るとき値が0で、同じ動作を繰り返してしまう) dp[残り長さ][今の値]:=残りの長さで値を0にする文字列の数 として求めていく。+,-は普通に入れる。は同時に挿入して、長さ・その中で値をいくつ変化させるかを試す。1回で0にならない場合、その中身にがあってはいけないという制約がつく。全体の答えは、↑のDPで最後が0にならない版(同じように解ける) Nまでの約数の和はO(NlogN) なので、 O(N3logN) o
670H: 1~9を互いに区別して部分集合に分ける方法は20000通りぐらい、そのうち細分になっている関係は1.6e6ぐらいなので、まずこれを全列挙する。あとは、ある分け方についてその分け方またはその細分になっているものは、ある辺集合を使わないということと同値なので、その辺集合を先に掃き出す掃き出し法を使えば簡単に求まる。その後、細分の関係を用いて、ちょうど分け方があるものになる通り数を求める。分け方にid付けるとき、mapでやるとTLEするので、trie木を使った。O(へんなの) どうやら200002かけても細分か否かをbit演算でやれば通るっぽい?:angry: o
674H: コスパのいい方を80個以上使ってなかったらそっちに寄せての要領で、最低使用量を決めて残りの重さ803をDPする。O(N4) 2べき分解→小さいのから詰めてく、というやり方でもできる。前者は境界が面倒なのでこちらのほうが楽? o
707H: 動かす⇔コスト-1の辺をたどる にして最小費用流 o
517H: 可能判定は後ろから埋められるところを埋めていけばいい。最小化は、埋められるところが1つでも見つかれば、それを埋める場合について再帰的に解く。それ埋めない場合、逆側の(列/行)は残ってる全てをその色で塗らなければいけなくなる。こう決めたとき可能かどうか・最小値を求る。 o

oo

537H: 最小費用流に言い換えると、最小流量1、コスト全て負のグラフ、source,sinkは無しで費用を最小化する問題になる。 そのままでも少し強いライブラリがあると解ける。逆に、全て辺を流した状態からどれを消すか考えると、費用が正のsourceやsinkのあるふつうの最小費用流になる(どっちも同じことだが) source,sinkにこだわっると前者が見えない(見えなかった) oo ☆
555H: i番目にheadをおいた状態から始めるとすると、何回かそこで完成するチャンスがあるかもしれないが、一番後のものだけ考えればいい(後のものはそれまでの可能な初期値を全て可能とするため)。iについて自由に数を決められるところのbitmaskを持つ。次に、包除原理する。ここで、goalと全く同じ置き方だけは除外して考える。すなわち、Σ(Sの元)番目にheadをおいた状態から始めてすべて可能となる初期状態の数(-1)|S|-1の総和を求めればいいのだが、Sの元から始めたときすべて可能になる部分はbitmaskのandを取って1だったところなので、codeが影響する長さに制限される。逆にこれが長いと、外にはみ出ない制約から有向な初期位置自体が減るので、うまくやると218182とかになる oo
567H: 山をn-1,n-2,…,0と置いてく。全ての列で見える山が見えない限り、置く候補は高々2つ(2つずらそうとすると端が動いてしまう).全ての列で見える山があるとき、素直に全部試す。状態として、マップ全体じゃなくてそれぞれの列の最高地点の配列を持つと、これで自然と状態数2n+nnになる。 oo
576H: |S|で場合分け。ある長さLについて、indexの差がLの倍数のときそれは同じ文字でないといけない。あるマスとあるマスが同じ文字でないとけない、という条件で、片方からもう片方が導けないようなものが二つあるとき、そのGCDは2000以下。(∵縦にa,b違うとき、a
bマス下の行で二つは高々長さ2000で同時に出てきてしまうため)。よって|S|<=のときは全部試す、それ以外については同じでなければいけないという関係ごとに全部見る、どの関係にも属さないものは2|S|-n*m (実装が結構たいへん)(最初に候補を全列挙したほうが楽らしい) oo
580H: 下からDPを埋めてく。i行目に初めて到達して、それがj列目のとき、以後のコストは「min{行内の任意の経路} max{経路の途中で初めて通る列} そこで降りたときのコスト」(maxが成り立つよう壁を張れるし、ある経路に対しそれよりコストを掛けさせることは不可能) これを用い、さらにDPする。列内でくねくね動くことはありうる。(状態は、左、右、行内の移動でのそれまでのコスト、今左端か右端か 3番目の数が9502になるのでは?→ならない。同じ行の初めのDPのコストの差は高々450なので(∵初めに横移動すればいい)、ここで675+450以上掛けるぐらいなら列内を左右に舐めたほうがいい。) oo
588H: Bobが勝つ⇔ある頂点で、そこから伸びる部分木の高さが3以上のものが3つ以上あるところに、BobがAliceより2ターン早くたどり着けるものがある 確かに、思いつけばそれはそう。AliceがBobの方向へ向かっていく感じの解法でもできるが、場合分けが結構大変。 oo
593H: ふつうのDP.dp[i]:=i文字目までの文字列での組み合わせの数、とすると、最後のw..wo…oを全部試すとO(N2)になる。最後の付け加え方について、Sでのwを含むかどうかで場合分け。含むものは、i以前の最後のwとその前後のoから、区間が決まる。含まないものは、逆にdp[i]を求めたときにどこまで可能か次のw,oの場所からすぐわかるので、別に足す。 oo
596H: n = k (mod divisor) ごとに考える。はじめてn
(n-1)…(n-k2) = 0 (mod divisor)となるkを求めておけば、条件を満たすnがどこ以上か分かる。divisorを素因数分解して、うまいこと合成するとできる。 oo
597H: 1列のRG,GB,BRを0,1,2とし、0,1,2をX,Y,Z個置く問題として考える。0で隔てられた残りの部分で奇数個のものがi個となるような置き方を数え、残りの1,2をどう埋めるかの数を掛け、足し合わせる。(奇数個残したいところは0に(1or2)を、偶数個残したいところは0に(1or2)を2個くっつけて組み合わせを取る感じ。左右は場合分けしないといけない。長さ0の場合1,2の埋め方が1通り、他の偶数は2通り) oo
603H: C[i]:=Σmin(a[j],b[i-j]) でC[i]最大の値を求めたい。a[i]>=M,b[j]>=Mとなる(i,j)の組については前通り試し、そうでないものをFFTで数える。min … がk以上となるようなものがCにどれぐらい寄与するかは、 A[i]:=(a[i]>=k?1:0) B[i]:=(b[i]>=k?1:0) という2つの数列をたたみこめば求まるので、合計でO(N4/3(logN)2/3)で求まる。 oo
605H: こんなのどうせでかいのor小さいのから見るに決まってる…かと思いきや、編集後も残りの要素は連続するし順序が保存されるので、左から埋めていくとうまくいく。P[i]がどこまで広がれるか(それより小さい要素のある範囲)を求めて、どこまで埋めたか、次使う数はどれか、何回操作したかでDP oo ☆
608H: 縦軸を時間、横軸を位置としてグラフぽいものを描く。あるA,Bについて、左の壁に接するなら、それより初期位置を左にずらしても最終位置は同じ。右も同様。B+Aを固定し、両方の壁にぶつからない範囲、右につぶれる範囲、左に潰れる範囲に分けて計算。(整理してから実装しないと実装が躍動して大変なことになった…) oo
610H: XY独立。後ろからDPしていくことを考える。利得のかわりに逃す利得の最小値を考える。毎ステップ、ある点を中心にV状に足して、その後小さい値を近くに均していく感じになるが、この形は常に谷状・下に凸になる(帰納的に示せる) DPテーブルをグラフとして見たときの折れ線の傾きが変わるところを全部配列で持って、V状に足すのと谷をでかくする操作をする 谷底の高さがどれだけ上がったかを毎回足し、和が逃す利得 oo
705H: 行列にスイッチのベクトルを掛けて出てくるベクトルのうち1になる要素を最大化したい。行交換・列交換はしてもOK。列の足し算もしてもOK(スイッチの付け方にある変換が施されるがその変換は全単射なので) これを使い掃きだした形が下三角になるよう掃き出し法みたいなことをすると、N個のスイッチのうちいくつかは使っても使わなくても関係ないものになる。残りの有効なスイッチの数をL個とする。L<=27なら全探索。L>27のとき、L個のライトはある1つのスイッチを押すかどうかだけで点くかどうか決まるので、それ以外のM-L個について、いくつかスイッチを押すか押さないか決めたときに点くかどうかを持つbitDP。 oo ☆
705M: これすき ある2つの箱の中身が何回かの(同じfunctional graphとは限らない)操作を経て同じ箱の中身になるかどうか予め求めておく。初期状態から、併合できる箱の中身はどんどん併合してしまう。もう併合できなくなったら答え。(なぜこれでいいかというと、どんな状態も初期状態のsubsetなので最適解にたどり着ける) ☆ oo
625H: まず、DPで[i人おいたとき][j個のクラスターになっている]というものを、クラスター内の順序が同じものはすべて同じとみなして数え上げる。最後に、jこのクラスターを適当にテーブルに配置する。クラスターの個数が同じなら、どんな人数の割り当ての違いがあっても配置の数は同じになるため。 oo
627H: フロー。それぞれのセルに縦か横を割り当て、S側が横にするセル、T側が縦にするセルとする。敵を倒せない割り当て方について、敵のスコアだけカットが生じるような辺を張り、答えから引く。タワーから見てより遠くでよりスコアの小さい敵は攻撃しない。これで単調になる。横のタワーから見て、ある敵までのどこかで縦のセルがあった場合-(敵のスコア)としたいので、横のタワーの頂点から流量(敵のスコア)の辺を新しく作った頂点に張り、その頂点からinfの辺を敵までのセル全てに張る。縦については流れが逆 oo
629H: 結局 PI_{k=1}^N (x+k) でのxKの係数を求めたくなる。これはNについての2K次以下の多項式なので(∵Kについての漸化式がべき乗の和とかを使ってかける)、N<=2KぐらいまでをDPで求め、多項式補完する(多項式を求めるんじゃなくて、直接そこにNを代入したほうが楽) oo ☆
654H: s0-s1のパスではじめに使う頂点で場合分けしようとすると、その点の両隣のパスの辺でグラフを分けたとしても同じ置き方ができる。パスの長さが偶数のときはこれでよし。奇数のとき、s1をパスの中で最も早く使わなければいけない、という条件がつくが、これは単にs0のみでおけるということ。 O(N2) oo
657H: (a,b),(b,c)に辺があり(c,a)にも辺があるならa,b,cは横か縦に揃えて、(c,a)になければ(a,b,c)で横・縦別に置く。これが構成できるかO(N3)で確認。確認したら、1つ辺を決めると残りは全部決まるので、置いてく。連結成分ごとに独立なのでDP。孤立点のみは横に置こうが縦に置こうが同じなので別処理 oo
664H: dp[マージソートのどの区間に対応するか][何回比較するか][与えられたやつの対応する部分列とのLCPの長さ][LCPの次の値が小さいか大きいか(実際は、小さい/それより後ろはdont careのほうがいいかも)]:=通り数 でDP。メモ化再帰のほうが楽なきがするけどそれにしても大変。O(N5logN)な気がする(実際ははやい) oo
669H: 下の桁から埋めるDPをするが、重複が出ないよう、[Miを1を使いつつ1,M,…,Mjまでの和で作る通り数]を求め、Miずつ使う最小のコインで場合分けて足していく。この通り数もまたDPで計算する。Mi=M
M^{i-1}なので、同じようにMiずつ使う最小のコインで場合分けて足す。 oo ☆
671H: 上から埋めてくのは間に合わないが、斜めに埋めてくとWH2min(W,H)の状態でbitDPできる oo ☆

ooo

525H: 自己同型を求める問題であること、その上で角柱であることが分かればGoal。発想度高し ooo
526H: 1つ文字列を加えることで、i文字目までマッチしている確率ベクトルを変化させるような操作を考える。この操作は500回以上やっても500回やったのと同じ(500回以上前に付けた文字列は 「i文字目までマッチしている」に影響しないから) ooo
545H: ビットごとに制約がついているものとみなし、包除原理を使う。つまり、Σ(Sの元の桁の制約をすべて満たさない個数)(-1)^|S| を全てのSについて求める。集合Sを固定する。(Sの元の桁が全て1の要素の数)はR/Bを自由に決めていい。Sの元の桁の制約を破らなければいけないため、その桁が0の要素はR/Bの片方に寄せる。どちらに寄せるか2^|S|通りあるが、このうちi桁目とj桁目がどちらも0のAの要素があると、自由度が1減る。こんな感じの連結成分の個数を数えればいい。22020*20使うとTLEするので、探索にして毎ステップの計算がO(桁)になるようにする。 ooo
577H: それぞれのセルに、左右で塗るか上下で塗るかを割り当てることにすると、そのコストは (隣り合うセルで左右の塗りが異なる組+上下に塗るが上下にもうセルがない辺+左右に塗るが左右にもうセルがない辺)/2となる。(始点と終点を両方数えていることになるため) これはフローに変形できる。隣り合うセルの間に辺を、上下にセルのない辺にはSから辺を、左右…はTに辺を貼る。(最小カットを考えると理解しやすい) ooo
587H: ある辺の張り方が3彩色可能⇔ある長さWの文字列Sが存在し、全ての行について、その行の文字列がSかSのflip(NZ交換) NZのボードをグラフにしたとき、内部で次数が奇数の点があってはいけないことを考えると確かにこれが必要になる(もっと自然な導き方あるのかな…) あとはグラフをbitmaskとかで作りdfs、辞書順greedy ooo
590H: 始点からの最短経路長は、辺で結ばれたものの絶対値が1以下で、0以外は正ならなんでもOK.i番目の頂点への最短経路長がk以下かどうか、という頂点をそれぞれ作り、最小カットを求めればいい。(S側が正しくない述語、T側が正しい述語ととらえると、(i,k) -> (i,k+1)には(want[i]-k+1)2の辺を、さらに辺でつながった(i,j)には(i,k+1)->(j,k)にINFの辺を張ればよい) ooo
KUPC_K_Xor回廊: 綺麗な上汎用性が高そう。今更解いた。 ooo
667H: 順列が作るサイクルに注目する。両側にあるサイクル2つは対消滅できる。(サイズn,mとする。0-0,n-1-m-1,0-i(0<i<m-1),i-0(0<i<n-1),0-m-1,n-1-0の順でswapすれば綺麗に消える) これを使えば同じ側にあるサイクル2つも対消滅できる。サイクル1つは、i-0(0<=i<n),0-0とswapすれば消える。 ooo
518H: 分割統治を考えてみると、O(L2logK)でできる(行列を持つ必要はなくて、なぜならどの行も1行目にxorで入れ替えたものだから) 実は2つの間の(indexをxor、中身を掛け算)の畳み込みはO(NlogN)でできる。X=(A|B),Y=(C|D)とすると、Z=X$Y=(((A+B)$(B+D)+(A-B)$(C-D))/2,*1/2)でできる($は↑の演算) 合計でO(L log L logK) ooo

*1:A+B)$(B+D)-(A-B)$(C-D

ICPC Bangkok '16

ICPC バンコク大会に行ってきました.とても楽しかったです(小並感)久しぶりに更新。

1日目

  • 午前中に荷造りをして夕方成田から飛んだ.
  • 現地23時ごろに空港に着いた.自力ホテルまで移動を想定していたら,大会の迎えが来てくれた.ありがたい
  • 会津のチームもいたのでここで会釈したりした.
  • ここで換金するつもりが,迎えを待たせると悪いのでお金を換えずにホテルへ向かった.中心地に行くと両替できなさそうなので少し不安(この後クレジットカードでキャッシングを試みたけど結局ダメだったので,海外キャッシングの使えるwafrelkaに借りた)
  • ホテルに着く.腹が空きまくるので,近くにあるセブンイレブンでバーガーみたいなのを買った.人畜無害そうな見た目をしつつメチャクチャ辛いのでびっくりした
  • シャワーを浴びようとするけどお湯の温め方が分からないので水のまま浴びた.それでも大丈夫なぐらい暖かい
  • 寝ようとするもあまりに暑くて眠れないので,クーラーの主電源を直接叩いて点けた(実はリモコンがあったのだが,隣の藤原を起こすとよくないので電気をあまり点けていなくて気づかなかった)

2日目

  • 朝7時?とかに起きる.睡眠好きなので明らかに寝足りない
  • 大会が大学までのバン(ちょっとデカい10人乗りぐらいの車)を出してくれた.この後も移動は全部やってくれて助かった.1kmちょいとはいえ暑いので歩くと大変だったかもしれない
  • 時間があるので,食堂で朝ごはんを食べる.普通のメニューが30バーツぐらい(=100円)でうれC この前行ったときは空港からアクセスのいいレストランだったので100バーツぐらいはした気がする
  • 登録をしたりポロシャツを貰ったりする.ちょうど喪服期間だったので,選手が灰色で運営が黒だったりで珍しい(大体カラフルなので)
  • 開会式で踊りとかを見て,ルールの説明などがあった.早起きなのでまだ11時とかでビックリする
  • 午後はプラクティスがあった.ライブラリはこの日提出するルールで持ち込み忘れたので,プラクティス中に頑張って書いて印刷したりした(CxivDxiv伝統)(なお使う機会はなかった)
  • どうやら問題文やverdictが微妙に曖昧で他の人は困ってたらしい(伝聞)
  • この後buddyと呼ばれるガイドさんが,美術館や寺院やデパートに行きたいか聞いてきて,結局そのほとんどに連れて行ってもらった.本当に親切で,選手10人に対して6人ぐらいガイドがついててHuman Resourceを感じた.割とガイドさんたちの思いつきだった気がするけど,市内を自分で回るのは骨が折れるので本当にありがたい
  • ホテルに帰ったあと夜ご飯を食べに近くのフードコートみたいなところに行く.タイ料理があまりなかったけどその中で唯一面白そうだったタイすき焼きを食べに行く.
  • 肉に生卵がかかったものが出されて,卵をくぐらせた状態で茹でるやつ.美味しかった.
  • 寝る

3日目

  • この日は8時に起きる.それでも眠い
  • ギリギリまで寮にいたら朝ごはんを買う時間がなくなった.悲し
  • またバンで会場まで行って,入場などを済ませる.
  • 開始まで結構時間があったので,藤原とdegwerの顔の特徴をひたすら列挙してたら藤原から嫌な顔をされた.(ex.ホクロが左右対称な位置にない,鼻の先端が丸いとか)
  • ゆったりしてたら突然開始して緊張する.予め適度に緊張しておいたほうがいい
  • とりあえず12問のうち真ん中の4問を担当する.
  • E:問題長い,木,読むの後回し
  • F:文字列・ゲーム,読む,少なくともめんどくさそう.
  • G:単純なので考えてみるとフィボナッチ数のKの倍数項の和となることが分かる.そこから先は苦手の臭いがしたので誰かに投げようと思い後回し
  • H:問題文が分かりづらすぎる.
  • 読んでる間にdegwerがL?を通して,PCが空いていたので,慌てて手のつけられそうなEを読んで,案の定手はつけられそうだったので書き始める.必要な実装が多すぎて初手でやるのは間違いだったかな
  • 誰かが書ける問題でき次第代わりつつEを書いていく.実装できない間はHを読んだりFを詰めたりした.
  • Hの方が明らかに簡単なので,PCが空いたときに書いてみる.サンプルが合わない.誤読を心配し後回し
  • しばらくしてるとHのClarが入ってサンプルが間違っていることが分かる.少しデバッグして,提出(AC)
  • Eがぼちぼち完成する.出す.WA
  • なんか間違えてた.AC
  • Fが分かった気がしたので書く.微妙に考察が足りなかったので詰まりつつも出す.WA
  • フォーマットを間違えてたので出す.WA
  • 何が間違ってるのかさっぱり分からない…と思ってたら,まだフォーマットが間違ってた.AC
  • 藤原も同じ原因で,実質2AC獲得みたいなもんよ.これでかなりペナルティ無駄にした
  • Jをdegwerが書いてて,AとKが取り組めそうだったがAは時間がなさそうなのでKを考える.詰まりはしたが通すまではいかなかった.無念
  • コンテスト後はみんなでワイワイして,晩餐会の会場へ向かった.
  • 腹が減ってたけど飯までがやたらと長い,まあしょうがない.degwerとかがナプキン?で鶴を折って圧倒的交流してた.
  • 結果発表は,Seoul National UnivがFを通せば負ける展開だったが,FでWAを大量発生させてて助かった.2位
  • タイの偉い人に「お腹すいたでしょ!ようやくディナーだよ,ガハハ!」みたいな声を掛けられる.やっぱりな
  • 飯!美味しかった.
  • 帰って寝る

4日目

  • この日はアユタヤ観光.朝6時前に起きる.
  • バスで1時間強かかるっぽく,あまりに眠いのでバスで寝る.
  • 最初の寺院はビルマに破壊された遺跡で,なんとも不安になる形をしてた(いろいろ傾いてたり)
  • 次も似た感じの寺院だけど,今度はredecorationされてて色も違うし形もちゃんとしてる.階段の傾斜がすごくて登ると怖い.あと観光用の象が客を乗せて歩いてた
  • 次に水上マーケットにいった.ランチでトムヤムラーメンみたいなのを食べた.うまE.その近くで時代劇みたいなのを見た.ビルマとの戦いを扱ってた.タイが負けてる間に時間が迫ってきたのでバスに戻る.
  • 次もまた寺院に行った.仏像が寝てるものとか,大量の鶏の像とかがあった.
  • 帰りはbuddyとスマホで単語当てゲームをやってた.英語の勉強になりました(小並感)
  • ちょっと時間があったので,夕食を食べてお土産を買いに行く.
  • 空港まで送ってもらって,帰りの飛行機に乗る.

カプセルホテル宿泊記

情報オリンピック本選で1日目と2日目の間に家に帰るのが面倒だったので新宿でカプセルホテルを取りました。これからカプセルホテルに泊まる予定のある人は参考になることがあるかもしれません。


2015/2/7 に 新宿区役所前カプセルホテル に泊まっていました。 ビルの3-8階がホテルになってて少し見つけづらい。あと歌舞伎町に近いので厳重な注意が必要。
最初はフロントに行ってログインした。フロントに居る人を見ると客のうち1/4ぐらいは外国人ぽい感じで、従業員も完全に英語のプロだった。
ロッカーの鍵を預かるが、腕にどうやって付けるかがよく分かららなかったので教わる。力が足りないだけだった。
ロッカーに行って貴重品を置いて、風呂に入る。ロッカーはそこまで幅が大きくないので大きなスーツケースは入らなさそうだった。風呂はオリセンより豪華なぐらいで、ジャグジー・水風呂・普通の風呂・サウナがあった。洗面所には使い捨ての歯ブラシ・髭剃りがあって、小物を忘れた人でも大丈夫。
ロッカーには予め館内着とバスタオルが入っていてこれも助かる。
風呂に上がってから休憩スペースに行ったら思いの外ふつうのホテルっぽい内装でビックリした。インスタント食品の自動販売機やレストラン・電子レンジ・コインロッカーなどいろいろあった。
ひとまず部屋を見てみると、大体大きさは2段ベッドの片割れぐらいの大きさの壁に囲まれた領域がある、みたいな感じ。思ったよりは広かった(なんか棺桶より二回り大きいぐらいのがたくさんあるのかと思ってた)
f:id:hogloid:20150208104144j:plain
↑中からの写真
十分清潔だったけど、そもそもカプセルの部屋にカギが閉まらないのは問題かも。シャッターみたいなのを閉めると外側とは一応遮断されるけど、ある程度光は漏れてくるから完全に暗くないと眠れない人はアイマスクが必要。たまに宿泊階なのに喋る人がいて、音を気にする人は耳栓が必要。
部屋の空調も効いてて寝心地は普通によかったけど前述の光と音のせいであんまりよく寝れなかった。

朝になったら起きて着替えて鍵を返して出発。

まとめると、カプセルホテルは以下のような人に向いています:

  • 安く泊まりたい人
    • 他のふつうの宿の半額以下ぐらいで泊まれます
  • カプセルホテルに一度は泊まってみたいという人
    • 一度は泊まっても悪くはないです
  • 治安・光・音を特に気にしない人
    • これらを気にしないならデメリットはほとんどないです
  • 何も泊まる用の服・器具を持っていないが寝る必要のある人
    • ほぼすべてが用意されています


以下のような人には向いていません

  • セキュリティ意識の高い人
    • 鍵で閉められていない空間に寝るのがそもそも無理という人もいるはず。ロッカーも、頑張ればぶち壊せることが知られています
  • 人のたくさんいる場所が苦手な人
    • 基本的に小さいスペースを最大限に利用しているためいろんな場所の人口密度が高めです
  • 狭い空間で寝るのが嫌な人
    • 圧迫感を感じる人もいるかも

僕としては、もうそんなに積極的に泊まりたくはないです。鍵がないスペースに寝るというのはちょっとこわい。

今までに作った問題たち

そろそろ作った問題たちが増えてきそうなので、それらをまとめて感想を書いておきます。
まとめるのも面倒になるほどたくさん問題を作るぞ:punch:

  • Codeforces #162 Div1C/Div2E Choosing Balls
    • 初めて放出した問題。最初はa,b>=0だったり、クエリーじゃなくてO(NlogN)も許さざるを得ない感じだったけどsnukeやりんごさんの助けでCに置けるぐらいの問題になった。そもそもこの頃は問題のテストケースとかも作らなければいけないとは知らなかったなあ。初めてpolygon(CFの作問プラットフォーム)を使った。
  • Codeforces #263 Div1B/Div2D Appleman and Tree
    • 原案は僕で準備はsnuke。B問題が却下されたけど、日程は決まってしまったっぽいので大急ぎで作ったのがコレ。割と典型っぽいし特に思い入れは無し。
  • Codeforces #263 Div1E Appleman and a Game
    • snukeと一緒に原案を作った。僕だけだったらここまで難しくはできなかったなあ。ちなみにこのCFは夏ごろに3人でsnuke宅に集まって色々しながら原案を作ってた。楽しかったしこういう形式の作問もいいと思う:) この問題は難しい知識もいらないけどちゃんと難しい問題になってて好きです。(まだあんまり作ってないから何ともだけど)
  • Codeforces #286 Div1D Mr. Kitayuta's Colorful Graph
    • evima&yosupoとの合作回。想定解だと、ただ次数の小さい方に注目するだけでオーダーに√Qが出てくるのが面白いなあ、と思ったけど、ふつうの平方分割解もあるし、やっぱり√系の解法のものはFull Feedbackの場所に出すべきという思いを強くしました。div2のはこれの簡単版

今年の目標

必須

  • 人間的に成長する意思を持ち続ける
    • そろそろこれやらないと社会的死が待ってる
  • CF IGM
    • +29するだけでいいしヘーキヘーキ インフレしてるし
  • TC 2700
    • こっちはあんまり伸びる気がしないんだよなあ

できたら

  • 国際少人数onsite(TCO,GCJ,Yandex,顔本杯)に引っかかる
    • そろそろ1回ぐらい出来て欲しい(願望)
  • CF Top10に一瞬でもいいので入る
    • こちらはインフレ関係ないしキツそう
  • TC 2800
    • まあ一歩ずつ。今年で3000載るとはまったく思えないし

今年の目標を振り返る

恒例。放ったらかしでは意味がないんじゃ。
今年の目標 - hogloidのブログ

必須目標

  • CF Rating で2350をつける
    • つきました
  • TC Rating で2550をつける
    • つきました
  • 進級
    • まだよくわかんない

これぐらいは

  • 上の状態で年越し
    • はい
  • 上+100ぐらいはつける(どっちも)
    • まあ両方大体ついたかな(SRMの方はちょっと足りない)
  • (あれば)国内コンテストで5位以内 ex.天プロ
    • テンプロは6位だった。他はかなり微妙だったなあ・・・ICPCはよかったけどあれは団体なので別。
  • 不可を出さない
    • 1学期は防げた。なお2学期

やりたいなあ

  • 国際オンサイト(TCO,GCJ,Yandex.Algo etc..)に出る
    • ダメみたいですね
  • 言葉遊びでウェイwする
    • ???何を言っているんだこの人は

雑記なのでいずれ消えてるかも。

AOJ 2374 RabbitLunch

概要

日本語なので読んでね
RabbitLunch | Aizu Online Judge


































































解法

O(NlogN),O(Nlog^2N) のやり方もいくつかありますが、O(N) で解くことをオススメします
ヒントはフロー(僕はこれをsnukeに教えてもらった)
かなり面白いので、すぐに見ないほうがいいかも。
見たい人は下までスクロール




















































与えられた条件を二部グラフのフローの形にしてみると、
source-人参(流量は人参の個数)
人参-キウイ(m*n の辺を張る。流量はすべて1)
キウイ-sink(流量はキウイの個数)
の辺を張る。

求める値はこのグラフでの最大フロー
これは最小カットに等しい。

source-人参の辺からK本、キウイ-sinkの辺からL本カットに入れると、
人参-キウイの(M-K)*(N-L)本を切ればよい。

よって、source-人参の辺・キウイ-sinkの辺 を切るときは、流量の小さいものから切っていけばいい。

source-人参の辺の切る数をiとして0...Nまで動かす。
人参-キウイ、キウイ-sink での最小カットは、
X軸にキウイ-sinkの切る辺の数を取ると、
f:id:hogloid:20141115234413p:plain

この2つのグラフを合わせたような感じになる。

キウイ-sinkのグラフは、切る辺は小さい順に並んでいるので、下に凸
人参-キウイのグラフはそもそも直線

となり、和を取ったグラフも下に凸
なので、局所解が大域解になってる

ところで、iを1つ大きくした時、キウイ-sinkのグラフは変わらず、
人参-キウイのグラフは傾きが小さくなる。
このとき、キウイ-sinkの切る数の解は少なくなる方向にのみ動くことがわかる。

よって、iを増やしながら、しゃくとり法をすればいいことが分かる。
ソートをバケツソートで行うと、すべてO(N)

ソースコード
AIZU ONLINE JUDGE: Code Review