えびちゃんの日記

えびちゃん（競プロ）の日記です。

four-t practice 2019 #05

今日はチーム練をしました．つたさんは前からブログに記録しているんですが，これからはえびちゃんもしようと思ったのですることにします．

2015 ACM/ICPC Asia Regional Shanghai vjudge.net

前日

別に書く必要はないんですが，前日のことを書きます．

GCJ の Round 1A を無事通過したり，ウェーブレット行列や赤黒木のライブラリ整備をしたり，とってもがんばりました． それとは関係ないと思うんですが，手の皮が剥けてしまって痛かったし，今も痛いです．

当日（開始前）

おててがつらくて絆創膏を買って行きました．

あとせっかくなのでかわいい写真を撮りました．

動き方は試行錯誤中な感がありますが，とりあえずえびちゃんは環境構築をする係です．一文字で最新のソースをコンパイルするやつがないとダメな体になっていますね． その間にたぶくんが前から，つたさんが後ろから問題を読んで，えびちゃんも構築が終わったら真ん中あたりを読むのが通例になっています．

当日（開始後）

上に書いた通りに行動します．環境構築が終わったあたりで，他のチームが F を通しているのにつたさんが気づいたので，えびちゃんがそのまま実装して通します．えらいね．

あまり覚えてないんですが，つたさんが K の，たぶくんが A の解法を生やしたっぽくて，気づいたら実装されてて通されていました． L もそれなりに通されているとかで，つたさんが K を実装している間にえびちゃんが読んで考察していました．

L 問題概要：\( (x, y)\) にいるとき，\( (x+z, y)\) または \( (x, y+z)\) へ移動できます．ただし \(z\) は \(x\) と \(y\) の最小公倍数です．\( (e_x, e_y)\) が与えられるので，上記の移動を繰り返して \( (e_x, e_y)\) へ移動できる点の個数を求めてね．\(x\), \(y\) は正整数です．

ある点に移動できる点は一つしかないのでは？ と思って \( (i, j)\) から遷移できる点を \(i\), \(j\) の昇順に書き出したりしました．

\(x\), \(y\) が正整数なので，\(\mathrm{lcm}(x, y) = z \ge x, y\) なので，\( (x, y)\) から \( (x, y+z)\) に遷移したとき，\(x < y+z\) であることがわかります．つまり，逆向きに操作するときは，\(x\) と \(y\) のうち大きい方から適切な数引けばいいなぁとか考えました．

つたさんが K を通した後は一緒に考察していたんですが，つたさんは \(x = gs\), \(y = gt\), \(s\) と \(t\) は互いに素とかおいて計算していてえらいなぁと思いました．当然これをやるべきなんですが，えびちゃんはこれが頭から抜けがちなんですよね．

つたさんと本質のあたりをちゃんと詰めて，えびちゃんが実装して通します．えらい． この時点（1 時間弱）で AFKL の 4 完で，2 位になっていました．すごそう．

順位表を見てどれを解くか決めつつ，読んでいない問題をなくす作業をしました． えびちゃんが B を考えて，他の人は G を考えていました．

B 問題概要：高さ \(K\) の完全二分木があります．根は \(1\) で，\(i\) の左右の子はそれぞれ \(2i\) と \(2i+1\) です．根から葉までのパスをすきに選んで，符号をすきに指定したものの和で，与えられた \(N\) を作ってね．

たとえば，\(K = 3\), \(N = 6\) のとき，\(-1+2+5\) などを構築したいです．

えびちゃんはビット関連の操作がすきなので楽しかったです．

えびちゃんがいろいろがんばって，\(1 \le N \le 2^K\) なら解けることがわかったんですが，全部右の子を正の符号で足したものはもっと大きくなるはずで，それを詰めようとがんばっていました．この時点でその部分までの実装はしていました（ここ伏線）．

その後，つたさんの生やした別の方針の解法を聞いたんですが，つたさんが実装つらそうとか言っているのでえびちゃんが実装しました． たぶくんが G を実装するのと（詰まり次第）交互にやっていました．

えー，G も B も WA でつらかったです．

冷静に考えるとつたさんの方針では \(N \ge 2^K\) のケースに対応できないことがわかったんですが，実は制約を見ると \(1 \le N \le 2^K\) のケースしかないらしいです（は？）． なので \(N = 2^K\) だけ場合分けをして提出するも，WA，えーんえーん． えびちゃんがさっき実装したやつで通るはずなので，それを投げます，AC．うーん，これもったいなすぎる（ごめんなしゃい）．

不可能しか残ってなくないか． 各問題をつまみ食いしながら考察すると潜在意識下で考察が進む*1のを信じてそれをするも，当然不可能なので不可能．

たぶくんの G をデバッグするしかないので，それをします． えびちゃんがソースをにらんだり，つたさんがたぶくんとお話している時間がありました． こういう局面でえびちゃんがあまり話さない側になりがちで，よくないなぁとかちょっと思っています．

ソースをにらむと負数の除算でこわれていそうっぽいところを発見したので伝えたりしました． 無限に場合分けする問題らしくて，いろいろ条件を見直して試していたんですが，結局その負数の部分がやばかったっぽい？ diff はよくわからないので本当かはわからない．

終了 1 分前を切ったあたりで，サンプルに合った（色々試して合う状態に戻ってきた？）ので，提出するしかなさそう． デバッグ出力を消すのをつたさんがやろうとしていたんですが，間に合うか怖かったのでそのまま提出してもらいました． ちゃんと stderr に出力していてえらいね．大えらい．

終了 24 秒前に AC．う〜ん，アツい． これ，デバッグ出力消してから提出したらもっとアツい展開になっていませんでしたか？（欲張り）

ABFGKL の 6 完で 30 位でした．ペナルティが険しいね．

終了後とか感想とか

終了後はスープカレーを食べました．チキンとかチーズとかおいしいですね，大好物です．

つたさんがデバッグのときに emacs の操作で時間を食っていそうだったので，そこを改善するといくらか効率が上がりそうだなぁとえびちゃん的には思ったりしていたんですが，つたさんの勉強時間をそういうことに割くのももったいない気がするなぁとも思ったりします．難しいですね．木こりのジレンマだなぁ．

実装している間に他の二人が概要を話し合っているとき，実装に気を取られて聞き逃したりすると，二回分話してもらったりするのがもったいない時間だなぁとは思うんですが，話すこと自体に意味がありそうなので，遠慮しないでちゃんともっかい話してもらうべきだなぁ．

C 問題は，つよいデータ構造のライブラリを持っていれば書くだけでできる気がするので，他にできそうな問題がなくなったときのために，そういうのを用意しておくのもありだなぁとか思いました．や，1000 行近いライブラリを写経するの，タイピングコンテストですか？ という気持ちになりますね．

とはいえ，死なないために死ぬほど準備をしていくのが戦い*2なので，少しでも必要がありそうなことはしておくべきなんですよね．

来週もチーム練をしてくれるらしいので楽しみです．

追記：

そういえば，えびちゃんも「実はこれ，最悪 O(NQ) の解法が実は通るんでは？」みたいな発言をしたんですよね．どうしようもなくなったらそういうことを躊躇なくできるようになっていきたい（いきたいかなぁ...）．

*1:https://codeforces.com/blog/entry/53457

*2:えびちゃんは BLEACH のネタがすきです．