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面倒な）方針に時間をかけすぎている

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