2018/7 solved(1)
7/1
JAG 国内模擬 に参加
6完だった。Gも考察はできてて、サンプルも合ったんだけど、間に合わせられず...国内予選のリハーサルをできて動きを確認した(両面印刷はやめよう)。
ARC 100 に参加
久々に参加した。もっと時間作って参加したいんだけど、どうしても土日の9時はなかなか難しい...。Eが解けてから、CDに時間かかりすぎ。
7/2
7/3
7/4
左上から順に、そのマスに文字を置くか置かないかをきめていくdpをする。そのときに持つべき状態は、(今いるマス, 手前1行分の状態(置いたか置いてないか))があれば十分である。置いたか置いてないかさえわかれば、並べる順番が決まっているのでどこにどの文字が来ているかがわかり、今置こうとしている文字も何行目の何文字目なのかが分かるから、置いたときに得られる点数が計算できる。行が切り替わる瞬間に、文字をちゃんと使い切っていないと遷移してはいけないことに注意(submission)。
7/5
左右と上下を独立にしていいとこまでは分かるけど、そこから条件を満たしつつ動く組み合わせを計算するのが難しい。折り返して考えるというのは賢いと思った(submission)。
z軸方向に対してスキャンしていくときに、連結成分の個数が変わる可能性のあるイベントは、ある球が現れる/消える、球と球がくっつく/離れるのイベントのみである。このイベントの種類はであり、これを順番に処理しながらその都度連結成分の個数を数える。ここは単純なBFSで実装したので、である。よって、全体としてはになっている。また、球が現れ始める瞬間に既に他の球と交わるような場合もある(例えば、内包している時)ので、イベントを1つずつ処理するのはなく、かなり近い座標で起こっているイベントは一度に処理する必要がある(submission)。
削除ができるってことは相手の操作を打ち消せるな、と思うと3ターン目以降って無駄なのでは?と思うと、深さ2までの全操作を試せば良いことになる。構文解析パートは、エラーにも対処しないといけないので結構めんどいけどがんばる。あと、0が有効にならないことを考慮し忘れていてバグらせまくった(こういうのはなくそう)(submission)。
7/6
7/7
構築ゲー。とりあえず、0101か1010を使わなきゃいけない数が多い方から先頭に、x+1個だけ並べておき、残ったものを切り替わりの数が変わらないように同じ数の隣に置いていく(submission)。
区間を全探索。累積和で高速化しておく(submission)。
倍数の関係になっているので、コインは額が大きい方から貪欲に使っていって構わない。コインは種類しかないので、全体はで処理できる(submission)。
7/8
基本的な方針としては、まず直径dになる分を作ってしまう → 端以外の頂点から次数と深さを守りつつ頂点を生やしていく ということだが、木を生やしていくので(親方向の頂点番号, つなげていい次数, 残されている深さ)をqueueに突っ込みながら新しい頂点を生やしていくと実装が楽。ただ、いろいろなコーナーに注意(d=1だとk=1でもいいけど、d>=2だとk>=2じゃないといけないとか、そもそも直径dを作るための頂点数nが少なすぎるとか)(submission)。
とりあえず、どの区間を略語にするかを全探索することにする(通り)。そして、dp[n][3] = 単語i以降に注目、省略をj回使用したときの長さのmin
を計算することにすると、遷移は2通りなので全体はになる。遷移の省略する方を考えるときに、かかってしまわないようにdpをする前にiをスタート地点にする今省略として注目する長さのハッシュをmapなりでとっておくと良い(submission)。
Codeforces Round #490 (Div. 3) Virtual
国内予選終わって若干燃え尽き気味だったけどとりあえず簡単目な問題でも継続しようと思ってやった。発想自体はそこまで難しいものがあるわけじゃないけど、実装はそんなに簡単なわけじゃないしいい練習になった。
7/9
7/10
dfsして全パターンを試して、条件を満たしているかをチェック(submission)。
小さい方から貪欲にM個取っていくが、a[i]とa[i+1]の間を高速に処理するようにする必要がある(submission)。
Codeforces Round #495 (Div. 2) Virtual
Dで時間を溶かした(思い思いの枝刈りをしたら通った...)。Eも思いついてたけど、重心をみつけて、そこから使う頂点を見つけて、それがパスになってるかをチェックして...を実装してたら間に合わなかった。
最大値の最小化を見た瞬間に二分探索を考えた。まず、k=1のときを考えると、このときに選ぶべき点は重心だなあと思ったので、重心からパスを伸ばしていくことを考えることにした。重心(最も遠い点までの距離が最小になる頂点)は、全方位木dpで求めることができる。この位置をスタートにして、二分探索をすると、必ず含めなければ行けない頂点が決まるので、あとはそれがパスになっているかをチェックすれば良い(submission)。
7/11
連続する1の区間で、一番長いやつを見つける。
幹線道路のペアを全探索する。
7/12
下限を全探索する。このときの下限の候補は通りを考えれば良い。固定した下限に対して、各区間がこれよりも大きくなるように選んだときに、最大値が最小になるような切り方をdpでで求めることができる。あとは、答えを逐次更新していけば良い(submission)。
一本道になるような進み方以外が最適になることはなさそうなので、一本道を作っていくことを考えると、今いる場所とそこまでの最短距離をペアにして、その一本道を作るために木をどかしきる最小コストをBFSで求められる(submission)。
7/13
Codeforces Round #496 (Div. 3) Virtual
Div.3なのに全完できなかった...
中央値が以上になる区間がいくつあるかを求める関数をとすると、答えはで求められる。この"""以上"""がミソで、このように考えることで二値化して考えることができ、E1と同じような考え方を適用できる(submission)。
7/14
7/15
求めたい答えが以下であるかどうかをチェックする二分探索をすることにすると、数列の値を以下かどうかで二値化でき、BITなどを使ってその区間に以下の個数が個以上あるかどうかがチェックできればいいことになり、高速に数えることができる(submission)。
2017 Ho Chi Minh City Regional Contest Virtual
7/16
答えを二分探索することにすると、決め打ちした値に対して、dp[i] = i番目のワードを区間の左端にすることができるかというdpを、尺取りっぽく更新していくことができるようになる。左端は、限界のライン(ワードと必要最低限のスペースで一行に収まるか)、右端は必要最低限ライン(ワードと目一杯のスペースで一行を超える事ができるか)、という2つの値を持ちながら尺取りして、dpを更新していけば良い(submission)。
ACM-ICPC 2018 国内予選 に参加しました
今年もICPCに参加しました(3回目)。今回が自分にとって最後のICPCです。前回までの2回は同じメンバーでしたが、1人が年齢制限で引退してしまったので、今回はメンバーをガラリと変えての参加です。WAsedACというチーム名で参加しました。
結果は全体16位、学内1位で通過できそうです。
本番中の流れ
序盤は、
- 自分が印刷しながらテンプレを打って、Aを読む、A書く、通す
- その間にBとCを2人に読んでもらって、行けそうな方から書いてもらう
っていうのを大まかに決めて動いていた。ただ、BでWAが出たりCでちょっと考察に詰まったりで焦りがあった(模擬はうまくいきすぎた)。
Dは、とりあえず自分が問題を読んで、よく分からないけど半分全列挙したいな〜ってチームメンバーに話してたら自分で喋ってる間に解決した(迷惑)ので、Cが終わったら書き始めて、その間に2人にはE以降を読んでもらう。
Dが程なく通って、EFGどれいくか、みたいな感じになる。
FとかGが見た目的には良いけど、順位表的に、この時点でE4チーム、それ以外0みたいな感じだったのでE読みたくなさすぎるけど頑張って読むことにする。
ただ、頑張って読んで、整理するとそこまで発想が難しい問題ではなかったので、実装してもらうことにして、アイデアを出したのが自分なので自分は隣で見守ることにした。
実装自体は30分くらいでやってくれて、ただサンプルが合わないので3人でデバッグ大会を始める(この辺で5完を確実にとりに行くことにした)。
間に合って良かった(完)(終了1分前)
感想
チームの反省からすると、
序盤焦りすぎた : BとかCとかを担当した人は焦ったと思います。ただ、順位表を見返すと、結果的にDまでのスピードは遅すぎるわけでもなかったような気がするので、本番中はナーバスになりすぎたかなと思います(本番中「おちついてくれ〜〜」って何回も言った気がする)。
Eはやっぱり自分が実装すべきだった : その辺の、誰がどういう問題の実装をやるか、とかどの問題を考えてもらうか、とかは練習が足りなかったから適材適所まではいかなかったかもしれません(国内を通過するためなら1問ずつ皆で頑張るでも良いかもしれませんが)。
ただ正解数を伸ばしたかったら、やっぱり最低でも2問くらいは並行すべきなのかなという気がします(そうしないとどうしてもPCが空く時間が発生する)。この辺りのどう動くかは、やはりチーム依存だと思うので、模索する必要がありそうです。
国内予選終了後には、参加した人々が集まって🍣と🍕で打ち上げをしました。今年は自分の所属する大学からは9チームも参加していたので、打ち上げにもたくさん人がいてビビりました。その多くが学部生で、これからも続いていくといいなと思っています。それも、今年も大学から複数チームがおそらくアジアに行けると思いますが、そのうち今年でICPCを引退する人が結構いるためです。他の大学みたいにサークルがあるわけではないのですが、この流れが続くようにしたいですね。
お疲れ様でした!