naoya_t@hatenablog

いわゆるチラシノウラであります

〈AGC埋め〉AGC 500点問題 (AGC 001 B, 002 C, 010 B, 013 B, 014 B)

日課
400点まで埋めてしまったので500点を埋めた
f:id:n4_t:20180718131810p:plain

AGC 001 B - Mysterious Light (500)

X=N-Xのときは正三角形を描いて戻ってくるので3X
そうでない場合は…ユークリッドの互除法っぽく
可動域が三角形か平行四辺形かによって変わる?
サンプルケース増やした
計算あわない(というか思考を組み立てられないというか)

1時間経ったので解説読む
方向性は合ってたんだけど(解説解シンプル)
全部平行四辺形でいいのか
→AC
https://beta.atcoder.jp/contests/agc001/submissions/2860135

AGC 002 C - Knot Puzzle (500)

あれ?隣り合った合計がL以上になる組を最後に持ってくればいいだけでは?
これが500点というのはどうかと思う(まあ初期だし仕方ない)
(htmlのサンプルが想定通りに書かれていないのか自動テストがバグって手動テスト)
→AC
https://beta.atcoder.jp/contests/agc002/submissions/2860182

解説解も同様;

AGC 010 B - Boxes (500)

  • a[]の合計はN(N+1)/2の倍数になるはず(そうでなければ脱落)
  • 合計がN(N+1)/2のk倍だったとする。a[] の隣り合う項同士の差を見ると
    • 普通は +k で
    • 新たに1,2,3..Nが始まる所では+k-Nになってるはず

→WA

  • ああ、同じところから複数の1,2,3..が始まるとき+k-mN だ

→WA

  • 判定方法が間違ってた。(k-diff)%N==0だけじゃなくてdiff≦kもチェックしないと駄目

→AC
https://beta.atcoder.jp/contests/agc010/submissions/2860727

解説解もほぼ同様。(自分の実装では+nの回数がk回だったかを調べているけれどすべてがnの倍数なだけで十分だったりするのね)

AGC 014 B - Unplanned Queries (500)

(AGC 013 Bを飛ばしてこちらから)
ノートに適当な絵を描いて。
パスを他のパスに重ねて各区間を偶数回ずつ巡るようにする…一筆書きできれば行けそう
ってどう検出すればいい?
ああ、各ノードのout-degreeが偶数ならいいのか
→AC 9'03''
https://beta.atcoder.jp/contests/agc014/submissions/2861493
すんなり解けて拍子抜け

解説を読んで

適当な頂点(どこでもいい)をrootとして
クエリ(a,b) = (a,root) + (root,b) - 2(p,root)
ここでpはLCA(a,b)
偶数か奇数かが問われているので2(p,root)の部分は無視できる。
aがクエリに偶数回現れているならaとrootの間に偶数が足されている。
各ノードがクエリに偶数回現れているなら全ての辺には偶数が書かれる。
そこまではOK。
逆は言える?(奇数回現れるノードがあった場合に打ち消せるか?)
奇数があるとそのノードからrootまでの偶奇は反転する、けどそこだけを(他の区間を指定することで)戻すことはできないよね
ってことは全部偶数じゃないと無理

AGC 013 B - Hamiltonish Path (500)

最後の500点問題。
クリークを探してそこで輪を作って…いや他とも繋がってるし無理だ
スタートとゴールの2点の選択を総当たりするのは(N=10^5_NC_2なので)無理
乱択で出来る方法がある?うーむ
(長考)
時間切れ。解説読む

解説を読んで

  • 適当に1つ頂点を取ってそこをスタート地点とする
  • その隣りのどれかをゴール地点とする。(現時点で長さ2のパス)
  • この時点で条件を満たしていれば終了
    • 条件を満たしている=スタートないしゴールから直接伸びている先が訪問済みのスタートとゴールだけ。(まあこれはN>2ならありえないんだけど)
  • スタート地点の隣りに未訪問のノードがある場合:その1つを「適当に」選んで新スタート地点とする(旧スタート地点は新スタート地点の次に寄るただの通過地点になる)。
    • これを未訪問のノードに接することがなくなるまで続ける
  • ゴール側も同様に調べてパスを延長していく。
  • このプロセスはノードを食い尽くすかそれ以前に止まる。止まった時点で出来ているパスを答えればいい。
    • 食い尽くしたということはスタートとゴールに繋がっている全てのノードは訪問済みということで、条件を満たしている。

なるほど、そう考えるのか。(こうしてうまい考え方に接するのが嬉しい)
→AC
https://beta.atcoder.jp/contests/agc013/submissions/2862428

サンプル入力のグラフデータをビジュアライズするやつ作ったw

f:id:n4_t:20180718131214p:plain f:id:n4_t:20180718131216p:plain
f:id:n4_t:20180718131222p:plain