four-t practice 2019 #03

2019 年 2 月 24 日 (日) に 2013 Daejeon Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。TAB が A〜D を、rsk0315 が E〜H を、自分が I〜L をざっと読んでいくことに。A はやるだけらしいので書いてもらう。通る。I は見た目がやばそうだったが冷静になると簡単だったので書く。通る。G もすぐわかったらしいので書いてもらう。通る。続けて K, L も通る。開始 1 時間で 5 問解けたのでけっこうよさげ。

J 問題は一回飛ばしていたけど TAB 君と一緒に考察したら実は行けそうみたいな気持ちになる。とりあえず書いて提出したけど TLE した。よく考えたら前計算の部分をテストケースごとにやる必要はなくて、while 文の外でやれば良いので直す。通る。このペナはもったいないね。

続けて F を書くも WA が出る。若干方針に自信がなかったし、方針ミスかも？と思って一旦放置してしまう。

しばらくして、rsk0315 がずっと取り組んでいた H 問題 (文字列) が通った。正答率低い問題を通せるのすごい。

ここで rsk0315 が F のソースコードをにらむと間違いを見つけてくれる (神か？) 直したら AC した。本当に申し訳ありませんでした

TAB がじっくりやっていた E の考察が終了して、実装してくれた。考察の一部をすでに聞いていたので、ペアプロしながら実装を直していくと通る！！これも正答率が低い問題だったので、すごくうれしい。

反省

序盤はほぼ理想的な動きだったと思う。1 時間であれだけ解けたのはとてもよかった。

中盤・終盤に関しても解くべき問題は解いた気がするのでそこまで悪くはなさそう。ただペナルティが多めで、今回は 7 ペナルティを負ってしまった。1 ペナ 20 分 (だっけ？) なので、1 回提出してペナルティを負うよりは 10 分考えてバグを直したほうが良いので、もう少し慎重になるべきかもしれない。

今後は環境構築含めた練習とかもしていきたいねという感じですね。

four-t practice 2019 #02

2019 年 2 月 23 日 (土) に 2017 Beijing Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。前回の反省を踏まえて、自分は後ろの問題から目を通していき、rsk0315 が前から目を通していき、TAB が A に目を通すことにした。A 問題が文字列なので rsk0315 に早速パス、TAB が代わりに前からざっと見る。題意の把握までちゃんとやろうとなるとそれなりに時間がかかる・・・。G が幾何なので TAB に投げつつ、問題をざっと見ていく。見た結果 E, F が簡単そうということになったのでそこからとりかかる。通る。H と J が解けそうだけどすぐにはやりかたがわからない。

前半に実装がやばそうな問題がいくつかあったらしく、それを rsk0315 が考えることに。自分は後ろの方の考察を、TAB は G の考察をやっていた。E, F を通してから次の提出に 2 時間近く要しているが考察したり実装したりがそれなりにあったのでこれは仕方ない気がする。前回の反省を活かして考察中でも画面はちょこちょこ確認するようにした (TAB が実装していた G のデバッグを手伝うなどした)

G が通り、それからしばらくして実装ゲーの D も通る。幾何と実装がちゃんと通ってすごい、チームメイトがつよつよで助かりますね (tsutaj 何もしてなくない？)

H, J は解法自体は思いつくけど時間制限的に厳しそうという感じ。大きいケースは多くないそうなのでこれでもいけるんちゃうか？みたいな感じで J を書いたら通って草 ( でも が通る場合があるぞい)

あと I の解法っぽいものも思いついたので TLE に気をつけながら書いたら通った。

この時点で残り 1 時間。これまた実装ゲーっぽい A 問題を rsk0315 が Python で華麗に通す (すごい) あと H も実はこれで間に合うんちゃうか？みたいな感じで書いたら通って草 ( でも が通る場合があるぞい)

終わってみると 8 完でそこそこ解けた (やばそうな計算量の提出が 2 問通っているので微妙だが)。でも C の Mo っぽい問題できなかったのはアレだし、B も知識が足りなかった。今回のセットは変な問題はなかったしちゃんと復習したいですね・・・。

反省

今回は問題概要を 2 人がかりで両側探索したけど、簡単枠が真ん中に存在したせいで発見が遅れた (おいおい) これどうすればいいんですかね・・・。もうすこし雑な問題概要の把握でもいいのかもしれないけど、誤読したらヤバいし怖いですね。

解ける問題を落としたり後回しにしたりとかは特になかった気がする。これ以上スピードをあげるには単純に実力が必要

誰がどの問題を担当するかも割と理想的に回った気がして、幾何は TAB に・文字列とか実装とかを rsk0315 に投げて自分はよくわからない DP とかそのへんをやるのが定着しつつある。ただ分業するのはいいんだけど一緒に考察する練習とかももっとやりたいなあと思う

four-t practice 2019 #01

2019 年 2 月 10 日 (日) に 2016 Dalian Regional を vjudge で解いたのでその時の立ち回りのメモです

メモ

開始。TAB が A を見て、rsk0315 が B を見て、自分が C を見る。B は正規表現ぽいらしい。自分も見てみてひと目で Shift-or っぽいと思ったがなぜか可能性を捨てる (は？) これ無限回反省すべきで、これのせいでペナルティがひどいことになった。

C は実験すると Girigiri Happy New Year Contest の B と同じ形になることがわかった (というか問題設定含めて全く同じ問題) が、制約がやたら大きいのでどちらにしろ処理できない、放置

順位表を見ると H, I, J がやたら解かれていたので見たら本当に簡単だったので通す (開始 1 時間くらいで通す形になったのでもう少し早い段階で順位表を確認すべき)

D を TAB と rsk0315 が考えていたけど TLE が取れないらしい。自分も考察してみたらもう少し軽そうな別の解法を思いついたのでそっちで書いたら通った、よくよく考えたら数学問で自分が通すのかなり珍しい (この問題でペナルティがかなりついた、提出する際はもっと慎重になるべきなのかもしれないがジャッジが壊れていることもあるのでどうにも難しい)

F を rsk0315 が実装したけど通らないらしい。問題概要を聞いてコーナーになりそうなところをエスパーしながらペアプロすると直る、AC (ペアプロする前に自分が何やってたか思い出せないんだけど、なんか詰まってそうだったら早めにパソコンの方まで行くべきなんですよね、簡単なことのようで難しいんだけど)

A の問題文が不明瞭らしいので全員で読むが不明瞭すぎる。YES, NO の問題なのに YES, NO の条件がよくわからない。とりあえずサンプルに合うように好意的に解釈するとそれっぽいアルゴリズムが生えるので書く、通る (？？)

B に戻ったら約 4 時間前にふと思ったことがやっぱりあってそうなことに気づくので書く 通る もったいなさすぎる・・・

残っているのは C, E, G, K だが C は制約が大きすぎ、E, K は問題不明瞭、G は良問なんだけど解けないという感じに

C は確か黄金比が関係していることだけ覚えていて、しかし自分は黄金比を知らないのでチームメイトに聞く rsk0315 が式を書いてくれる (神か？) 実験をすると黄金比を掛けて切り捨てしたものが関係していそうなことに気づくも、制約が大きいので結局どうするんだろうなあと考えていたらコンテストが終了した いろいろ調べたけど結局 C は多倍長使わないと解けないらしい (えぇ・・・)

反省

B 問題の処理が最悪すぎて実質 250 分くらい余計にペナルティを負った。つらすぎる

あと全体的に立ち回りが良くなくて、例えば H, I, J を通すのが遅かったり通すまでのペナルティが多かったりする。もう少し自分がセット全体を見て、優先順位に関して敏感になるべきな気がした、これはかなり反省です

G が解けなかったのは完全に実力不足で、こういう系統は自分が通せるようにならないとダメなやつなのでちゃんとやる (復習しました)

C の黄金比の話をチームメイトにふったのも終盤の話で、もっと早く言うべきだった 多倍長関係がアレだけど早い段階で対処していれば通ったかもしれないなあ・・・。

まあ結論としては自分の立ち回りがひどかったです、チーム連携難しい。A, D, F のアシストができたところが唯一よかった点かな