JOI春合宿2020Day2

結果

4+0+6=10pt

日程内8位(unique)

二日間累計7位(unique)

A：色々な辺が混じったグラフの色の種類数で辺を特定する

B：グラフの辺の増加のシュミレーション

C：数え上げ、1,1,2,2,..,N,Nのものが変化して、最終状態から初期状態を数える

経過

□9:00(0+0+0=0pt)

コンテスト開始

Cを眺める

天才の見た目をしているのでサンプルケースで観察をするが、解法につながらない

□9:21(0+0+0=0pt)

Bを眺める

難易度が低そうな見た目をしているので、解法決め打ちで考察をする

B-2の17点に対して強連結成分分解を実装するが、途中で嘘とわかりやめる

□9:59(0+0+0=0pt)

Aを眺める

A-2,3を考え、二つペアに質問するだけでは特定ができないことを確認する

A-1を実装する

ファイルをダウンロードしてgraderを生成し、それをクリックするが実行されない

コマンドに"grader"と打つがcommand not foundになる（"./grader"が正解らしい）

仕方がないので目視コンパイルで4点を取る

□10:34(4+0+0=4pt)

Bを考える

相互フォローのグラフの連結成分に注目することがわかる

具体的な良いシュミレーション方法が分からないので別の問題に移る

□11:01(4+0+0=4pt)

Cを考える

値の大小関係のオーダーで走査してDPをすることを考えるが、状態量が多すぎることに気づいてやめる

□11:18(4+0+0=4pt)

Aを考える

A-満点を念頭に、集合SとS+xでの差分を使った二分探索を考えるが、うまく値が定まらないことがわかる

場合分けに疲れたのでやめる

□11:56(4+0+0=4pt)

Cを考える

C-1のN=13のケースすらわからないので、Day1のAの教訓で実験することにする

N=3,4,5のケースで実験すると、答えの個数や出現方法に規則性がないことがわかる

どの問題も解けないので、頭を冷やすためカロリーメイトとラムネを食べに行く

□12:14(4+0+0=4pt)

Bを考える

考察の正当性に自信がなかったので、B-1の1点を取ってverifyすることにする

一回のクエリで複数の成分間で相互フォローが増えるケースを考慮していなかったためWA

WAの原因が分からないため別の問題に移る

□12:52(4+0+0=4pt)

Cを考える

DPの走査の方向を値の大小ではなく列の方向に取ることを考えると、A-1の6点の3^nのDPがわかる

丁寧に実装するとサンプルが一発で合って6点が得られる

□13:26(4+0+6=10pt)

Bを考える

B-1の1点のWAの原因を考え使っている性質を証明し直すが、実装に近いパートのそもそも問題として考えていなかった箇所に間違いがあり、気づかない

□14:00(4+0+6=10pt)

考察

たまたま真っ先に思いついた一つの（間違ったor面倒な）方針に時間をかけすぎている

どっちつかずになるのは確かに良くないが、常識的な方針はひととおり挙げてから考えた方がやはり安全

JOI春合宿2020Day1

結果

100+6+12=118pt

日程内7位(unique)

A：AとBの個数が等しい単調増加列をひとつ構成、難易度9

B：4つの点を長方形の中にいれる、難易度12

C：点がワイパーで移動する、難易度12

経過

□9:00(0+0+0=0pt)

コンテスト開始

Aを眺める

誤読防止のためA-1のDPの11点を実装する

方針を固めずに実装したら途中で手が止まったのでやめる

A-2を考えるが、何もわからない

□9:17(0+0+0=0pt)

Bを眺める

配点がふざけているので、簡単枠を疑う

B-満点を考えるが、わからない

B-1のK=1のケースの2点を提出する

□9:37(0+2+0=2pt)

Cを眺める

C-2のSegtreeの10点まで考える

C-1の1点を提出する

□9:50(0+2+1=3pt)

C-2のSegtreeを実装する

途中で実装に疲れたのでやめる

□10:01(0+2+1=3pt)

A-満点を考える

問題をより簡単な問題に言い換えることに成功

□10:34(0+2+1=3pt)

Bを考える

簡単枠だと信じているので、{左端の最大値,右端の最小値}×{下端の最大値,上端の最小値}の4点を出力するがWA

K=2のとき(左端の最大値,下端の最大値)と(右端の最小値,上端の最小値)の二つを出力するコードを提出するとACとWAが交互に出る

なので、もう一種類のペアの組み方も試すとK=2のケースに正解する

□11:00(0+6+1=7pt)

A-満点を考える

前の考察を見直すと、言い換えた後のより簡単な問題が解ける

実装が重いので丁寧にレジュメを作ってからコードを書く

想定解・多くの人の解とはまったく異なる方針で解いており、実際は難易度9だが、難易度11相当が解けたと思って喜んでいる

□12:58(100+6+1=107pt)

C-3のSegtreeの11点を実装する

□1:21(100+6+12=118pt)

C-4の53点を考える

慣れていないデータ構造を使って領域処理をしなければいけないことがわかるので、やめる

□1:40(100+6+12=118pt)

C-2のSegtreeの10点を実装し提出するが、WA

□1:58(100+6+12=118pt)

□2:00(100+6+12=118pt)

考察

天才っぽい見た目の問題でも部分点を固めることが満点につながる

A問題 Building4の解法

（１）左右から最善の単調増加列を伸ばして、それに乗らないものにバツをつける。両方にバツがついた箇所があったら解なし。

（２）片方にバツがついたところを挟んで左右は独立なので分ける。

（３）両方マルの箇所が隣り合っているとき、a[i],b[i]の大きい方からa[i+1],b[i+1]の小さい方に行けないことがある。そうでないとき、iまでとi+1は独立なので分ける。（１）の操作の性質より、a[i],b[i]の小さい方からa[i+1],b[i+1]の小さい方にいけなかったり、a[i],b[i]の大きい方からa[i+1],b[i+1]の大きい方にいけなかったりということはない。

（４）iの大きい方からi+1の小さい方に行けないということは左下の図のように表せ、左からいくつかは小さい方を選んで、それより右は大きい方を選ぶ必要がある。また、そのような選び方がいつもできる。

（５）一旦全て大きい方を選ぶことにして、左のいくつかを小さい方に変えることを考えると、左下の図のように累積和の最小値から累積和の最大値までAの個数を変化させることができる。

（６）すべての区間で累積和の最小値を取ったり累積和の最大値を取ったりしてもAの個数がNにならないなら解なし。そうでなければ、それぞれの区間で累積和の値を指定して、累積和が指定した値になるように反転すると具体的な解が得られる。

計算量はO(N)、実装は面倒（index、反転or反転しないなど）

IOI2019Day2

結果

59.9+12+15=86.9点

190位相当

 IOI2019 Day1-155点＋Day2-86.9点＝合計241.9点

170位（メダルなし）相当

経過

実施日程　2010/3/17(火) 9:00~14:00

A：OutputOnly、二次元グリッドの点を折れ線で被覆

B：変な形式、マンハッタン距離がKかの判定をするAND、OR、NOTの式を構築

C：最短距離、地面に平行か垂直の直線上を移動する

競技の環境を変えてみようと思い、リビングに移動する

母親に文句を言われる

□9:00(0+0+0=0pt)

コンテスト開始

エディタの準備

Cを眺める

C-3、C-4のs=0,g=n-1の小課題に対して、貪欲法的な限定をしたDPを提出する

C-4の18点はWAになり、C-3の15点だけを得る

□10:11(0+0+15=15pt)

C-4がWAになる原因を探して証明を確認するが進展なし

時間をかけすぎたので別の問題に移ることにする

C-1、C-2の24点の簡単な拡張Dijkstraは、C-4を検討する時に実装することにする

□10:25(0+0+15=15pt)

Aを眺める

inputを読み込みoutファイルを生成するプログラムを書き、A-10点くらいの移動毎に2回折れる出力を提出する

□11:09(12+0+15=27pt)

A-20点くらいの、折れる方向を交互にする出力を提出する

10個ケースがあるが、out7が10点満点になって他はそれぞれ2.2点くらいになった

□11:25(34+0+15=49pt)

A-30+点くらいの、外側から螺旋状に回る出力を提出する

既に満点のout7を除いて、6つのケースが5~9点になり、3つのケースが2点のままだった

□11:41(59.9+0+15=74.9pt)

配られたヴィジュアライザで点数の低いケースを見ると、スコットランド国旗やイギリス国旗のような形状をしていた

時間をかけすぎたので、Bに移ることにする

□11:47(59.9+0+15=74.9pt)

Bを読む

読んだ結果、誰が解いても制約の100倍良い回数で満点を得られてしまうような問題になる

何度も読む

英語が難しい

正しい題意がわかる

□12:42(59.9+0+15=74.9pt)

B-満点に対して、思いついた解法を提出する

H=1のサブタスクだけに正解する

□13:01(59.9+12+15=86.9pt)

誤読を疑って再び英文読解をする

誤読が無さそうだということがわかる

□13:43(59.9+12+15=86.9pt)

解法の方を疑うと嘘であることがわかる

題意（小課題の制約の意味）を理解し、満点解法を実装する

終了8秒前に提出するがWAになる

□14:00(59.9+12+15=86.9pt)

デバッグをすると、焦ってfor文の中で違う添字をインクリメントしていたことがわかる

提出すると100点が得られる

□14:16(59.9+100+15=164.9pt)

考察

なんだこのset

精神的な耐性がついたということにしておく

IOI2019Day1

結果

50+65+40=155点

150位相当

経過

実施日程　2020/3/16(月) 9:00~14:00

A：二次元グリッド（難易度10.5くらい）

B：転倒数を最小化（難易度8くらい？無限人解いているがわからず）

C：グラフ・ひとつ構成（難易度12）

JOI春2017-自然公園の77点が分かったので、それを提出して正解した

□9:00 (0+0+0=0pt)

コンテスト開始

エディタの準備

Bを眺める

B-満点に対して「ARC088-E PappleSort」の解法を提出すると45点分のサブタスクだけ正解し、WAになる

□9:32 (0+45+0=45pt)

Cを眺める

C-2 成分数が１のケース、深さ優先探索

C-3 木のケース、C-2を利用する

C-1 サイクルのケース、C-3を利用する

□10:19 (0+45+40=85pt)

Aを眺める

A-1からA-3 累積maxの前処理、長方形を決め打って一回O(N)で判定、O(N^5)

枝刈りによってN=200のA-3も正解する

□11:01 (27+45+40=112pt)

累積和によってO(N^4)にすることでA-4の22点を狙うが、700*700*700の配列を作るとコンパイルが通らないため、諦める

累積和を使ったことでH=3のA-5に正解する

□11:21 (37+45+40=122pt)

Bを考える

何も分からない

転倒数を扱う問題全般がよくわからない

□11:53 (37+45+40=122pt)

C-4,C-5を考える

C-4に対して、根をN通り変えたdfs木で木のサブタスクC-3を実行させるが、WA

□12:49 (37+45+40=122pt)

Aを考える

すべてのマスの値が0か1であるA-6を考えると、A-7を含む満点解法の方針がわかる

累積和、累積maxでA-6を提出する

□13:00 (50+45+40=135pt)

A-満点を実装するため、N=8で20点が付けられているB-2を得点しておく

□13:10 (50+65+40=155pt)

A-満点のレジュメを書く

いくつもの細かな箇所で実装の工夫（データ構造）が要求されるため、何を使うか検討する

□13:28 (50+65+40=155pt)

実装を開始する

□13:45 (50+65+40=155pt)

実装が終わる

マスの値が同じものの処理ができていない

処理に足りない点があった

□14:15 (50+65+40=155pt)

出直すことにする

考察

満点級のレジュメ・実装には100分は必要。

「解けたとしたら実装に時間がかかる」というものから時間をかけて考察する。

あと、リアクティブ・マラソンのスコアとか枝刈りの計算量とかの改善への期待と、最適化・数え上げでの正当性への期待は違うもの。

APIO2018 New Home

問題概要

一次元の座標がある。1~Kの色の店が指定された座標に現れたり消えたりするので、色別にある座標から最も近いものまでの距離を求めその最大値を取った値を答える。

クエリは先読み可。

解法

Subtask1

N,Q<=400

時の流れを時系列に、計算クエリ毎にO(N)かけて距離を計算。全体でO(NQ)。

Subtask2

N,Q<=60000,K<=400

時の流れを時系列に、色ごとに店の座標のsetを管理する。計算クエリでは色ごとにset.lower_boundをする。O((N+QK)logN)

Subtask3

N,Q<=300000,店はすべて最初から最後まで存在する

時の流れの存在意義がなくなるので、座標の昇順（対称性より降順でも可）を時系列に取る。それぞれの色で、最も近いものまでの距離は「x+定数」か「-x+定数」の形の関数がその色の店の個数の二倍の個数並んでいる形になるので、それらのうち最適なものがどれかが正しい状態になるようにする。「x+定数」、「-x+定数」のそれぞれの定数の値の候補をsetで管理して、O((N+Q)logN)

Subtask4

N,Q<=300000,店はすべて最初存在し、しだいになくなっていく

何もわからない

Subtask5

N,Q<=60000

Subtask2の手法とSubtask3の手法を組み合わせて、クエリの平方分割をする。

時の流れの時系列に、B(=バケットサイズ)個ごとにクエリを処理する。その期間中にその色の店が現れたり消えたりするような色については、Subtask2の方法を用いて最短距離を計算する。そうでない色については、その期間中常に存在している店だけをピックアップして、Subtask3の方法を用いて最短距離の最大値を計算する。N=Qとすると計算量はO(ANlogN+BNlogN)になって、A=B=√NとすればO(N√NlogN)になる。

しかし、setを使っているO(N√NlogN)なので非常に厳しい。バーチャルでこれを提出したところ、一ケース目から間に合わなかった。

Subtask6

N,Q<=300000

時の流れを時系列に取る。計算クエリでははじめに答えを二分探索し「ある座標の区間内にすべての色が存在するか？」という問題に変形する。

これはセグメント木の基本的な問題である。各店の座標の地点には直右の同色の店の座標を置く。店の追加、削除は色ごとに店の座標のsetを管理しておき、lower_boundで変化した地点のひとつ左とひとつ右を見て、2回くらいセグメント木の一点更新をする。区間[L,R]内にすべての色が存在するかは、[-∞,L-1]のmaxがR以下であるかに等しい。計算量はO(Nlog^2N)。TimeLimitが5秒なので間に合う。二分探索をダブリングでする（セグ木上で二分探索するテク）とO(NlogN)になるが、座標圧縮などの関係で実装は大変になる。

それぞれの色でかなり左の方にひとつずつ店があると仮定して、座標そのものが同じでも店によって違うセグメント木の地点を割り当てるとすると実装が楽になる。

ソースコード

oj.uz

JOI Open 2018

結果

0+100+100=200pt

4位相当

目的

小課題を貪欲に取っていく戦略を継続しつつ、解法のレジュメを書くことを実験する

経過

実施日程　2020/2/15(土) 9:00~14:00

A：平面上のパズル (yutaka1999とyokozuna57をなどの6人以外全員0点)

B：文字列・クエリ (40人くらいが100点）

C：数列・最適化 (9人くらいが100点、他は20点以下)

□9:00 (0+0+0=0pt)

コンテスト開始

□9:10 (0+0+0=0pt)

起床。コンテスト開始に遅刻。

C-1の5点 (R1000)、順列全探索

□9:24 (0+0+5=5pt)

C-2の15点 (R1400)、ビットマスクDP

□9:28 (0+0+20=20pt)

B-1の10点 (R1000)、文字列の同値判定

□9:41 (0+10+20=30pt)

B-2,B-3,B-4の90点 (R2000)、二次元領域和のセグメント木

安全のためB-2の25点のみ実装

□10:09 (0+35+20=55pt)

セグメント木を書いてB-3,B-4の65点に正解

□10:15 (0+100+20=120pt)

A-1の15点 (R2600)を考えるが、何もわからない。

小課題1がわからないのは誤読・勘違いなので、一旦C-3を考えることにする

□10:49 (0+100+20=120pt)

C-3の80点 (R2600)、挿入DP

レジュメを丁寧に書くと、本来ならプログラムを書いた後に修正していたはずの綻びが先にわかる

プログラムをレジュメの通りに書く

サンプル1が間違うので、デバッグを開始する

□11:50 (0+100+20=120pt)

バグの原因は場合分けの漏れ

直す

□12:42 (0+100+100=200pt)

A-1の15点 (R2600) を考える

誤読・勘違いを調べるが、何もわからない

何回も伏して再び考えるが、何もわからない

□14:00 (0+100+100=200pt)

考察

レジュメは良いと思った

C-3はレジュメなしなら時間内に合わなかったと思う

場合分けの十分性を示すべき

JOI Open 2017

結果

28+80+30=138pt

10.5位相当

目的

前日にJOI Open 2018を実施した。パフォーマンスは良いとは言えなかった。

小課題に真摯に取り組む姿勢が足りないと感じた。

今回のJOI Open 2017では分析のため行動を記録することと、解法の概要が掴めた小課題から貪欲に詳細を詰めて実装し得点する戦略を練習することを目的とした。

経過

実施日程　2020/2/14(金) 9:00~14:00

A：インタラクティブ、木（70点以上が25人くらいいる）

B：幾何（80点以上が12人くらいいる）

C：グリッド、最短経路（yutaka1999以外は30点以下）

□9:00 (0+0+0=0pt)

コンテスト開始

□9:10 (0+0+0=0pt)

起床。コンテスト開始に遅刻。

C-1,C-2の30点 (R2000)、座圧・拡張ダイクストラ

□9:47 (0+0+30=30pt)

B-1の5点 (R1400)、区間和最大

□9:59 (0+5+30=35pt)

B-2の20点 (R2000)、複素数平面で回転

□10:14 (0+25+30=55pt)

A-1,A-2の18点 (R1400)、DFS

□10:46 (18+25+30=73pt)

朝食。卵かけごはん。

□10:57 (18+25+30=73pt)

C-3の70点が難易度10であることを疑って考えるが、30分で分からないので高難度と判断

□11:23 (18+25+30=73pt)

B-3,B-4,B-5の75点 (R2400)、偏角を時系列に取って区間和最大のセグメント木

簡単のためB-3,B-4だけに絞った実装

48分バグを探して、何故かわからないまま正解する

□12:42 (18+80+30=128pt)

A-3の10点 (R1400)、周期性

22分バグを探す、手元ではなく提出によってテストする

□13:36 (28+80+30=138pt)

A-4,A-5の72点 (R2200)、混乱した解法をコードにして提出する

得点は得られない

□14:00 (28+80+30=138pt) 

考察

バグを探す時間が多かった。

今回のバグ探しはおみくじの当たりくじを探すようなもので、競技プログラマがやるべきものではない。

プログラムを書き始める前に、5分投資して解法のレジュメを作ることにする。