hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

four-t practice 2019 #07

2019 年 5 月 13 日 (日) に 会津合宿 2014 Day3 を AOJ で解いたのでその時の立ち回りのメモです

メモ

今回は北大の別のチーム (チーム名未定) も参加してました。

開始。前回と同じ戦略で進めていった。まず A を読んで実装したが若干読み間違えていてサンプルが合わなかった (えぇ・・・) 日本語を読んで AC。B はめんどくさそうだけど rsk0315 が一瞬で通していた。

TAB が C を、自分が D を読むも、明らかに役割を逆にしたほうがよさそうなので交換する。それで C を実装するも WA (こいつ戦犯しかしてねえ)。よく考えると遷移がおかしいので直して通す。

しばらく D とかを考えていたけど、ここで E が簡単そうとのことで見てみると区間 DP のにおいがしてくる。こういう実装はわりと好きなので実装したら通った。

F は幾何で、直感で考えると異なる点集合間で最も近い線分対の距離を求めるだけに見えるけどさすがに違いそう・・・と思って TAB と一緒に考えるもやっぱりあってそう。パソコンがあいてるときに TAB 書いてもらい、だしたらとおって草 (えぇ・・・)

D は CRT をやればいいんですが、互いに素でない場合にどうしようねみたいな話をする (実は TAB のライブラリが互いに素でない場合も動いたらしい、コンテスト後に気づいた)。制約が小さいので適当をやってもいけるよと rsk0315 に伝えるとすぐ書いてくれた。これも通って 1 時間半くらいで全完。

反省

今回は序盤に老人 (tsutaj) がノロかっただけで、あとはよかったんじゃないかなあ。3 時間の練習をするつもりが半分くらいで終わってしまったので次回練習するときに 3 時間の感じをつかみたい。

four-t practice 2019 #06

2019 年 4 月 21 日 (日) に 2017 Tehran Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

今回は京大勢や ragan (北大の別のチーム) も参加してました。

開始。今回は rsk0315 が環境構築、自分が序盤の問題を読み、後半を TAB に読んでもらうことに。A はさすがにやるだけなので通す。B は簡単そうだがサンプルを見ると同じ入力で答えが違う、これはなに???適当に投げたら WA だったので TAB に解けそうな問題がないか聞く。

H が比較的簡単らしいので読んでみる。たしかに簡単そう。実装したら通った。ここで B の題意をエスパー (?) してあってそうなやつを投げると通る。うーん・・・

中盤の問題を rsk0315 が読んでいたが、E がいつの間にか通っていた。これ以外にはあまり簡単なものは残っていなさそうなので、まずなにに取り組むべきか相談した。

I は文字列の実装系で、rsk0315 が頑張りたいと言っていて、D は問題文が読みにくいが読めた後はやることがわかったので自分が頑張って、C は幾何なので TAB が頑張っていた。どれも重ためなので時間はかかったものの、この 3 問は最終的に全部通った。よかったよかった

あとは G, J, K を解きたいねとなっていて、最後に J を頑張るも通らず時間切れ。

G は終了後に heno_world から解法を聞いたが言われてみればなるほどなあって感じだった・・・。考察力不足だなあ。

反省

終わってみれば、多くの問題の実装を担当した気がする? (A, B, D, H) でもどれも序盤に通した問題なので軽いんですよね・・・

振るべき人に問題を振れた感はあって、いい感じに得意分野に割当が出来たのでよかった。

個人的には D の実装がおそすぎて反省ですね・・・。

four-t practice 2019 #05

2019 年 4 月 14 日 (日) に 2015 Shanghai Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。前回に引き続き rsk0315 に環境構築をやってもらう。問題を 3 つに分けて読み進めていくも、簡単な問題を取りこぼすとまずいので順位表も並行してみることに。F が開始直後からかなり通されていたので読む。確かにかなり簡単。環境構築をやっていた rsk0315 にそのまま実装を任せて AC。

TAB が A の実装をしている間に、自分は後ろの方の問題を読んでいた。K と L はできそうな雰囲気がある。TAB とパソコンを交代しながら K を実装していき、1 個余計なペナルティを出しながらも AC (もうしわけない)

L を rsk0315 と一緒に考察する。LCM と言われているので gcd が関係ありそうで、適当に式をいじっていたら解法が生えたので実装を rsk0315 にまかせて、自分は他の問題を読んだ。A と L がほぼ同タイミングで通る。ここまで 1 時間なのでペースはいい。

ここからが問題で、順位表的に B を通したい感じになったので考察するも、全ケースに対応させるのが難しそう。また G も考察するも WA が取れないという状況に。自分も E を考察したけど、クリティカルな考察には至らなかった。

B の解法を聞いていると「なんか制約勘違いしてるのでは?」みたいなことに気づく。もう一度制約を読むとやはり勘違いだったらしく直すと通る。また、G の解法についての議論はわりとしていたのでデバッグをやってみる。-1 とか +1 まわりが面倒だがとりあえずサンプルに合うようになったので出してみる。これがなんと通って終了 24 秒前 AC になった。解いているチーム数が少ない問題だったのでうれしい。

反省

序盤に順位表をこまめに確認するのは必要そう。早解きできるかどうかはペナルティにかなり響くので

最近序盤のスピードはかなり速くなった気がするけど、やはりそれ以降落ち込むので実力を上げるなりチームワークをもっと良くするなりしないとダメそう。結果論として今回はあまり中盤以降の動きが良くなかったので、まだまだ改善できるとは思う。

今回のセット個人的にかなり好きだったので復習したいですね、特に C, D, E とか