10/13-10/19

今週はvirtualはお休み(毎週お休みしそう)。
CFでレートを下げただけの週だった...。

出たコンテスト

KUPC2019 34位
CF#592(Div.2) 372位 2017->2008
CGR#5 2498位(????) 2008->1908
CF#593(Div.2) 335位 1908->1938
ABC143 23位

解いた問題

KUPC2019-D MaxMin Game

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_d
i+1回目に勝ち負けが入れ替わったとする。このとき、i回目までに1以上2i以下のカードが全て手札から出ていることが必要。
よって、入れ替わるタイミングでは最初がどんな手札でも出ているカードの集合は同じなので、勝ち負けが変化しないようないくつかの区間に分割して考えられる。
そのような長さkの区間内で2人にカードを分配する通り数は、「最終的に|A|=|B|となり、常に|A|>=|B|を満たすように、前から集合A,Bに分配していく通り数」となる。これは実は、長さkの括弧列の数と同じである。これはカタラン数として知られており、C(2k,k)-C(2k,k-1)となる。
これを全ての区間について求め、掛け合わせれば答えが求まる。

KUPC2019-F カズマ王国の陥落

https://atcoder.jp/contests/kupc2019/tasks/kupc2019_f
各拠点から、ある1つの街だけに派遣するような最適解が存在することが示せる。
区間を右端でソートし、次のようなDPを考える:
dp(i,j):i番目の区間まで見て、今まで派遣した中で最も右にある街がjのときのダメージの最大値
右端が単調増加しているので、遷移元が狭まることがなく、このDPで最適解を求めることができる。
遷移にO(N)かかるように見えるが、累積maxを取っておくことでO(1)ででき、O(NM)でこの問題が解けた。

Mujin Programming Challenge 2017-B Row to Column

https://atcoder.jp/contests/mujin-pc-2017/tasks/mujin_pc_2017_b
明らかに、全てのマスが黒になるまでに初めてある1行が全て黒になる瞬間がある。これをi行目とし、iを決め打った時の全て黒になるまでの最小操作数を求める。
(i,j)が黒くなっていないとき、(k,i)が黒いようなkが存在するならば、(i,j)は1回で黒くできる。もしこれが存在しないなら、マス目上に1つでも黒いような(l,k)が存在すれば、最初に(l,k)->(k,i)と1回操作しておくことで、1回で(i,j)を黒くすることができる。これを全てのjについて考えれば最小操作数が求まる。
実は、これに「元から全て黒くなっていないような列の数」を足したものが答えとなる。明らかに、i行目を黒くする過程でそのような列数は増えることがない。また、実は減ることもないことが示せるので、これがiを決めた時の最適解となることがわかる。
これを全てのiについて計算するので、適当な前計算をすればO(N^2)で解ける。黒いマスが存在しないときは-1を出力すればよい。

天下一プログラマーコンテスト2016予選B-C 天下一プログラマーコンテスト1999

https://atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_c
本戦の順位によって人を並び替えておく。以下、ハシモトくんの記録上の勝ち負けを考える。
dp(i,j):i番目の人まで順位が一致していて、i番目の人がj回勝ったような確率 というDPを考える。
遷移は、dp(i,j)=sum{dp(i-1,k)}*f(i,j) のようになる。予選順位によってkの下限がjかj+1か決まる。f(i,j)は「i番目の人がj回勝つ確率」であり、これは各iについてO(N^2)で計算できる。dp(i,j)の遷移はO(N)でできるので、全体でO(N^3)で解けた。

ARC067-F Yakiniku Restaurants

https://atcoder.jp/contests/arc067/tasks/arc067_d
訪れる中で番号が最小の焼肉店をL、最大の焼肉店をRとおくと、LからRへ順に移動していくことで、移動距離の最小値を達成できる。よって、L,Rを決めれば、区間[L,R]における焼肉の美味しさの総和を最大化すればよくなる。
各チケットは、区間内で自由に使う場所を決められるので、区間内でもっともBの大きい場所で使えばよい。
Segtreeを使えばO(MlogN)で区間を決めた時の美味しさの総和の最大値がわかるが、全体でO(N^2MlogN)となってしまい間に合わない。
f(L,R):区間[L,R]における焼肉の美味しさの総和の最大値 というテーブルfを計算したい。
焼肉(i,j)が食べられるような区間[L,R]の条件を考える。全ての(i,j)についてこれが求まれば、f(L,R)にB(i,j)を足していくことで全てのf(L,R)が求まる。[L,R]でのチケットjで食べられる焼肉の中でのBの最大値がB(i,j)となればよい。
この条件は、「S<=L<=i,i<=R<=Tを満たす任意の[L,R]」という形になる。S,Tは、setを持ちながらBの小さい方から見ていくことで、各チケットごとにO(NlogN)、全体でO(MNlogN)で求められる。Bが等しいもの同士も、適当に順序付けすることでうまく処理できる。
後は条件を満たす[L,R]について、B(i,j)を足しこめばよい。
二次元平面上で考えると、長方形領域に値を加算していく形になっている。これは二次元imos法でO(NM+N^2)でできる。
これでf(L,R)が求まったので、この問題が解けた。

ABC143-F Distinct Numbers

https://atcoder.jp/contests/abc143/tasks/abc143_f
Ci:「Aj=iなるカードjの個数」とする。
X回操作すると仮定し、これが可能である条件を考える。問題は、次のように言い換えられる。
「X行K列のマス目に、数列Aの中から1つずつ数を書き込んでいく。同じ行に同じ数が入れてはいけない。マス目を全て埋められるか?」
明らかに、Ci>=Xなるiは、iで一列埋めてしまうのが最適。
後は、残っている列をCi=Xなるiの個数)*X+(Ci=X*K」が条件だとわかった。
単調性より、後はXを二分探索すれば答えが求まる。
累積和などで必要な値を適当に前計算しておけば二分探索内の判定はO(1)でできるので、全体でO(NlogN)で解けた。

感想

学校の後のCodeforcesは必ず仮眠を取る!

10/6-10/12

出たコンテスト

🤔

IOI2013 Day 2 Virtual

今までやった5時間セットで一番成績がよかった。
100+100+63=263点、Day1と合わせて430点、銀の真ん中らへんなので適正という感じ。
~0:30くらい 1問目を読むと、30分で76点、定数倍が軽ければ100点が取れる解法がわかってしまう。
76点でも取っておいたほうがいいと思ったので実装する。
0:47 1WAを出したが、1問目が通る。にぶたんの区間に気をつけよう。
~1:20くらい 2問目を読むと、よい性質に気づいて一気に90点、定数倍が軽ければ100点が取れる解法が15分くらいで分かる(定数倍ゲー多い...)。
1:50 書いたコードの定数倍が軽かったらしく、2511ms/3000msで通る。
~2:10くらい 明らかに「動的二次元セグ木を書きなさい」という問題だが、闇な気がしたのでやる気をなくす。とりあえずただの二次元セグ木で取れる63点を取ることにする。
2:22 3問目の63点が通る。動的二次元セグ木を導出しようと頑張る気が起きなかったので撤退。(時間が半分で終わってしまった...)

難易度はたぶん8-9-11みたいな感じ。
1問目 Cave
小課題3までは省略。
ドアを左から見ていき、順に対応するスイッチとその正しい状態を当てることを考える。
制約を見るとlogがつきそうなので、二分探索を考える。
「対応が未決定のスイッチの中の左からX個選んだ集合について、今見ているドアと対応するものがあるか?」という問題が解ければ、Xについて二分探索することで答えが求まる。
実はこれは、「左からX個選んだ集合」のスイッチを反転させ、元の状態での質問の答えと比較することで、1回の質問で知ることができる。
クエリ呼び出しはO(NlogN)回、時間計算量はO(N^2logN)となるので、適当な枝狩りをすれば間に合う。

2問目 Robots
実は、最適解において、「弱い」ロボットが運ぶおもちゃを考えると、「Xi>=Xjならば(iが運ぶ任意のおもちゃのW)>=(jが運ぶ任意のおもちゃのW)」が成立することが示せる。この性質を利用する。
解を二分探索することを考えると、「K分以下で片付けられるか?」という問題を解けばよくなる。
まず、「弱い」ロボットにおもちゃを割り当てる。このときロボットiは、「重さXi未満の残っているおもちゃの中で、大きさの大きい方からK個以下」を取るのが最適となる。ロボットをX、おもちゃをWでソートし、尺取り法とpriority_queueを用いることでO(TlogT)でどのおもちゃが取られるかが分かる。
その後は、「小さい」ロボットに、普通に大きさの小さい順に割り当て、最終的に全てを割り当てられたかを判定すればよい。これもO(TlogT)でできる。
時間の最大値がTであることから、O(T(logT)^2)で解けた。

3問目 Games
GCDはセグ木に乗るので、66点までは普通の二次元セグ木を実装すれば取れる。
80点は二次元動的セグ木、100点はそれのメモリ削減が必要らしい。
動的セグ木は、ポインタベースで「ノードが必要になったら作る」ということをすれば書ける。
これを応用すれば二次元にできる。(実装する気が起きない...)

解いた問題

AGC038-C LCMs

https://atcoder.jp/contests/agc038/tasks/agc038_c
Aiの最大値をVとする。今、S(k)=(gcd(i,j)==kなる(i,j)に対するijの和)とすると、lcm(i,j)=ij/gcd(i,j)より、1<=k<=VにおけるS(k)/kの和が答えとなることが分かる。
T(k)=(i,jがともにkの倍数となるような(i,j)に対するijの和)とする。T(k)=(iがkの倍数となるようなiの和)^2 となるので、調和級数より、O(NlogN)で求められる。
T(k)からS(k)を求めるには、余計に数えている分を引く必要がある。実は、kを上から見ていったとき、S(k)=T(k)-(kより大きいkの倍数lにおけるS(l)の和)となるので、これも調和級数からO(NlogN)で求められ、この問題が解けた。
数えなくていい部分も数えているのでAiの和を引いて1/2をすると答えになる。

ABC140-F Many Slimes

https://atcoder.jp/contests/abc140/tasks/abc140_f
Sを大きい順にソートしておく。明らかに、S1が最初のスライムとなる。
時系列順、同じ中では親の大きさ順にスライムを決めていく。
新たにできるスライムの大きさを考えると、「親のスライムより小さいSの中で最大の大きさ」とするのが最適。
もし最大でないものを取ったとして、その後で使われる最大のものとこれをswapしても損しないからである。
これを愚直に実装し、もし途中で構築できなくなったらNo。

CODE FESTIVAL 2016 qual B-E Lexicographical disorder

https://atcoder.jp/contests/code-festival-2016-qualb/tasks/codefestival_2016_qualB_e
SiがSjより辞書順で大きいとき、
1.SjはSiのprefixである
2.最初から見て、2つが初めて相異なるような場所で、Sjの方がSiより辞書順で前にある
のどちらかである。
Trie上で考える。
1.の場合はTrieで前計算することができる。
2.の場合について考える。
「f(i,j,k):Siと他のある文字列Tとの辞書順が決まる場所において、Siの文字がj、Tの文字がkとなるようなTの個数」というテーブルfを前計算しておく。
これはTrie上で、26*O(sum(|S|))程度の計算回数で求めることができる。
各クエリにおいては「Skiより辞書順で小さい文字列の個数」を求めればよい。1.の場合は明らかで、2.の場合は、新しい辞書順でSiの方が後にくるようなfの値のみを足せばよい。
クエリ回答も26^2*O(Q)程度の計算回数で求まるので、制限時間6secに間に合う。

感想

台風のせいで土曜にまともに競プロできなかった、悲しい

9/29-10/5

この場所を有効活用したいと思ったのでばちゃの結果を書くことにした。代表になれないのにIOIばちゃをする人になった(大学生になったらどうせ解かないし...)。
できる日は5時間ばちゃをやってここに記録するようにしたい。

出たコンテスト

CF#589(Div.2) 3完 2095->2017
AGC039 2完 2027->2043

IOI2013 Day1 virtual

100+12+55=167点。謎問題で点数がだいぶ左右されるのつらそう。

~0:20くらい 1問目、2問目を読む。2問目が謎なので後に回すことにして、1問目はすぐに小課題3まで分かる。
~0:40くらい 1問目の小課題4が分かり、それに連動して満点解法も分かる。自分がこの時間で分かるということは簡単枠だろうと思ったので実装することにする。
1:07 1問目の小課題4だけ通る。なぜか一緒に取ろうとした小課題1が通らない。
1:51 謎だったので満点解法を実装すると、通らない理由がわかる。なぜか65点。
1:54 M=N-1で壊れていることに気づく。100点。
2:41 3問目を読むと、小課題3まで分かったので書くと通る。
2:54 すぐに小課題4もわかったので通す。それ以降はヤバい臭いがするので飛ばす。
3:57 2問目がよくつかめなかったので雰囲気で書いて出す。6点。
4:16 微妙な改善を投げるが12点。そのままコンテスト終了。

1問目 Dreaming

各連結成分について、「そこからの連結成分内への距離の最大値が最小となる頂点」のみ他の連結成分と繋げればよい。これに気づくと、次の3つの問題を解けばよくなる。
・木の中で最も遠い2頂点間の距離を求めよ。
・木の中で、「ある頂点を根にしたときの深さの最大値」の最小値を求めよ。
・頂点ごとにコストviが定まっているN頂点0辺のグラフがある。これにN-1辺を追加して、d(i,j)=vi+vj+(iとjの距離)*L の最大値を最小化せよ。
1つ目と2つ目は、全方位木DPをすることで求まる。
3つ目は、実はviが最大の頂点から他の全頂点へ辺を張るのが最適となる。
これは、viが最大な頂点をmとして、m-t1,t1-t2に辺が張られているとき、m-t1,m-t2 に辺を張り直しても損をしないことからわかる。
これでO(NlogN)で解けた。

2問目 Art Class

画像分類をしてくださいという問題。
無思考で「差の二乗和」とかを求めて特徴量を探そうとしていた。
なにもわからない...

3問目 Wombats

55点までは省略。ここから非自明パート(解説を見た)。
最短路テーブルをセグ木に載せることを考える。具体的には、列iから列jまでを被覆するノードでは、「C(p,q)=(i,p)から(j,q)への最短路の長さ」を任意のp,qについて求めたテーブルCを持つことにする。
「D(i,j)=i行目からj行目への、任意の列の2組の最短路テーブル」を求めたいとする。進行方向の性質から、これはi < k<=jなるkについて、D(i,k-1)とD(k,j)から求めることができる。愚直に計算するとO(C^3)。
k-1側の出る場所を固定すると、実は、k側で入る場所を右に動かすにつれ、「k-1からkへ移動する列」も右に動いていくことがわかる。この性質を使えばO(C^2)で求められる。
k=(i+j)/2とすることでセグ木のマージが同じようにできるので、辺更新1回についてO(C^2logR)でできる。
回答クエリについては、全体を被覆する区間を見るだけでよい。O(1)でできる。
これで解けた...と思ったが、実はサイズR*C^2のテーブルを用意しただけでMLEする。時間には余裕があるのでセグ木を工夫するとできるらしいが、面倒になって実装していない...。

解いた問題

JSC2019決勝-A Equal Weight

https://atcoder.jp/contests/jsc2019-final-open/tasks/jsc2019_final_a
15分くらい。300ではない。
まず、A,Bが相異なるので、条件を満たす組で同じシャリやネタが2回使われることはない。
握りの重さの種類数は高々2*10^6通りであることに注目する。
愚直全探索を考えると、シャリとネタの組を全部試し、重さに被りが出たところで終了、というようになり、これはO(NM)に見える。しかし、2*10^6通りより多い組を試した時点で1つ以上被りが生まれるはずである。そのため、2*10^6+1通りより多い通り数が試されることはなく、間に合う。

CF1228E Another Filling the Grid

https://codeforces.com/contest/1228/problem/E
コンテストが後5分長ければ通っていた...。
1の置き方を決めていくことを考えると、「行の中で最初に1が現れる列」が単調増加すると仮定して、
dp(i,j,k):i行目まで見て、i行目の中で最初に現れるのがj列目で、jがk回連続しているときの通り数
というDPをすると、累積和を使って面倒だがO(N^3)で解ける。コンテスト中はこの方法でやった。
上のDPは1の順序を固定してやったせいで面倒になっているが、冷静に考えると「1が既に入っている列の個数」さえ求まっていればよいことがわかる。
dp(i,j):i行目まで見て、1がj個の列に入っている時の通り数
というDPでO(N^3)で解ける。
また、実はこれは包除原理が使える。「i個の行、j個の列に1が含まれていないことがわかっている時の通り数」を計算し、偶奇に応じて足し引きすればよい。O(N^2)で解ける。「または」のみの式は「かつ」の通り数を足し引きすることで求められる、というのが包除原理。

JSC2019決勝-C Maximize Minimum

https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_c
座標xにあるイチゴについて、min(x,L-x)に置いてあるとして考える。
間に2つ以上イチゴのある2つの距離が答えになることはない。また、L/2に最も近い2つについて、(最も近いものを折り返した時の2つの距離)より距離が長くなることはない。よってこれと「間に1つイチゴがあるような2つの距離の最小値」とのminが答えの下界となる。
これは、「左から偶数番目にあるやつを折り返す」というように決めると達成できる。
L/2に近い2つの方の距離は毎回計算してよい。間に1つイチゴがあるような2つの距離は、この2つの集合が一度の操作で定数個しか変化しないことを用いると求められる。
「今の座標の集合」と「間に1つイチゴがあるような2つの距離の集合」をmultisetで管理すればO(NlogN)で解ける。
実装がとてもつらい。

AGC039-B Graph Partition

https://atcoder.jp/contests/agc039/tasks/agc039_b
V1に入れる頂点を1つ固定し、全頂点への最短距離を計算する。すると、最短距離がdの頂点をV(d+1)に入れるのが最適となる。なぜなら、Vi(i>d+1)に入れると壊れるのは明らかで、Vi(i<=d)に入れたとしても、それが条件を満たすならばV(d+1)に条件を満たしたまま移動できるからである。これは最短距離の性質を考えるとわかる。
このようにして構築したグラフのうち、条件を満たすものがなければ-1、あればd+1の最大値が答えとなる。

感想

相変わらず競技プログラミングをする時間がない。
PGBATTLEで入賞していてうれしかった。

9/22-9/28

ブログっぽいことをしようと思いました。

出たコンテスト

CF#558(Div.1) 2完 2018->2095
PG BATTLE 結果不明
ABC142 6完 1982->2027

解いた問題

手応えのあった問題だけ。

JOI2009春 1-2 Stamps

https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day1_20.pdf
30分くらい。
新しい文字列T="IO"+S+"OI"としても、端の"IO""OI"を変化させることに意味はないので、Tのもとで考える。
Tは I..I とO..O が交互に繰り返される形になっている。これらのブロックをまるまる削除したり追加したりすると、2つまとめて消すことになり、必ず損をすることになる。
これでI..I、O..Oを独立に考えてよくなったので、操作回数が最小かつその中で文字列が最短になるものを考えると、
ブロックの長さLが奇数のとき floor(L/2)回変更する
Lが偶数のとき 1文字削ってfloor(L/2)回変更する
のが最適となる。
これを愚直に実装すればO(|S|)で解ける。

CF1229A Marcin and Training Camp

https://codeforces.com/contest/1229/problem/A
30分くらい。
「a_uで立っているbitがa_vで立ってない、またはa_u=a_v」の場合に(u,v)に有向辺を張ったグラフを考える。
明らかに、入次数=0な頂点は使えない。また、それを消すことによって入次数=0になる頂点は使えない。
これを再帰的に繰り返していき、残った頂点は全て入次数>0であり、これらを全て選ぶのが最適。
bit演算を使えば高速にグラフを構築でき、O(n^2)で解けた。

CF1229B Kamil and Making a Stream

https://codeforces.com/contest/1229/problem/B
コンテスト中はこの解法が間に合うとは全く思ってなかった。解説AC。
ある列Aについて、gcd(A_0),gcd(A_0,A_1),...,gcd(A_0,A_1,...,A_N)の中での種類数がO(logA_0)であるということを使う。これは、順に見ていった時にgcdが減る場面では必ず1/2以下になるということから分かる(gcdで掛けられている素因数が1つ以上減るので)
葉側の頂点vをDFSしながら走査していく。unordered_mapを使って「根からvまでのパスの中の、vを含むgcdの集合」を種類ごとに管理できるので、O(nlog(xmax))で解けた。

CF1229C Konrad and Company Evaluation

https://codeforces.com/contest/1229/problem/C
40分くらい。
稼ぐ額が大きい方から小さい方へ辺を張った有向グラフとして見ると、頂点が更新されたときに、入ってきている頂点を全て出ていくように変更し、差分を計算する、という処理をすればよいとわかる。
実は、これを愚直に実装するだけでACできる。
クエリを√M個のブロックに分割して考える。
・頂点がブロックで初めて更新されたとき 
これで更新される辺数の和が2M(次数の和)以下であることは明らか。
・頂点がブロックで2度目以降に更新されたとき 
各頂点について、1度更新されると入次数は0になり、1つのクエリについて高々1つしか入次数は増えないので、ブロック内のクエリ数から、変更する必要のある辺数は√M回以下。よって合計でM回以下。
これを合わせて、O(Q√M)になる。

ABC142-F Pure

https://atcoder.jp/contests/abc142/tasks/abc142_f
「全頂点が入次数1、出次数1のグラフ」はサイクルの集合となる。このうち1つ構築すればよいので、1つのサイクルになるような誘導部分グラフを求めればよい。
まず、元のグラフにサイクルがなければ明らかに-1である。そうでなければ必ず以下のように構築できる。
サイクルの始点を決め、順に見ていく。後ろから入ってくる辺があれば自分の前にある頂点、「入ってくる元の頂点」の後にある頂点は使わないようにする。後ろへ出ていく辺があればその間にある頂点はグラフに含めないようにする。この結果できるグラフは必ず2頂点以上のサイクルになるので、条件を満たす。

感想

コンテスト以外で1問しか解いていなくてまずい。こういうのを可視化していきたい。

AtCoder黄色になりました

青になってから半年たたずになれるとは思いませんでした。やったね。


黄色になるために自分が役に立ったと思ったことを列挙します。大体は他の人もブログに書いていることだとは思いますが......。

AtCoderのコンテストに出た

unratedと合わせて70回くらいは出た気がします。出た後、解けなかった最初の問題の解法を自力で導出できるようになるまで解説を反芻するのがいいと思います。自分はこれをさぼったので水色で停滞しました。

Codeforcesのコンテストに出た

実は、AtCoderで黄色になる一週間前に、Codeforcesで黄色(薄橙?)になっていました。


Codeforcesは出てない回もかなり多いんですが、CodeforcesAtCoderの参加回数がほぼ同じです。要するにかなり開催頻度が高いです。質は...わかりません(開始延長することはよくあります)。
英語だったのでAtCoder以上に復習を全くやっていなかったんですが、ある回の解けなかった問題の解法に感動して以来するようになりました。

・色々なコンテストに出た

yukicoderTopcoderCSAcademyなどの出れるコンテストには大体出ていました。自分に合ったレベルなら大体学びが得られると思うのでいっぱい出るのはよいと思います(生活習慣崩壊には注意しましょう...)。

AtCoderの過去問を解いた

f:id:TA1SA:20190505122336p:plain
AtCoder Scoresの「精進グラフ」
普段の競技プログラミングの時間の大体をこれに費やした気がします。AtCoder Problems/AtCoder Scoresには感謝しかないです。
実力がついてくると、昔は雲の上の存在だった1000点以上の問題が解けたり解けなかったりして楽しいです。
黄色になるのに一番貢献したと思うのはやっぱりAGC埋め(まだDの半分も埋まっていませんが...)でしょうか。AGCの問題は適当に考察すると大体嘘解法に突っ走ってしまうので、考察の仕方がうまくなった気がします。

・JOI(日本情報オリンピック)の過去問を解いた

f:id:TA1SA:20190505122325p:plain
非公式難易度表の埋まり具合
自分は(この記事を書いている今は)JOI現役勢で、コンテストの中でも一番重要度が高かったのがJOIでした。
JOI非公式難易度表とその埋め具合を管理してくれるAOJ/AtCoder-JOIという便利なものがあるので、青の間はこれを元に難易度9~10を埋めていました。これも黄色になるのにだいぶ貢献したと思います。
難易度9~10は、(全く傾向が違うのでアレですが)AtCoder基準だと700~1000点くらいな感じで結構考察が重いです。そして実装はもっと重いです。難易度11に手を出してみた時は、正しい考察ができても、実装が大変で1日かけてもACできずに諦めた記憶があります。
逆に言えば、それだけ実装力(境界処理とか)の向上には役に立ったと思います。

アルゴリズムとデータ構造の勉強をした

最小全域木問題とか最短経路問題とかはいい例ですが、アルゴリズムやデータ構造の原理や性質を使う問題は多いです。これを理解しようとすると、天才さに驚かされることも多くてなかなか楽しいです。まだ文字列系やフローなどはよく理解できていないのでやらないと......。

Twitterをした

最近は忙しくなってきたので控えようとがんばっています。が、様々な分野の知見を得られたりモチベをもらえたりすることも多いので適度にやるのがよさそうです。

・JOIなどのオンサイトに出た

青になったあたりからいくつかのオンサイトコンテストに行けるようになりました。中でもJOI春合宿は(問題も参加者も)レベルがすごくて、12問中0完だった自分はつらい気持ちになりましたが、モチベーションはだいぶ上がりました。予選にまじめに出ると企業コンも意外と行けたりするので面白いですね。

おわりに

やがて君になる」「宇宙よりも遠い場所」「CLANNAD」あたりは黄色になるのによい影響を与えてくれたと思っています。ありがとうございます。

JOI2019春合宿 参加記

Day ?

直前に2018のVirtualをやったら3完だったので、今年もそのくらいできるかな〜と言っていた。1ヶ月前くらいから難易度10埋めをしていた。


Day 0

双子から誘われたので人々とご飯を食べてから会場に行った。会場に着くと1ヶ月前に体験したような雰囲気が漂っていて、人数が少ないだけあって実家のような安心感を覚えていた。
ラクティスではEmacsのゲームを教えてもらった。テトリス楽しい。
講義は聞いたことのあるSegtreeのテクを分かったような分かってないような気持ちになった。
自己紹介フェーズでのチューター勢が面白すぎた。

HL分解とSCCを書いて寝た(全く使わなかった...)。

Day 1

朝は自然に目が覚めた。朝食に998244353人並んでいて冷えた。
こどふぉったので緊張感0で競技開始。


合宿で最も満点が多かった1問目に全く時間を使わなかったのがダメすぎる。終了20分後に解法が分かってしまった。
O(NQ)が通るという話が面白かった(最近のコンピュータってすごい!)。
講義はグラフアルゴリズムで、こういう研究面白そうだな〜という気持ちになった。
つらくなったので五等分の花嫁を読んで寝た。

Day 2

朝はDay 1と同じ。緊張感0で競技開始。


この日は普通に実力不足という感じ、強いて言えば3問目でもっと取りたかった。
このあたりから精神と体調がおかしくなってくる。
機械学習の講義を受けた。ニューラルネットワークがすごいらしい。

Day 3


9人が通した2問目で0点を取ったのが本当にダメで、O(N^2)のDPにこだわりすぎてしまったことに後悔。
講義はSATについてで、名前しか聞いたことのない概念だったので新鮮だった。
解説が天才すぎて「これが”””競技プログラミング"""...!」という気持ちになった。
この辺で気が楽になったのか精神が回復してくる。
yukicoderに出て寝た。

Day 4


結局全日程0完だったものの、3問目にして合宿で初めて30点以上の点数が取れてとてもうれしくなった。2問目をちゃんと考察するべきだった気もする。
講義は強化学習についてで、PFNがすごいらしい。PFNのクリアファイルをもらった。
夜はAGCに出たが、ABDを考察して1問も解けなくて寝てしまった。結果的にはNo Subになってしまったので最悪。構築セットきらい。

Day 5

午前はわてれさんのパズルコンテストがあって、コードを書くのに疲れていたのでパズルを全部手で解いていた。たのしかった。
表彰式と代表発表会があって、前回のIOIの報告とかが面白かった。合宿で代表のすごさを実感したので本当に代表各位はすごいと思った。
自分の順位は16位で、同校7人の中で最下位だった。まあ実力通りっぽい。


同校の数研も同じところに泊まっているらしいので遊びに行ってABCに出た。24位であたたまったと思ったらミドリムシさんが優勝していてかてません...となった。

Day 6

帰るだけ

まとめ

・周りの人々が強すぎる
・Day 1で冷えると死ぬ
・解説前に風呂に入るとQOLが上がる
・余ったIOIグッズがもらえてうれしかった
・立ち回りを練習しておかないと激冷えする
・長いので色々な人と話せて楽しかった
・来年はがんばります

JOI2018/2019本選 参加記

あったことを羅列します。

1日目

10時くらいに起きてTwitterを見つつ適当に出る。
北千住でTMJNと会ったので毒蛇の脱走の考察をするが、なにもわからなくなりやめる。TMJNが天才っぽいことをしていて天才。
会場に着くと同校が大量にいたので固まる。パズルに自分のIDが使われていて笑っていた。

ラクティスは最初ログインできなくて焦ったものの普通に全完。
マインスイーパをして(最後の1つで死んだ)、双子などのところに行くとTwitterで知ってる人々がいたので話す。E869120の予想がこわかった。

講義があったが、難しかったので割り算はにぶたんすればできるなーとかどうでもいいことを考えていた。
夕食は貪欲法を使った。自己紹介フェーズで嘘解法で通さないことを宣言する。

バスで宿に向かって部屋に入るとすぐみんぷろが始まったので出る。
Cまでは普通で、Dが一生解けなくて冷えたのでFに行ったら15分で解けて「は????」って言ってた。
黄ぱふぉ1816->1869であたたまる。

絶起が不安で寝付けないとかいう状態になっていたが、気がついたら意識がなかった(起きたら周りに人が血だらけで倒れていたわけではない)。

2日目

6:45に目覚ましをかけたのに6:00に起きてしまう。二度寝しようとしたが不安になったので起床。
朝食は適当に食べてFAした気がする。
バスで会場に移動した後、色々な部屋を経由して会場に入る。

開始まで30分くらいあったので「1300問解いたし落ちるわけが無くないか?」とか思いながら虚空を見つめていた。

1問目は無限回見たやつなので8分くらいで解ける。

2問目は一瞬で分かったように見えて嘘で、頭を入れ替えて考えると降順に見ればいいことが分かるので解ける。この時点で20分。

3問目は問題名からしてセグ木かな?となる。
これは嘘で、制約を睨むとO(N^3)のDPが生えるので書く。部分点はよく分からなかった。
自信満々で出すと何故かTLEしていて(75点)、制限が500msなので定数倍がダメだと思って色々する。TLE。
焦ってコードとにらめっこしていると、DPの中でにぶたんをしていたのがボトルネックだと分かる。
前計算に変えてAC。この時点で80分くらい。

4問目は見た目的に苦手そうだなぁとなるが、とりあえず自明な8点を取って次へ。

5問目も4点は自明なので取れるが、それ以降が全くわからないので4に戻る。
xの小さい方から決めていけるなーと思うとDPが生えて、これで29点が取れる。
この時点で残り110分、341点だったので通ったかな?となる。

この後は1点も取れなかった。最後の30分は完全に諦めて虚空を見つめていたので落ちたかなーとか思っていた。
終わったので人のところに行くと、341点が大量らしく驚く。
2が虐殺問だったらしく背筋が冷える。下手したらハマって焦って死んでた気がしていたので。

E869120の乗っ取られたツイートにふぁぼりつつ昼食を食べる。
解説を聞くが、5が初っ端から理解できなくて頭の悪さを痛感した。
解散後はカラオケに行って帰宅。

結果

春通りました。

感想

コミュニケーションが下手すぎる 失礼なことをしていたらごめんなさい