2019-05-06

okimochi練(5/6)

国内予選2017と2015をやった。

2017

こるとんがAを通す。僕がBを見て書こうとするが詰まり、その間にCをこるとんに通してもらう。その間にBの誤読に気づき(おい)、落ち着いて通す。申し訳なかったけど実はこれはそこそこ苦戦するチームもあったそうなのでセーフ(いいえ)。

その後こるとんがFを難なく通す。その間にDもEもGもわからないと言っていた。こるとんがDはnm<=500が本質だと気づき、こるとんとrisujirohで通す。その後Gをrisujirohが思いつきこるとんが通す。Eをなんとか通そうとするが間に合わず終わり。僕は暇だったのでHを見ていたけど探索しましょうという感じだったのでまあ無理。

反省としては、Dの制約をちゃんと見るべきだった。ここは短縮できたと思うが、こういう問題もあるのか、と思ってしまった。本番9位相当で、まずまずと言ったところだった。The University of Tokyoが上位にいっぱいいた。

2015

このセットヤバすぎ。Aをrisujiroh、Bを僕が難なく通す。Cはこるとんが無理そうだったのでrisujirohが通す。その間にDはこるとんが思いつき実装、僕がその間にEFを見るがわからず、risujirohと一緒にFについてあーたこーだ言っていた。

DがTLEで計算量的にダメということになる。考え直してAC。その後も苦悶するがこるとんがEを通す(すごい)。Fもやろうとしたが実装方針が立たず終わり。

本番12位相当。Dは本番なら手元で回して結果を提出なので、ペナもタイムロスもないとすると5~6位になるらしい。Fの想定解を見て驚く(天才か？)。ちなみに別解として考えられていたものはコンテスト中に案があった。

Eくらいまでをできるだけ早く解くことが鍵になりそうという感触を得た。AOJ-ICPCの黄色まではしっかり埋めた方が良さそう、という話になった。普通に難しいとはいえもうちょっと仕事したい。

2019-04-30

okimochi練(4/30)

5時間セットをheno_worldとやった。

セットはACM-ICPC 2016-2017 Asia region Daejeon(韓国セット)

Aを読むがわからない。

B:こるとんが簡単とか言うのでやってもらう、なんか入力形式がめんどくさかったみたいで2ペナ踏んでたけど通る。

risujirohがCをやる。実装が大変そうだった。すぐ通らなさそうだったのでbfsするだけだったGを僕が書いて通る。人のPCで少し打ちにくかった。

Iがやるだけらしいのでこるとんがバグらせながら通す。その後Cも通る。

Lが簡単な木DPじゃーんと思ったので僕が書く。普通に嘘を出したあと微修正して確信を持って提出するが通らない(は？)。さすがに意味不明なので2人を呼んでデバッグしてもらうが原因がわからない。stackoverflowを疑うがそうでもなさそうなのと、heno_worldも通っていないのを見てジャッジがおかしいと判断し撤退。ここに30分使ってしまって本当にもったいない。

Dをこるとんが頑張る。詰めきれずに1度risujirohがFをやるが、やはり詰めきれずDに戻って通す(すごい)。僕がHが解けたと主張したので書くが実装中に怪しいことに気づきこるとんと議論して木DPかーと思いつつ時間がなく諦める。Fも嘘だったとわかり終わり。

Aの考察をてきとうに言っていたがだいたい合ってたらしい。難しいね。

反省点

個人としては、Hがあやふやなまま実装に走ったこと。みんなで冷静にやれば解き切れたと思う。あと順位表から明らかに地雷なFをrisujirohに軽い気持ちで投げてしまったこと。(他が思いつかなさそうだったけどね…。)

チームとしては、力を注ぐべき問題を定期的に判断すること。あと、問題が難易度順じゃないセットは最初に全部に目を通すこと(G,Iが遅かった)。

ジャッジは仕方ない。Hも壊れてたらしいね。

2019-03-31

エクサウィザーズ2019-D:Modulo Operations

めちゃくちゃ時間をかけてしまったけどこういうのが通せるようになったのは成長かな...。

問題

D - Modulo Operations

考察過程・解法

　確率に落とすのは苦手なので総和のままやった。
　まず最初に， $s_i\lt s_j$ という2つの集合の要素について， $s_i$ で余りをとった値に， $s_j$ で余りをとってもその値は変わらないことに気付こう。したがって， $s$ をソートして新たに番号を振り直すことにする。すると， $s_1,s_2,\cdots,s_i$ を作ってできた値を $v$ とすると， $v$ は $s_{i+1},\cdots,s_N$ たちの影響を受けない。このことを用いて，dpを組み立てていこう。
　 $dp_{i,j}$ を「黒板に $j$ が書かれている状態から始めて， $s_1,s_2,\cdots,s_i$ のみを選んで操作をしたときの，最後に黒板に書かれる数字の総和」としよう。こうすると， $dp_{i-1,X (\mathrm{mod} s_i)}\times {}_{N-1} \mathrm{P} _{N-i}$ の $i$ についての総和が答えとなる。この理由を説明しよう。 $s_i$ を先頭にすると決め打つと，次に書かれる数は $X (\mathrm{mod} s_i)$ となる。そこからの操作はどうなるかというと， $s_1$ から $s_{i-1}$ までの順番は $dp$ の部分に表現されているから，残りの $N-i$ 個の並べ方だけが自由である。従って，上の式が「 $s_i$ を最初に選んだ時の，最後に黒板に書かれる数の総和」を表しており，これを $i=1,2,\cdots,N$ について足し合わせれば，すべての順列について考えたことになる。
　最後にdpの遷移を考えよう。 $j$ が黒板に書かれているとして，使える数が $s_{i-1}$ までから $s_i$ までに増えたときに，どのような操作が可能になるだろうか？まず，最初に $s_i$ を選ぶとすると，黒板の数は $j (\mathrm{mod} s_i)$ となるから，その後の操作によってできる数の総和はもちろん $dp_{i-1,j (\mathrm{mod} s_i)}$ となる。最初に $s_{i-1}$ 以下の数を選ぶとすると，その後の操作によってできる数の総和は $dp_{i-1,j}\times (i-1)$ となる。 $i-1$ がかかっているが，最初に $s_{i-1}$ 以下の数を選んだので， $s_i$ はどのタイミングで選んでも総和には影響しない。よって， $s_i$ を入れるタイミングの数だけ $dp_{i-1,j}$ が加算されるということになる。
　計算量は $O(NX)$ であり，C++なら十分間に合う。Pythonだと心配。

実装

Submission #4777838 - ExaWizards 2019

$i=1$ のときだけ注意。もうちょっとうまく書けるかも。

最近調子が良いので黄色が見えてきた。

2019-03-23

yukicoder contest 209:writerをしました

　こんにちは。2019/3/22(金) 21:20~23:20のyukicoder contest 209(yukicoder contest 209 - yukicoder)
でwriterをさせていただきました。初めてのことで開始前は尋常じゃなく緊張しましたが，およそ160人の方に参加していただけました。ご参加ありがとうございました！
　以下では，準備の話とかコンテスト中のおきもちとかをてきとうに書いていきます。

A:野菜が苦手

　☆1が必要だなと思って作りました。野菜が苦手なのは本当で，特定の条件を満たさない限り野菜が食べられません(肉が十分量あるとかはその1つです)。最初は $O(A)$ を許していなかったのですが，☆1ということでやめました。コンテストでは150人程度の方がACしていました。

B:UMG

　バランス調整のために作りました。制約と計算量を意識しましょうという問題で，初心者向けとしては良かったのではと思っています。UMGというのは僕がいつも持ち歩いているウマゴン(UMAGON)のことです。他の問題文でも出てくるumgくんもそうです。こちらもおおよそ150人程度の方がACをしていました。

C:木を道に

　今回のセットの中で最初に生えたのはこの問題でした。なぜ生えたのか覚えていませんが，この位置として良い問題だったと思います。証明を考えると☆2.5でもよかったかもしれませんね。
　結局分岐の数を数えればよいということで，想定解は $\sum \max((次数)-2,0)$ でしたが， $(葉の数)-2$ で出している方も多かったです。よく考えると両者は一致するのでどちらでも良いです。
　僕やtesterさんは最初にこの問題を考えたとき，木の直径でなんとかするのかと思っていたのですが，提出でもこれをやってWAという方がそこそこ見受けられました。提出を見ながらわかるなあ思いつつとにやけていました。コンテスト中のACは120人程度でした。

D:umg tours

　ツーリストチケットと言いたかっただけなのですが，結果的に教育的な問題になったのでここに置きました。頂点に状態を持たせてDijkstra法を行うのはありがちな解法で，初めてという方にはいい練習になったのではないでしょうか。コンテスト中のACは70人程度でした。もう少し解かれると思っていましたが，頂点を増やしてから適切に辺を張る必要があったりなど，詰める段階や実装面では難しい部分があったと思います。
　ところで，この問題はC++でも実行時間がかかり，恐らくこの問題が原因でコンテスト中にジャッジが詰まってしまいました。ジャッジについては少し運営の方と相談すべきだったかもしれません。また，Python勢は制限時間が4秒でもちょっと厳しかったと思います。制約を小さくするのはなんかなあと思ったので許してください。

E:Kaiten Sushi?

　ボスとして用意しました。元々は「席が回る回転寿司屋で問題を作ろう！」というコンセプトで考え始めて(は？)，ボツ問を生やしつつこの問題に辿り着きました。実は解に気付いて証明をつけるのに数時間かかり，またtesterさんも同様で，証明までやるのはかなり大変な問題，という想定でした。想定解としては，ある位置での $(寿司の個数)-(お茶の個数)$ を見ると必要な最小の周回数がわかり，さらに最後に飲むことのできるお茶の位置も寿司とお茶の配置だけでわかるという，芸術点の高いものを用意していました。解けた方も解けなかった方も，是非とも解説を読んでほしいです。特にtesterさんは明示的に解を構成してくれました。
　ところがコンテストでは，寿司とお茶の取り方について貪欲が可能で，多くの人にsetなどを用いて貪欲をシミュレーションする解法で通されてしまいました。こちら側ではこの貪欲のちゃんとした証明が生やせていなかったのですが，普通に正しいようです。コンテスト中にtesterさんや既に全完していたtさんと証明を検討していました。提出をちゃんと見ると，想定解に近い方法で通している人も見受けられたので，それは嬉しかったです。
　結果的にコンテスト中のACは20人程度と，ボスとして十分機能したと考えています。解けた方も解けなかった方も，是非とも解説を読んでほしいです(大事なことなので2回書きました)。
　そういえば，「最近開店したというKaiten Sushi」というギャグには気付きましたか？

全体を通して

　難易度のバランスが不安だったのですが，結果的におおよそのAC者数が150-150-120-70-20だったのを見ると，良いバランスだったのではと思っています。DまではABCを意識，Eは暖色の人用という気持ちでしたが，狙い通りのセットになったと思います。コンテスト後は良セットだったという感想も多く見受けられ，嬉しい限りでした。

最後に

　またセットでやるとしたら夏休み頃なのかなあと思っています。競プロの実力としてはまだまだなので，力をつけて作問のレパートリーが増えればよいなあと思っています。
　時間があったので半分ノリで作問してしまいましたが，多くの人に解いてもらって，感想をいただけるのは本当に嬉しかったです。問題を見てくださったtesterの皆さん，参加者のみなさん，そしてジャッジシステムを提供してくださっているyukiさん，本当にありがとうございました！

2019-02-16

第3回日本橋ハーフマラソン予選

失敗したと思ったが(75位で，恐らくボーダーだが)予選通過したので，少し復習した。

A:ツーリストXの旅行計画

A - ツーリストXの旅行計画

コンテスト中にやったこと

山登り/焼きなましでよさそうだと思ったので， $0,1,\cdots,N-1$ という順から初めて，2点をswapする山登り法を試した。山登り法というのは

現在の状態から「少し変わった状態」のスコアを計算して，それが現在の状態のスコアより良ければ，「少し変わった状態」を現在の状態とする。

ということを繰り返すものである。この「少し変わった状態」を近傍と呼ぶ。2点swapというのは，点を訪問する順番を表した順列において，2点を入れ替えたものを近傍とするという意味である。これをすると28万点くらいになる。
Submission #4232922 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザの結果はこちら。
f:id:sigma1113:20190216174359p:plain
ところで，分散の計算には「 $(2乗の平均値)-(平均値の2乗)$ 」が使える。これを用いれば，実は近傍のスコアの計算を $O(1)$ で済ませることができる。つまり状態として訪問順の他に，距離の総和と距離の2乗和をもっておけば，点を入れ替えたときに減る距離と増える距離をそれぞれ計算することができて，これは高々4箇所であるので， $O(1)$ で更新が済むというわけである。これは差分更新と呼ばれたりする。
しかし，これをやればスコア伸びるでしょーと思って出したのだが，なんと全く伸びない。このあとBを解き，Aに戻ってきてからいろいろと試したが，結局28万点のまま終了した(152位)。悲しいね。

反省会

山登り/焼きなましというのは悪くなかった。問題は近傍の選び方であった。2点swapでは，パスを構成する辺が4つ変わっていることになる。これは全然「少し」変わった状態じゃないという問題があった。ここから，近傍として「パスのうち2辺を変更する」ということを考える。これは2-optと呼ばれる手法(?)らしい。そんなこと簡単にできるのかとちょっと思うが，訪問する順番の順列のある区間をreverseするだけでできる(絵を描くとわかる)。
なんとこれだけでスコアが150万点くらいになる(!?)。およそ5倍になっている。コンテスト終了後，TwitterのTLでは，「スコアが5倍になった」というツイートが散見された。
Submission #4238797 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。大幅に改善している...。
f:id:sigma1113:20190216180528p:plain
この提出は差分更新をしていないのだが，2点swapのときと同様に差分更新にして，焼きなまし法に変更すると，220万点が出る(30位相当)。焼きなまし法はパラメータの調整が面倒なのだが，以下の記事を参考にいろいろ試したらうまくいった。ありがとうございます。
焼きなまし法の適用メモ - Negative/Positive Thinking
提出はこちら。
Submission #4276320 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。
f:id:sigma1113:20190216181033p:plain

上位陣の考察を見ていると，使う辺の長さの範囲を限定したり，ある長さを決め打ってその長さに近い辺を使うということをしていた。この長さを決め打つという手法は有効らしく，「長さを乱数で決め打って，決め打った長さに最も近いものを選びながら，先頭から順番にパスを構成していく」だけで80万点が出るらしい(自分は試していない)。マラソンわかりません。

B:ファーマーXの収穫計画

B - ファーマーXの収穫計画

コンテスト中にやったこと

大きい数字である9や8をたくさん作って収穫したいと思った。ところが，1とか2を9にしても手数がかかるのでよくなさそうだ。そこで，てきとうに閾値を決めて，閾値以上のマスは収穫したい数字にする，ということをした。閾値は収穫したい数字の半分以上とした。収穫したい数字は9から始めて，9を収穫しきったら8を試す....ということを繰り返した。実装上はBFSを何回かすることになる。なんとこれだけで54万点が出る。
さらに，9のマスはいくつかあるわけだが，収穫する順番を乱数で決め，時間いっぱい試すことにより，55万点に乗った。これが最終スコアになった(38位)。やったことは非常にシンプルだが，これでそこそこ上位が取れたのは助かった。
Submission #4236103 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。ほとんど9で収穫している。よく見ると8も少しある。
f:id:sigma1113:20190216183234p:plain

反省会

大きい順にとる，というだけでは，手数の問題をまだ十分に考慮しきれていない。ある区画を収穫するときに，その区画を収穫すると1手あたり何点得られるか？ということを考えるのは，言われてみれば自然なことのように思える(まあ気づけなかったんですが...)。そこで，「ある区画を収穫するときに得られる得点/その区画を収穫するまでにかかる手数」を評価値とする。このとき，「その区画を収穫するまでにかかる手数」は小さくしたいから，収穫するマスの値を $K$ とすると，「隣接する $K$ マスの値 $K$ にするのに必要な手数の最小値」を求める必要があるが，これはbfsの際に優先度付きqueueを用いることで可能になる。
すべてのマスについて評価値を計算した後，それが大きい順に実際に手入れ，収穫をする。評価値が最大でないマスは，すでに本当は使いたかったマスが収穫されていしまっているということがあり得るが，その場合は評価値を再計算する。これを手数の限り繰り返す。
なんとこれをすると60万点に乗り，2位相当となる(!)。何を評価値すればよいかということをしっかり考えることが重要だと思わされた。
Submission #4267434 - 第3回 RCO日本橋ハーフマラソン予選
ビジュアライザはこちら。要はコスパの良い順なので，さまざまな数字が収穫されている。また，収穫されているマスが各段に増えている。
f:id:sigma1113:20190216185003p:plain

せっかくなので本戦も頑張りたい。

2019-02-06

AGC009-C:Division into two

きれいな問題だなあと思った。

問題

C - Division into Two

解法

　簡単のため $A\lt B$ とする。逆のときはswapしても問題ない。こんなのdpしかないやろという見た目がするので，dpを考える。制約を無視すれば，今何番目の数を見てるかということと， $X$ または $Y$ に最後に振り分けた数はどれだったかということが必要に見える。そこで $dp_{i.j}$ を「 $i$ 番目まで振り分け済みで，最後に $Y$ に振り分けた番号が $j$ のときの振り分け方の総数」とできる。遷移は，① $S_i-S_{i-1}\geq A$ なら $dp_{i-1,j}$ から $dp_{i,j}$ に遷移できる。また， $S_0 = -\infty$ として， $0\leq j \leq i-1$ について，② $S_i-S_j\geq B$ かつ， $j+1$ から $i$ の間の $2$ 項間の差がすべて $A$ 以上であるときに， $dp_{i-1,j}$ から $dp_{i,i}$ に遷移できる。(なぜ $j+1$ からかというと， $S_j-S_{j+1}\lt A$ でも， $S_j$ を $Y$ に振り分けているから， $j+1$ は $X$ に振り分ければ問題ないからである。)もちろんこれを愚直にやると $O(N^3)$ で，到底間に合わない。
　よく考える。まず，「 $j$ から $i$ の間の $2$ 項間の差がすべて $A$ 以上である」かということをdpの更新のときに逐一調べる必要はない。つまり， $S_i-S_{i-1}\lt A$ であれば， $S_{i-1}$ より手前の数は，これ以降②タイプの遷移が不可能だとわかるので，そういう番号を管理する変数を持っておけばよい。これを $id$ とし，定義を「現時点で②のタイプの遷移が可能な番号の最小値」とする。さらに， $S_i-S_j\geq B$ をみたす最大の $j$ を二分探索し，それを $s$ とすると， $dp_{i,j}$ に遷移してくるのは $j$ の $2$ つ目の添え字が $id$ から $s$ までの数である。だから，累積和を取っておけば②のタイプの遷移は $O(\log N)$ で可能である。
　タイプ①の遷移だが，これは $1$ つ目の添え字が $1$ 増えるだけである。タイプ②の遷移も， $1$ つの目の添え字は $1$ 増えるだけだから，結局 $dp_i$ を「最後に $Y$ に振り分けた数の番号が $i$ であるときの振り分け方の総数」として，これを $i$ が小さい順に埋めれば十分である。最後に，明らかに答えが $0$ になるパターンの存在に気を付けよう。それは，ある $i$ が存在して $S_i-S_{i-2}\lt A$ となることである。 $S_{i-1}$ を $X$ にも $Y$ にも振り分けることができなくなるからだ。
　以上より，次のようにすればよい。

$S_i-S_{i-2}\lt A$ となる $i$ があったら答えは $0$ 。
$dp_i$ を「最後に $Y$ に振り分けた数の番号が $i$ であるときの振り分け方の総数」とし， $dp_0=1$ とする。また， $id$ を「現時点で遷移してくることが可能な番号の最小値」とし， $id=0$ とする。 $i$ が小さい順にこれを埋める。最初に， $dp_i += dp_{i-1}$ とする。 $S_i-S_j\geq B$ をみたす最大の $j$ を $s$ とし， $s\geq id$ であれば $dp_i += dp_s-dp_{id-1}$ とする( $s\lt id$ のときは遷移できない)。最後に， $S_i-S_{i-1}\lt A$ であれば $id=i-1$ とする。
答えは， $dp_N-dp_{id-1}$ である。

実装

Submission #4183566 - AtCoder Grand Contest 009
二分探索のとき， $s=0$ のときの扱いに注意。あと $id=0$ のときも注意。

ちゃんと考察すると綺麗な遷移でコードも短い，好き。

2019-01-31

CODE THANKS FESTIVAL 2018-H:Median Game

これはわかればシンプルで楽に解けるので好き。

問題

H - Median Game

解法

このゲームでは，ある列の中央値がゲームのスコアになり，それを求めよと言われている(偶数のときは2つ候補があるが，大きいほうをとる)。中央値を求める問題では二分探索が有効である。中央値が $x$ 以上となるか？という質問に答えるには，数列の中に $x$ より以上の数が半分以上含まれるかを調べるだけでよく，これは比較的容易にできるためである。

それでは，「ゲームのスコアは $x$ 以上になるか？」という問題に答えよう(この問題は $x$ について答えが単調なので，二分探索が使える)。このとき，Aliceはスコアを大きくしたいので， $x$ 以上の数を増やしたいはずである。一方Bobは，スコアを小さくしたいので， $x$ より小さい数を増やしたいはずである。この2人の戦いをdpによって見守ろう。

$dpAlice[i]$ :上から $i$ 枚目以降のカードが残っているときにAliceの手番で， $(x以上の個数)-(x未満の個数)$ の最大値
$dpBob[i]$ :上から $i$ 枚目以降のカードが残っているときにBobの手番で， $(x以上の個数)-(x未満の個数)$ の最小値

dpの遷移であるが，とりあえずAliceの手番のときを考えよう。今回はこのdpに $O(N^2)$ かけてよいので。 $i\lt j \leq N+1$ について，区間 $[i,j-1]$ のカードをとり， $j$ 枚目以降のカードを残してBobに手番を渡すとしよう( $j=N+1$ のときはゲーム終了という意味)。これらのカードの総和を $S$ とすると， $S$ と $x$ の大小によって $dpBob[j]$ に $1$ を足すか $-1$ を足すかすればよい。この結果の $j$ についての最大値が $dpAlice[i]$ である。Bobの手番のときも同様である。
dpの遷移は後ろから，つまり $i=N$ から行うことに注意。ゲームでdpをするときの定番だろう。「ゲームのスコアは $x$ 以上になるか？」という問題の答えは， $dpAlice[1]\geq 0$ のときYes，そうでないときNoである。