AtCoder ABC311 - G - One More Grid Task

たまには解説を書いてみます。

概要

\mathrm{O}(nm^2) 解の解説をします。

yfuka86 さんが書いた解説1の、帰着後の問題の解き方を解説します。

帰着後の問題

長さ m の整数列 B, C が与えられる。 l, r \,(1 \leq l \leq r \leq n) を適切に選ぶことによって、 ( \sum_{l\leq i \leq r}B_i )(\min_{l\leq i \leq r}C_i) として達成可能な最大値を求めよ。

入力例2を使って考えていきます。

4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4

l_y = 2, r_y = 3 の場合を考えてみます。

この時、 B = (5,8,17,5), C = (1,2,8,2) です。

高さが C_i で、横幅が B_i の長方形を並べてみます。

( \sum_{l\leq i \leq r}B_i )(\min_{l\leq i \leq r}C_i) はこの図形に含まれる長方形の面積に対応します。例えば、赤色の長方形は l = 2, r = 4 の場合に対応し、青色の長方形は l = 1, r = 3 の場合に対応しています。

従って、帰着後の問題の答えはこの図形に含まれる長方形の面積の最大値に等しいです。これはヒストグラム中の最大長方形を求める問題として知られており、スタックを使うか、Cartesian Tree2 を使うことで、 \mathrm{O}(n) で解くことができます。

ヒストグラム内の最大長方形 | アルゴ式3

  1. https://atcoder.jp/contests/abc311/editorial/6833↩
  2. Library Checker↩
  3. この解説では、lower_left や lower_right を求めるのにスタックを使っていますが、Cartesian Tree を使って求めることもできます↩

2020 年振り返り

競技プログラミング

コンテスト成績

  • Google Code Jam 2020 Round3 進出 & T シャツゲット

  • ICPC2020 国内予選突破 (18位)

  • AGC048 23 位

Rating

AtCoder

Rating 2011 → 2121 (+110)

Highest 2069 → 2259 (+190)

f:id:TABTABTAB:20201231174459p:plain
2020年のPerformance*1

Codeforces

Rating 2160 → 2113 (-47)

Highest 2160 → 2216 (+56)

AC Count

月ごとの AC 数（抜けてる月がいくつかあるけど）

1年間の heatmap (AtCoder/Codeforces/AOJ/yukicoderの合計)

f:id:TABTABTAB:20201230185507p:plain
AC heatmap *2

5, 6, 7 月あたりはそこそこ精進してたけど、それ以外の月はほぼ精進できてないですね...

ライブラリ

online judge verify helper*3 を導入してライブラリの整備を始めました。

github.com

今までライブラリをほとんど持っていなかった*4ので自分的にはかなり進歩しました。*5

HLDとかはまだ持ってないので引き続き整備を進めていきたいです。

まとめ

「M1でICPCを引退するし、M2になるとあんまり競プロできなくなるだろうから2020は競プロを真面目にやろう」と思っていたはずなんですが、結局全然精進できませんでした。 まだICPC横浜までは時間があるので、頑張ろうと思います。

今年はオンサイトがなかったので ICPC 横浜には頑張って欲しいですが、どうなるんでしょう...

レートに関しては目標を定めてもしょうがない気がしてきたので、来年はAC数とかの目標を立てようと思います。

*1:https://atcoderapps.herokuapp.com/atcoderperformances/show_graph/?username=TAB&rivalname=&since=2020-01-11&until=2020-12-27

*2:https://rika0384.github.io/ac-heatmap/?handle_atcoder=TAB&handle_codeforces=TAB_0905&handle_aoj=TAB&handle_yukicoder=TAB

*3:https://github.com/online-judge-tools/verification-helper

*4:遅延セグ木すら持ってなかった

*5:AC-Libraryができたので結果的に整備してなくても助かっていたのかもしれませんが

ICPC 2020 国内予選参加記

ICPC 2020 国内予選に参加しました。

今年はえびさんと monkukui 君と僕の 3 人で tsutaj というチーム名で出ていました。

去年まで 3 年間はつたさん、えびさん、僕で four-t というチームで出ていましたが、つたさんが卒業してしまったので、つたさんの代わりに monkukui 君に入ってもらって、つたさんにはチーム名になってもらいました。

コンテスト直前

2 限の講義を受けて、セコマでご飯を買って 12:00 過ぎくらいに会場についた気がします。リハーサルの問題を解いたり、 monkukui 君と library checker の問題をみたりしていました。簡単目のバチャをやったりもしていました。

コンテスト中の流れ

最初問題が見れなかったけど、10分程待つと見れるようになる。

monkukui 君が A, えびさんが B, 僕が C を読む。A, B は順調に AC されるが、C が全然分からずとても焦る。C が解けず困っていると北大の他のチームが C を通し始めてさらに焦る。

しばらくして、手元実行なことを思い出して時間がかかりそうな解法を実装して実行してみる。テストケース 1 の実行が 15 分くらい待つと終わったので、提出し 2 つ目のテストケースを実行する。 テストケース 2 も 15 分程で終わって提出し、AC。

この時点で学内 3 位だった気がする。このままでは予選落ちなので焦る。

この辺の記憶が曖昧。

D, E に取り組んでるえびさん、monkukui 君と話す。D は 16! は厳しくて、bit dp っぽいよねとか、解を決め打ってみる、とかを話した気がする。E は 2 行前にすすむしかないので、偶数行目と奇数行目は分けれるよねとか、分けたあとも市松模様みたいな感じで分けれるよねとかを話した。

気がつくと slack に 「D 解けた気がする」みたいに書いてあって、すごい。

えびさんがそのまま実装して、AC, すごい。

E がバグったりしてるらしいのでえびさんがデバッグを手伝っていた気がする。

僕は F を多分かけそうな気がするので書く。UnionFind っぽく連結成分のサイズを管理しながらいい感じにやる。

E のデバッグが終わったらしく、提出すると AC して 5 完。

monkukui 君の手が空いたので F の愚直を書いてもらう。

F が書き終わり、サンプルが通ったので投げるも WA。えびさんにコードの説明をしてデバッグするやつをする。えびさんが手元で実行すると RE になるみたいなことを教えてくれる。配列外参照をしてるところを見つけて直し、提出しようとしたところでコンテスト終了。

結果

全体 18 位、学内 1 位で予選突破でした。

4 年連続で突破できて嬉しいです。アジア予選はオンサイトで開催してほしいですね。

国内予選で 5 完したのは初めてだし、順位も今までで最も良かったので成長を感じますね。この調子でアジア予選も頑張りたいです。

XOR に関連した問題

XOR が問題名に入った問題はたくさんある。

XOR の性質

  • x \oplus y = y \oplus x
  • (x \oplus y)\oplus z = x \oplus (y \oplus z)
  • x \oplus 0 = x
  • x \oplus x = 0

この性質から次の性質が成り立ちます．

  • 数列全体に対してある値で XOR をとっても階差は変化しない (A_i \oplus x) \oplus (A_{i+1} \oplus x) = A_i \oplus A_{i+1}

他にも，以下のような性質があります

  • (2x)\oplus(2x+1) = 1
  • (2x)\oplus(2y) = 2(x\oplus y)

足し算は XOR と AND を用いると次のように表せます

  • x+y = 2(x \And y) + x \oplus y

よくあるパターン

  • bit ごとに見る
    求めたい値が bit ごとに求められる場合使える
    0/1 の個数を数えたり，桁 dp をしたり

  • binary-trie*1*2 を使う
    数の大小が大事なときに使う？
    数の追加削除，全体に XOR ，K 番目に小さい/大きい，x より大きい要素の数，とかができる

  • 自分自身と XOR を取ると 0 になる性質に注目する

  • F_2 線形代数
    集合を扱うときに使える？

問題

bit ごとに見る
binary-trie を使う
自分自身と XOR を取ると 0 になる性質に注目する
F_2 線形代数
未分類

*1:

みんなのデータ構造

みんなのデータ構造

  • 作者:Pat Morin
  • 発売日: 2018/07/20
  • メディア: 単行本（ソフトカバー）
この本に載ってる（古い版？は無料のpdfが見れる）

*2:https://kazuma8128.hatenablog.com/entry/2018/05/06/022654 ここも詳しい

ICPC 2019 Asia Yokohama Regional 参加記

ICPC 2019 Asia Yokohama Regional に参加しました。

2017 Tsukuba, 2018 Yokohama に続いて 3 回目の参加でした。

結果は 4 完で 26 位でした。あと 1 問くらいは解きたかったところですが、一応去年・一昨年よりは良い順位を取ることができました。

2017 年に ICPC に参加し始めてから 3 年間、four-t というチームで参加してきましたが、それも今年で終わりになってしまいました。

つたさんが卒業してしまうので、来年は僕 (TAB) とえびさんともう一人（多分 monkukui 君 ? ）でチームを組むことになりそう。

ICPC に参加できるのは来年で最後なので頑張りたいですね。

コンテスト中に気をつけること

思いつき次第追加する

全体的なこと

  • 問題文だけ読んで考察を始めない。問題を開いたら制約・サンプルまで一度目を通す。（誤読して実装した後に気づくの防止）
  • 提出する前にコードを見直す（後で書こうと思ってたことを忘れたりしがち）
  • できるだけ最大ケースを試す（入力が整数一個の時とかは簡単なのでやる）
  • 0-indexed と 1-indexed を同時に使わない

やりがちなミス

  • 負の割り算で壊れるやつ
  • リーディングゼロを弾くとき "0" を弾く
  • H と W, N と M, R と C とかを逆にする

WA の原因がわからない時

  • 小さい制約で愚直解と比較
  • 出力のフォーマットはあっていますか（特に構築とかでやりがち）
  • 最小のケースとかコーナーはありませんか？
  • 実装方針を変えてみる

TLE の原因がわからない時

  • 関数の引数で無駄に vector のコピーとかをしてませんか？（参照で渡す）

考察が詰まった時

  • わかっていることを整理する
  • 愚直を考える
  • 実験
  • より簡単な問題を考える
    • 一般グラフの問題→木の場合を考える
    • 木の問題→パスの場合を考える
  • 単調性はありますか？二分探索できませんか？
  • 入力が行列 or 考察すると行列が出てくる → その行列を隣接行列だと思ってグラフを考える

ICPC 2019 模擬国内予選 参加記

JAG の模擬国内予選に参加しました. four-t 全員で出る模擬国内は実は初めて.

コンテスト中の様子

つたさん, えびさん, 僕の順で A, B, C を読む.

A はつたさんがすぐ書いて通し, B はややつらそう？だったけどえびさんが通す.

C を読みながらシミュレーションやるだけか〜？とか思ってると制約に 109 とか書いてあって無理じゃーんってなる. しょうがないので実験を手でやる. パソコンが空くタイミングがあったので実験のコードを書いたらバグる.

えびさんに手伝ってもらったりしながら考察を進めるといけそうな感じになったのでえびさんに書いてもらって AC.

K は多角形のケイっていう問題があるとえびさんから聞いていたので K 問題やるか〜と思うが、問題が H までしかない.

よく見ると G 問題がその問題だと気づくので, G を読む. 構文解析の F がつらいらしく, えびさんと G の考察をする.

凸包を最初にとって, 内部の点を一つづつ追加していくと良さそうな気持ちになる. priority_queue を使って周長が短いのだけ残して BFS をすると良さそう.

パソコンが空いてるので書く.

写経したりして書き終わるも, サンプルが合わない.

周長の短い K 個だけを保存してたけど, とりあえずちょっと多めにもつようにするととりあえずサンプルには合うようになる.

時間もないので出すが WA.

よく見ると priority_queue に要らないものだけ残って, 必要なものを捨てるようになってるのに気づいて直すが間に合わず, コンテスト終了.

反省

  • 実験のコードをバグらせない. 計算量悪くても良いからバグらせず, 短い時間で書けるような方針を選ぶべき.

  • 幾何があるからといってそればっかりやるのはあんまりよくない. 他の問題も内容くらいは把握した方が良さそう.

  • C みたいなやつ実はえびさんに投げたほうが早い？

  • タイピングが苦手. 写経で無限に typo する.

終わりに

本番はもっと良い順位をとりたい.

終わった後少し直したら G が多分できた.