four-t practice 2019 #8
5 月 19 日にチーム練をしました。北大の別のチーム (ragan) と京大のチーム (Heno_World) が参加してくれました。
コンテスト中の流れ
つたさんが A, 僕が B を読み, えびさんが環境構築をする。
A の方針はすぐ立ったらしくつたさんが A を書く。
B トポソっぽくやればできるのではという気持ちになる。なんで制約がこんなに小さいんだろうという気持ちにもなる。
つたさんが A を通したので B を実装する。
WA
よく考えると落ちるケースが普通に作れる。全探索っぽくやる必要があるのがわかる。 dfs っぽくやればできそうな気持ちになる。
C をつたさんが通す。
E をつたさんが通す。
B がバグる。 つたさんにもコードを見てもらったりしてデバッグをする。 B が通る。
えびさんが D を, つたさんが F を書く。
G は幾何なので読む。頑張ればできそう?みたいな気持ちにはなるが、時間が足りないのでやらないことにする。
やることがなくなったので二人を手伝う。(こういう時に何をすべきなのかよくわからない)
どちらも間に合わず終了。
A, B, C, E の 4 完。
良かったところ
- B で WA が出た後なんでダメなのかすぐ気づけた
- F でつたさんの解法が落ちるケースを作った
- G を捨てる決断をした
反省点
- B で WA を出した
- B の実装に時間をかけすぎた
- B で 1-indexed で実装したら途中で 0-indexed になってて壊れた
- 幾何が解けてない
- G の考察が足りていないのに、解ける気持ちになっていた
four-t practice 2019 #7
5 月 12 日にチーム練をしました。北大の別のチーム(名前はまだ知らない)と一緒にやりました。
コンテスト中の流れ
つたさんが A を読み、僕は B を読み、えびさんは環境構築をするいつもの。
B を読むとえびさんっぽいのでえびさんに渡す。
代わりに C を読みます。 木 DP をすれば良さそうな気持ちになります。 つたさんが A を通し、 B をえびさんが書き始める。 つたさんに問題概要と考えたことを伝えると、解けそうだね、となる。
B が通り、つたさんが C を書く。
つたさんが実装している間にえびさんと D, E を読む。D は中国剰余定理、 E は区間 DP っぽいという話になる。
C は一回 WA が出るが、ハックケースを見つけたりしてデバッグし通す。
D, E をつたさんとえびさんに任せて幾何の F を読む。
つたさんが E を書き、通す。
少し考えると線分と線分の距離を見るだけでは?みたいな気持ちになる。流石に嘘では〜となるけど特にやばそうなケースは見つからないので書く。通る
D もえびさんが通してくれて 2 ペナ、 1 時間 23 分で全完。
良かったところ
- 全完した
- 幾何が一発で通った
反省点
- D は僕が持っている中国剰余定理ライブラリだとほぼ貼るだけだったのに僕がやらなかった
- C を提出する前に間違いに気づけなかった
four-t practice 2019 #6
2019 年 4 月 21 日にチーム練をしました。(Tehran 2017の問題セット)
全体的な流れとか反省とかを書きます。
コンテスト中の流れ
つたさんが前の方から、僕が後ろから問題を見ることになった。えびさんはいつも通り環境構築して真ん中から。
K を読む。よくわからないなぁと思ってるとつたさんが A を書いて通す。
J を読む。よくわからないなぁと思ってるとつたさんが B を書き始める。
B のサンプルがわからんみたいな話になってたけどとりあえず合うようにして提出。
WA
この辺はあまり覚えてないけど、えびさんが E を実装していた気がする。
順位表を見ると、H が解かれているので見る。DP すれば解けそうな気持ちになるが、こういうのはつたさんが書いた方が早そうなのでつたさんに伝える。
H を AC
つたさんが実装している間に B を読む。サンプルはよくわかんないけど、全く同じケースがそれ以前にあるなら "No" にすると良さそうみたいな話をする。
B を直して AC
えびさんが E を書いてる間、J を読む。
よくわからんみたいになってると、C を読んだつたさんから問題概要の説明を受ける。幾何なので僕が C を担当することになる。
少し考えると解けるとわかるのでパソコンが空いたら書きます、みたいな気持ちになる。パソコンが空くまでの間、実装を詰める。
えびさんが E を AC
パソコンが空いたので書く。 これはライブラリがいらないタイプの幾何。ギリギリを考えますみたいなやつ。 壁の厚さの変数名と、直線の方向ベクトルみたいなやつをどちらも d という名前にしていたり、点の数を表す変数と、法線ベクトルみたいなやつの名前をどちらも n にしていたりしてダメじゃーん、ってなる。とりあえず "_" をつけて適当に直す。(変数名をちゃんとしましょう。) それなりに時間がかかったけど書き終わる。サンプルを試すと通るのでとりあえず出す。
WA
つたさんと交代するが、すぐに "_" をつけるべきところでつけてないやつがあることに気づいて直す。
サンプルにあったので投げるが WA
コードを読むと、さっきと同じミスがもう一箇所あることに気づく。 直して提出するも WA
流石に WA 出し過ぎでは、みたいな気持ちになってちゃんと全体を読もうという気持ちになる。
I を考察していたえびさんから相談を受けて一緒に考察する。えびさんが考えていたやつでいけそうだねみたいになる。
バグった時は人に説明するとバグに気づくみたいなやつがあるので、えびさんに C を説明する。結局方針は正しそうと言うことになり、コードも一緒に見ると、明らかに間違っているところを発見。つたさんに PC を代わってもらって訂正、提出。
C を AC
つたさんが D を、えびさんが I を、交代しながら実装。 僕はつたさんに G の概要を聞いて考えたりするがわからない。
TLE になったりしつつ、I をえびさんが AC
つたさんに D を実装してもらいつつ、えびさんと残っている問題の考察をする。
F を読む。これは幾何。つらそう。
Tighten Up! | Aizu Online Judge
これと似ているような気がする?僕はこれが解けていないので F はやらないことにする。
G はすでに少し考えてわからなかったので、J, K を考えることに。 J は少し考察をして、つたさんっぽいとなったので、K を考える。方針が立ったかと思ったけどえびさんが嘘だと見抜いてくれる。
つたさんが D を AC
J をつたさんに伝える。色々話していると、えびさんが実装できそうな気持ちになって、実装を始める。その間、僕とつたさんも J の実装を考える。
えびさんの実装が終わり、色々ケースを投げてみたりする。それらに通るようになったので提出するも WA.
つたさんにも実装をしてもらう。ペアプロみたいなことをした。実装が終わり、提出するも WA. 3人でデバッグするが間に合わない。
コンテスト終了。
結果は A, B, C, D, E, H, I の 7 完。Heno_World に最後抜かされて 2 位。
反省
C で方針があっていたのに簡単な実装ミスで WA を出してしまった。変数名とかをちゃんと考えましょう。
サンプルにあったらすぐ提出する癖をやめるべき。提出する前に一度コードを全て読むとかをすると良さそう。
つたさんに実装を投げすぎたかも? H は僕が書いても良かったかも。
感想
全体的な立ち回りはそんなに悪くはなかった気がする。
G みたいな問題を通せるようになりたい。
次は Heno_World に勝ちたいですね。
他の人たちとチーム練をするのは楽しいのでいろんな人に参加してほしい。
AtCoder黄色になったのでブログを始めました
3 月 30 日にあったエクサウィザーズ 2019 で黄色になりました!!!
黄色になりました!!! pic.twitter.com/7OGCxIRAm8
— TAB (@_____TAB_____) 2019年3月30日
2016 年 7 月 30 日の天下一プログラマーコンテストに出て競技プログラミングを始めてから、黄色になるまで約 2 年半かかりました。青になってから黄色になるのには 1 年以上かかってしまいました。黄色から橙にはもっと早く行きたいですね。(こどふぉで破滅を繰り返していたら青になってしまったので早く紫に戻して、こどふぉも黄色(薄橙?)になっていきたい)
黄色になるまでにやったこと
コンテスト
AtCoder や Codeforces のコンテストに出て問題を解きました。 AtCoder は基本的に毎回コンテストに出たと思います。 こどふぉは時間が遅いがちなのでそんなに出ていないです。
過去問での精進
- AtCoder の過去問 (ABC-D, AGC-B,C あたり 700 点以下ぐらい)
- AOJ-ICPC の 600 以下ぐらいの難易度の問題
- Codeforces (virtual participation をたまにやってました)
基本的には上の三つの問題たちを解いていました。 SRM div1 easy に良い問題があるらしいのでこれからはやっていきたいです。
知識
蟻本を読んだり、人々のブログを読んだりして知識を蓄えました。 北大の競技プログラミングサークルではテーマを決めて勉強会を行ったりするので、そこで色々教えてもらったりもしました。
実際のところ AtCoder はあまり知識が必要な問題は(黄色になるために解けなきゃいけない問題の範囲では)出ないと思うので、蟻本を読めば十分な気もします。
これからやるべき事
他の人と比べて解いた問題が少ないと感じているので、どんどん問題を解いていきたいと思っています。特にデータ構造を使う問題や、難しめの DP などに苦手意識があるので重点的に解いていきたいところです。( JOI とかをやるといいんですかね?)
ライブラリの整備もやるべきですね。