かっつのメモ帳

主に競プロ　時々日記

2021.03.22–28

日記 コードゴルフ

3月終わるってマジ？

3/22

去年のTCOのTシャツが届いた。

今日は先週のupsolveを消化していきたい。

SRM489

  • Easy
  • Med
    • 実験のDPを書くとすぐ分かる。

Hard を開けて就寝。$r$ の大きい順にソートして区間を分割するようなことを考えていたが、解法にはまだ至っていない。

3/23

SRM490

  • Easy
    • 互いに素な場合が解ければ良くて、これは簡単。
  • Med
    • DAGを作ってDP。
    • グラフにするパートが虚無。

今日の Hard は手が出せそうな見た目だったので粘ってみる。→解けた。

色々注意すべき点は存在するが、基本的な方針は下記ツイートのダブリング。

(このアカウント気分によって非公開になってるかも、その時はフォロリク送って下さい。)

夜はmugenさんに誘われて駅前にラーメンを食べに行った。久々に人と競プロの話をするのは楽しい。

帰り際、本来だったらもう次のICPC国内予選まで3ヶ月ぐらいなんだよな〜〜という話になり、AOJ-ICPC埋めるぞ〜！！と誓って解散した。

ということで今日はAOJ-ICPC450点を2問解いて就寝。

3/24

SRM491

  • Easy
    • 覚えてない。難しくはなかったはず。
  • Med
    • 面白かった。
    • 2つの集合をマージさせた時の最適コストは、(2つの集合のコスト和)-(集合全体で一致してる文字数)のようになるので、部分集合を $O(3^{N})$ で列挙するDPで遷移させることができる。

現在ブラックボックスで使用している最小費用流の気持ちを理解したくなって、フローの資料を眺めたり、ACLの実装を眺めたりしていた。

バチャ　Codeforces Round #546 (Div. 2)

遅刻全完。D問題、よく見る考察ではあるんだけど計算量が2乗に見えて実は抑えられてる(判定時にループを抜け出せない回数を考えるとこれは高々 $ M $ 回)というのが面白い。

この日は体調が優れなかったので早めに寝ることにした(3時)

3/25

仙台育英の試合を見届けてSRMバチャ。

SRM492

  • Easy
    • システス落ち。高さ条件の考慮漏れでした。
  • Med
    • 難しめだけど面白かった、オススメ。
    • これまで通ったルートを保持しようとするのは難しくて、ある起点 $x$ を通過して区間 $[l,r]$ を調査した後タイムリープで $x$ に戻るを繰り返す問題だと思うと見通しが良くなるはず。

先週出たtopcoderの謎インドコンの決勝の招待メールが届いていたのだが、CC になっていて、加えてコンテストの順位順にメールアドレスを晒し上げていて面白い。

1時間ほどで全完。満足とまでは行かないけど、そこそこの出来だったかな。

就寝(6時半)　明日は何らかの成果を出したい気持ちがある。

3/26

SRM493

  • Easy
    • 一回で動かせる場所は1個飛ばしの区間になるのを利用すると $O(1)$ で解ける。
  • Med
    • 答えは高々 $K$ で抑えられる。
    • 直近 $K$ 文字を持った枝刈り探索でAC。

コドフォブログで昨日のインドコンについて質問を投げたら、やはりインドの学生しか参加出来ないらしい。メアドだけ無意味に晒された上に、参加できないコンテストの為に学生証の写真を送るところだった、危ない。

プロ野球開幕。ヤクルトスワローズが弱くて悲しい。

FA狙うぞと初手C問題開いた結果、solvedが一番少ない問題を引いてしまい撃沈…。

3問目まではやるだけ。4問目のインタラクティブは2つ目の部分点までしか分からなかったが、区間を3分割して再帰的にやればクエリ回数落ちるのそれはそうで面白いと思った。

5問目はGCJかクリスマスコンでしか見かけないだろう問題設定で新鮮だった。部分点は正解数が最も多い人を選び続けるでOKらしい。満点は問題を難易度順にソートして、簡単な問題と難しい問題を1000問程度ずつ抽出して頑張ろうとしたが失敗した。kmjpさんの解法は、生徒を予め正答率順にソートしておき、その上で先程抽出した問題群の正答率をその周囲と比較すれば良いというもので、なるほどとなった。成績順にソートしているので、周囲との正答率の差が大きい生徒ほどズルをしている可能性が高くなる。

3/27

いつものICPCチーム+ツバサさん+suzuken君の5人でチームを組むことになり、通話を繋ぎながら参加。

___KING___ リスペクトで(？)チーム内で同じ問題のAC速度を競い合ったりして楽しかった。

J問題の考察・実装を担当したsuzuken君が凄い。考察を聞いて後追いで書き始めた僕は、まず実装スピードで敗北し、いざ提出すると41ケース中30ケースWAの結果が返ってきて流石に笑顔になってしまった。hotman君が終盤F問題の解法を出して、これもツバサさんとhotman君でAC速度勝負を始めていたが、hotman君が先にAC。遅れて出したツバサさんがWAで苦しんでいて親近感が湧きました(最悪)。

僕自身としてはチームメイトが詰まっていたG問題が通せたので良かった。始め $i<j$ となる $i,j$ を選んで $-1$ 倍するようなことを考えていたのだが、indexに順序付けをつけると正負が丁度半々ずつにするのと相性が悪いなと感じ、少し模索すると2冪で上手く行きそう。これは実装も軽いのでパパッと書いてAC。多分大丈夫だろうと思いつつ不安だったのでチームメイトに黙って投げて、ACを確認してから事後報告をした(最悪2)。

チームとして上手くハマった手応えがあって大満足、UTPC運営の皆様楽しいコンテストをありがとうございました。

upsolve をした中ではI問題が面白かった。

まず前提として最小全域木を取って考えてよくて、全域木を構成する辺が通行不能になった時、初めて非連結になる頂点間を結ぶ辺を消していく問題だと言い換えることができる。木の辺の削除クエリと同連結成分判定クエリに答えられるアルゴリズムがあれば良く、これはDFSだけで実現できる。

1時間ほどで全完。F問題好きです。

一番最初に開いた CODON をACするまで結局2時間かけてしまい、序中盤は冷えまくりだった。状態として、文字列 $ S $ をどこまで揃えたか/最後に訪れた頂点はどこかを持ったDPを最初に書いた。だが本問題では辺を使った順番でパスを区別するのに、これでは使った辺の順序が全く同一で終点が異なるだけのパス同士を区別して数え上げてしまう。重複の解消に苦戦していたが、自己ループが無いことに着目すると、このDPで重複して数え上げられるのは最初から最後まで同一の2頂点間を行き来するパスだけということが分かるので、この処理を加えることでACした。

LUNCHTIM は前から stack に詰めて見ていくことで線形時間で解くことができる。遅れて1完した後も CODON が解けず、仕方なく2番目に解かれていた UNICOLOR を考えることに。問題自体は容易でイベントソート+UnionFind 等で連結成分の管理をすることで解くことができる。

まだ CODON が解けない。GAMEPROF の40点までは解けていて後回しにしようかと思ったが、解けてるものを放置するのもなと思い立ち愚直2乗解で40点。

ここでようやく CODON が通り340点。残り時間的に GAMEPROF の満点を狙うより、PRIMECYC の部分点70点で410点を目指す方が賢明かもしれないと思い6問目を開く。ガバガバな鳩の巣原理より、$ k=5 $ で構築できるならばその中から3つ選び出して必ず $ k=3 $ を構築できるのでは？(出来ないと直感的に嫌な気持ちに…ry)という予測が立つ。実際この予想は正しかったようだ。

近傍の点を高々7つ取り出して全探索をする実装がギリギリ終わり、提出してみたものの1ケースWAになってしまいコンテスト終了。TLの感想を見るに惜しいところまで行ってそうだったが、時間足りなかった上に未証明なので仕方ない。

$ k=3 $ で構築可能な理由気になるので後で解説を見る。朝6時にセンバツの雨天中止を見てから就寝。

3/28

睡眠不足と不規則な生活習慣が原因か、体調が悪く晩ご飯の時間までダラダラして過ごしていた。今日もヤクルトスワローズは弱い。

A問題は明らか。B問題はソートして左端を固定すれば解ける、が実装がやや大変だった。

C問題も難しかったが、数列の要素の種類数を固定すれば二項係数の式に落とせる。前計算パートの計算量が良く分からなかったが手元で問題無さそうだったので提出するとAC。

D問題考察は簡単。ただこれも状態量がよく分からなかったので、手元で試して問題無さそうなことを確認してから投げた。

E問題は初め一般グラフだと思い込んでいて、こんなん無理だろと検索していた時間が無駄だった。木であることに気がついた後も取り敢えず手を動かそうと直径を求めようとしてたのもタイムロス。冷静になると二分探索+DFSで解ける。ただ終了間際デバックが間に合わず、5分遅刻で通った。悔しい。

メモ


ARC-E の類題であるJOI春合宿の regions - 地域 (Regions) を解いた。

この問題も同様に木DPで解くことが出来るが、こちらの方がより難しいように感じた。JOI難易度10が解けて嬉しい。

競合相手が少なさそうだったので、コードゴルフしてみた。　提出

日記執筆中に最短が更新されていた…。

以下今回学んだゴルフテクニック。

AtCoder でゴルフするなら、#include <bits/stdc++.h> を用いるよりも、#import<atcoder/all> の方が短い。

最初のコードでは一部サボっていたが、基本的には if ではなく三項演算子を使うべき。

例として if(x==hoge)huga; は x-hoge?0:huga; のように書ける。

無向グラフの入力の受け取りを 0-indexed で行いたい場合、このコードは技巧的で上手いな〜〜となった。

for(cin>>N>>M;cin>>m>>c>>r;G[c].push_back({m,r}))G[--m].push_back({--c,r});

後基本的なところとしては、vector<array<int,2>> G[1<<15] や auto [x,y]:G[s] 等の空白を詰められる箇所を見逃していて反省。

グッと睨むとDFSにおいて頂点数の情報が要らないことと、場合分けが一つ外せる箇所を発見し最短コード再奪取 (344 Byte → 336 Byte)

更に変数を1つ減らし、三項演算子の中間項を省略出来る文法を思い出すなどして 336 Byte → 332 Byte。

上の例だと、x-hoge?:huga; と書ける。

時系列が逆転しているが深夜にCFバチャをやった。

A問題は難読。円周を囲う格子点の数を線形オーダーで求められれば良い。

B問題はメモ化再帰で解くことができる。

C問題は線形漸化式に落ちそうな見た目をしてるので BerlekampMassey で犯罪出来そうだな〜と思いつつ持っていないので式変形を頑張るも敗北。

$ (i+1)^{k} $ は $i^{j} (0 \leq j \leq k) $ の和で表せるから行列累乗できると見て確かに……となった。

SSRSさんの組合せ的解釈の解法も面白かった。特にフィボナッチ数と、 $N-1$ 個の球が一列に並んでいて隣接する 2 個の球が共に選ばれないように幾つかの球を取り出す通り数に等しいというのは初めて見て勉強になった。

あーこれ書いてて思い出したけど、初見というのは嘘で、前パスグラフの独立集合の選び方の総数を考えていた時にフィボナッチ数に一致して驚いたのと考えれば同じ話だった。これも綺麗な話題ですよね。

今週を振り返って

割と楽しかった