JOIでコードゴルフ１
JOIの問題を解いていたらいくつかの問題でShortest Codeが取れた。
最近の実装に対する意識の変化によるものだと思う。
記念にまとめておく。
グラフ系
春09 Advertisement(難易度8)
強連結成分分解
(795Byte→)673Byte
SCCが最もシンプルな形。
春10 Highway(難易度10)
オイラーツアー、最小共通祖先、セグメントツリー
(2210Byte→)1596Byte
セグメント木は様々な面から非再帰を用いる。
幾何
春07 Lines(難易度10)
線分の交点の重複排除
(1111Byte→)541Byte
複素数平面を使うと回転が簡単にできる。片方の線分を(0,0)→(0,a)の形にしてから内分の比を取ると、単純な式になる。
春08 Nightman(難易度10)
線分交差など
(1879Byte→)1481Byte
複素数平面で式を単純化。入力が整数であることから、微小な値だけずらすようなことをすることで、正確性を保ちつつ場合分けを回避できる。
春08 Belt(難易度10)
偏角の扱いなど
時間制限が10秒なので怪しい解法が通っているが、それを除けばShortest。
(1008Byte→)877Byte
本質的には他のコードと変わらない。
変数名が短い。
その他
本選09 博覧会(難易度10)
実装方針は複数考えられる。
(843Byte→)815Byte
４回転することで場合分け回避、二分探索で判定問題に落とすことで最大最小の扱いによるバグを回避。
JMO2019予選
自分は競技プログラミングに関して明らかに行き詰まっていて、最近ではレートさえ落ち始めたので、何かしようと思った。
社会に目を向けると、強い競技プログラマーは数学オリンピックも強そうということがわかった。
だから、数オリをやってみた。
とりあえず２０１９年のJMO予選をやった。
成果
一時間と数分で１から６までの六問を解いた。本選行きボーダーが５問らしいので、それには通過できた。（TAISA_が７問と主張していたので終了後は悲しい気持ちになっていたが、自分で調べると違っていた。）追加の一時間で７から９を考えたが、一問も解けなかった。１０以降は人間向けでないらしいので、やらなかった。
頭が良くなりそうという感想を持った。
内容
１問目
x(1+y(1+z))=31みたいな問題。
簡単な枝刈りで解ける。
正解：2分
２問目
(100p+10q+r)^2が{2,3,5,7}からなる５桁の数になるものを列挙するような問題。
一の位に注目すると、必ず5であることが分かる。
小さい方から調べていくが、三桁×三桁はすぐ六桁に上がるので、４つくらい調べれば良い。
正解：6分
３問目
3×3のマスに1~9を入れて、隣接したものの差が3以下になるようにする方法を数え上げる問題。
条件がかなり厳しいので、中心の値を決め打ってパズルをすると解ける。
正解：１７分
４問目
五角形の中で遊ぶ問題。
愚直に相似を取ると解ける。
正解：９分
５問目
n=97*a+32=100*b+33=103*c+34なる最小の自然数nを求める問題。
愚直にユークリッド互除法で解いた。
32*3+1=97、33*3+1=100、34*3+1=103を使うと楽に解けるらしい。
正解：１０分
６問目
１２０角形の頂点集合であって、頂角が18度の二等辺三角形がないようなものの最大のサイズを求める問題。
円と三角形の何かしらの公式を使って、中心からの角度が36度であると言い換える。
角度に注目すると、頂点のindexのmod6で独立なので、分けて考える。
すると、20個の頂点の中から(2,9,9)が生まれないように選ぶ問題になる。
偶奇で何かすることを考えると、奇数のindexのものを180度回転させることで、「三連続で頂点を選ばない」という制約に言い換えられる。
この制約なら、貪欲に取っていけば良い。
正解：１９分
AtCoderに出そうだと思った。
７問目
整数２次多項式P,Q,Rに対して、P(1)=P(2)=Q(3)=0かつすべての係数の最大公約数は１であるようなとき、R(x)(^2=P(x)^2+Q(x)^2)を列挙する問題。
x^4の項や定数項に注目してみるが、何も得られない。
虚無：２３分
未確認
P(x)^2=(R(x)+Q(x))-(R(x)-Q(x))と変形すると良いらしい。
８問目
内心の問題。
内心外心の問題は普通の模試の問題すら解けないため、何もできない。
虚無：４分
未確認
９問目
4×4のグリッドを4色で配色して、すべての行・列について色が{1,1,1,1}か{4,0,0,0}か{2,2,0,0}になるようなものを数え上げる問題。
KmCodeが「９問目は競プロ！」と言っていたので考えた。
{4,0,0,0}がある場合は簡単に数えられる。
すべて{1,1,1,1}である場合は気合で数えた。
{2,2,0,0}の個数で場合分けしようとするが、綺麗に分かれなかった。
数オリ特有のテクニックでもあるのではと思って諦める。
虚無：１８分
確認済み
色を{0,1,2,3}としたとき、各行、列でxorがゼロになっていることが必要十分で、これはちょうど左上の 3×3のマスを自由に当てはめ、それ以外を自動的に埋めることで対応できる。言葉で表されている制約・条件を結合律・交換律のある演算で表現すると良いらしい。
JOI Open Contest 2019-1問目 三段跳び
問題概要
1以上10^9以下の長さNの数列Hがある。
Qつのクエリに答える。
L<=a<b<c<=R && (b-a)<=(c-b) なるindexの組(a,b,c)に対してH[a]+H[b]+H[c]の和の最大値を求めよ。
N,Q=5*10^5
小課題１
N,Q=100であるため、愚直O(QN^3)
小課題２
N=5000である。解法はいくつか考えられるが、例えば、aとcの組すべてに対してH[a]+H[b]+H[c]の和の最大値を前処理で求めておけば良い。O(N^2+Q)
小課題３
Q=1である。解法がいくつか考えられるが、満点に繋がらないものを述べる。
a,b,cのいずれかが大きい方からlog2_N番目以内のものである。よってaやbやcを決め打って他の二ペアの値の和の最大値を求めることができ、O(QNlogN)
小課題４
aとbのペアが限定できる。具体的には、min(H[a],H[b])>max(H[a+1~b-1])となるようなものに限定される。H[a],H[b]の値は大きい方が良く、またaとbは近い方が良い（他のものを内包するなら不要）ことに由来する。このようなペアは高々2Nつであり、setなどで適当に求められる。b=2b-aとし、a<b<cの制約のみを残すと考えやすくなる。
[a,b)の区間Nつとc｜a<b<cを処理する問題となった。いまcに対する制約がindexオーダーの不等号ひとつで非常に自由な状態であることから、indexのオーダーで走査することを考える。
クエリの区間[L,R)が更新の区間[a,b)を内包する形であり、bはオーダーに関係のない値であるから、右から左に境界を移動させ、区間の左端（Lやa）で処理を行うべきである。具体的に、x[i]を変数、y[i]をH[i]の値として、クエリの区間ではx[i]+y[i]の最大値を求め、更新の区間ではx[i]の最大化処理を行えば良い。それぞれのバケットにはx[i]+y[i]の最大値を持ち、区間更新はその値をx[i]+(バケット内のy[i]の最大値）で最大化することで実現できる。バケットが結合律を持ち遅延評価がO(1)でできるため、Segtreeを使うことができ、計算量はO((N+Q)logN)
区間の内包外包関係についての深い理解が問われる問題。
JOI open2019
32+100+0=132pt 19位
一問目を解きたかったが行き詰まった。一順序に複雑なものが乗っかっているタイプの問題をよく理解していないので、それを勉強する。
くだらない部分点はやる気が皆無なので取らなかった。
本番のフロー
すべての問題を読む。
参加表明のために一問目の5点を取る。
他の小課題１は実装が重いので逃げる。
1:00くらい-5pt(+5)
一問目が楽しそうなので、考える。
O(N^2)解がいくつか分かるが、満点に繋がらないので実装しなかった。
小課題３(Q=1,L=1,R=N)が満点に繋がりそうなので考える。
ずっと観察をしていると、大きい方からlogN+α個のものがすべて選ばれないことがないことがわかるので、実装する。
3:02-32pt(+27)
満点解法を考えるが、適当な当てずっぽうしかできないので解けない。
4:12-32pt(+0)
一問目を諦めて二問目を考える。
これはJOIではない。
気合いを出すと解ける。
4:55-132pt(+100)
一問目のO(N^2)を書こうとするが間に合わない。
5:00-132pt(+0)
反省
一順序に複雑なものが乗っかっているタイプの問題に対する知見を深める（分割統治とバケット、区間を端でソートして走査するやつなど）。結果を求めなければいけないときはくだらない実装だけ重い部分点も取る意志をもつ。
2019年春合宿
忘れそうだったのでかく
day0
りんごのマスコットが人気だった
day1
100+29+29=158pt
それはそうという感じ
木のやつは経験量という感じ
Naanは新規の考え方
暫定5位タイ
上は双子とKmCodeとQCFium
day2
35+15+22=72pt
自明を全部取りましたねという感じ
セグ木の奴が解けなかったのは考察法がひどかったため
2Dグリッドのやつはまだ分からない
最短経路のやつは素直になりましょうという感じ
暫定8位(unique)
day3
13+100+0=113pt
素直さが足りないのでLampsに4時間+n分かけた
素直になりましょう
暫定7位(unique)
day4
24+48+31=103pt
代表のボーダーまで90くらいあって、代表になる気だったのでMonotoneMinimaを考えていたら終了した
7位(unique)
day5
パズルをした
本選233でお情けで通ったので、去年に引き続きNULLをゲットした
day6
PCKの相方がautumn_eelになった
やったぜ
反省
未熟なところ
11年春合宿4日目Virtual
3/18(月) 14:00~19:00でやるつもりだった
虚無の練習がした訳ではないので90分くらい早く諦めた
30+100+100+100=330pt
難易度は11-9-6-9らしい
普通のことをできたという感じ
本番のフロー
ギリギリまで春合宿のためのお勉強をする
0:00-0pt
１問目（リンゴの出荷）を見る
４ヶ月前のJOI予選対策のコンテストで自分が作った５問目にとても似ていた
おどろく
配点が30,100だが、30は自明ではなく、簡単に取らせる気はないらしい
少し考えるとRMQxRAQをすると良いことがわかるので、実装する
1:16-30pt(+30)
２問目（本棚）を見る
とても簡単に見えたので嘘解法を提出すると、嘘解法なのでWAになる
少し考えるとRMQをするだけなので、かく
1:40-130pt(+100)
３問目（IOI）を見る
二分探索をするだけ、境界の処理には注意が必要
1:56-230pt(+100)
４問目（オリエンテーリング）を見る
DAGなので、DAGの本質について考察するが、そんな必要は無かった
AGC002-F LeftmostBall をすると解ける
実装に時間がかかる
3:10-330pt(+100)
１問目（リンゴの出荷）を考える
考えると、"ノードを遅延評価的に伸ばすセグ木"をやると良いことがわかる
書いたことが無くて闇確定だし、やる気が無いので諦める
3:15-330pt(+0)
反省
本番ではやる気がでるといいな
17年春合宿4日目Virtual
3/13(水)12:30~17:30でやった
27+30+15=72pt
日程内5位
参加者のレベルと難易度が高い年だし妥当な結果っぽい
本番のフロー
0:00-0pt
問題１（誘拐２）を見る
２ファクタのグラフを圧縮するタイプの問題
問題を理解するのに時間がかかり、その上考察上の飛躍をして解釈してしまった
23点の部分点を取るつもりだったが、正しく実装すると満点が取れる解法を思いついてしまっていて、当然実装が重いので飛ばすことにする
1:25-0pt(+0)
問題２（都市）を見る
木の順序関係を数値から復元する問題
セグ木の気持ちになると区間の内包外包関係で表すと良さそうなことがわかるので、それを実装する
1:55-22pt(+22)
桁数を一桁だけ減らすと8点がもらえるらしいので、もらう
まともな考察をせずに雰囲気でやったので、時間をロスする
2:15-30pt(+8)
問題３（ドラゴン２）を見る
部分点１の15点を取る
オーバーフロー対策のベクトルの式変形に時間がかかる
3:00-45pt(+15)
問題１（誘拐２）を考える
頭を冷やしてもう一度問題を見ると、自分が飛躍をしていたことがわかる
飛躍を解くと実装が楽な問題になり、それを実装する
3:55-72pt(+27)
問題１（誘拐２）を考える
この問題は最初に考えていた解法で通るが、計算量解析が非自明なタイプの問題で、通ることに気づかなかった
貪欲などを考えていたら人生が終了した
反省
・良い問題の表現だったとしても実装が楽とは限らない。部分点を取るためには言葉の通りの表現が使いやすいことがある。
・限定表現があったらそれを使ってより良い上界があることを疑う
