コンテストページ
https://codeforces.com/contest/600
20:30くらいからやりますhttps://t.co/ipyBWT9svq
— idsigma (@IKyopro) February 1, 2020
カツサンドさんバチャです。
解法
✔A - Extract Numbers
これはなんですか？
C# ならば Split と SelectMany で分解ができます。 整数である条件は、すべてが数字で、空でなくて、長さが 1 もしくは先頭が '0' でないです。
Aはコード編集ミスを直したら通った。2桁目以降に'0'がある場合を数字でないほうに分類してた。。アホです
— tarattata (@tarattata1) February 1, 2020
✔B - Queries about less or equal elements
A をソートして二分探索です。
✔C - Make Palindrome
登場回数をカウントです。 奇数回登場するもののうち、最大のものが真ん中です。 真ん中が必要なければ、'$' とでもして出力のときに消せばよいです。 すると奇数回登場するものは偶数個ありますから、小さい半分を 1 つ増やして、大きい半分を 1 つ減らして全部偶数子にしましょう。
✖D - Area of Two Circles' Intersection
難しそうな見た目をしていないのに無限人落ちていてびっくりしています。 私だけ嵌ったのかと思っていました。
交わらない場合は例外処理です。 交わるときには、交わっている領域の境界の 2 つの弧の円周角を t0, t1 としましょう。 すると、真ん中で切ると面積は r0 * r0 * (t0 - cos(t0) * sin(t0)) です。
不思議ですね。円周角が 90 度以上の場合にも大丈夫そうかなと思ったのですが、どうなのでしょう。 角度は余弦定理で計算をして、sin は cos から計算をしました。 不思議です。
これってトリビアになりませんか？ なりませんね。
このように分けるとうまくいきそうなのですが、どこか間違えているのでしょうか。基本となるピザに三角形を足すか引くかをするのですが、sin の符号がいいお仕事をしてく、るイメージです。 pic.twitter.com/rVte7Dgl6i
— ながたかな (@ngtkana) February 1, 2020
わあ、ありがとうございます。修正をしたら Wrong answer on test 28 まで進みました。このケースは
— ながたかな (@ngtkana) February 1, 2020
-999999999 0 1000000000
999999999 0 1000000000
で、誤差ギリギリで落ちているようです。これはなんんとも、難しいです。
ところで修正箇所はこちらです。幾何って難しいですね（はい！？） pic.twitter.com/mHx3tkTA1n
C# に long double はありません。（Arccos が 2 乗で接しているので厳しそうかなと思ってコンテスト中に調べた人です。）64 bit 浮動小数点数でも工夫をすれば通るのでしょうか。なんにしても、角度自体は面積に直接必要ですから、どうしても必要です。困りました。
✖E - Lomsat gelral
管理するものは - m: 部分木の中に何色がいくつあるのか - M: 何重に重なっているものの色番号の合計がいくつなのか - hi: もっとも重なっている重複度はいくつか です。
これは、頂点が 1 つ増えたり減ったりしてもきちんと更新が出来ます。 一番難しそうなのが hi の更新ですが、こちらも - hi よりも大きなものが誕生したとき +1 - hi が 0 になったとき -1 で大丈夫です。
ところで私の Mo がうまく動かなくて困っています。 あまりに意味のわからないバグり方をしていますから、もう諦めて書き直した方が良さそうでしょうか。 Mo を書きたくないからと、やすやすと C++ に切り替えたばちがあたったのかもしれません。
バグ
こんなバグり方あります！？
queries にクエリを入れているのですが、クエリ番号 id が、いつの間にか 1 から 2 に書き換わっています。
コードコメントアウト全探索の結果、どうやら append の中で m[c[i]] を増やすところで変わっているようなのですが、原理がわからなさすぎて泣いています。アクセス制限やキャプチャーの仕様をきちんとわかっていないということなのでしょうか。いずれにせよ私は C# に移行することを決めましたから、後日そちらで通したいところです。
