cafelier@SRM

SRM443

SRM | 12:07 |

SRM443 の成績・ソース (要ログイン) : AC/TLE/- : おもしろい問題セットだった

300開く

• 300, 600, 1000 だったので 600 難しそうと思ってヒヨりました…
• 『ちょうど接したり交わったりはしてないけど重なってることはある円が２次元平面上にばらまかれてます。ある点からある点まで行くのに円周を最小で何回越えれば行けますか』

• えーと最小と言えばダイクストラ、というか幅優先か。
  • 300点だから多少ハードなコード書くハメになるんだろうから、そのくらいのコードは書くべきかな。
  • あ、グラフじゃなくてツリーになるから共通の一番下の祖先(LCA)まで上って降りてくるのが最短パスに決まってる
  • それでいこう

• 領域と領域が先祖関係は否かは円同士の包含関係で決まる
• 50領域しかないから、直接の親かどうかは↑を二重ループで回せば求まる

• …とやってツリーを作ったら、ループ回してそれぞれの祖先リスト作って重なってる部分を除いたら最短路！
• できた。通った。

• submit！
  • submitした瞬間に気づいたんだけど、ツリーとかLCAとか考えなくても、「始点を含んでる円の数 + 終点を含んでる円の数 - 両方含んでる円の数*2」でいいのでは…俺はアホか…

600開く

• 問題文短い！すばらしい
• 『A個の0とB個の1があります、1回の操作でちょうどK個の数字のビット反転できます。全部1にするのに必要な操作は何回』
  • A,B,Kは100000まで。

• えーと単純に幅優先探索すると
  • A+B=200000状態あって、それぞれからK通りの反転の仕方があるから、200億。死亡。Kが大きすぎると逆に手が減るけど、それでも√K手くらいを20万にかけたら十分死ねるなあ

• 0の個数がKの倍数だったらひたすら0を反転していけば終わるからA/K回だなあ。
• それ以外の場合もなにか最寄りのKの倍数に行ってそっからKずつ減らすパターンに必ず落ちるはず。最寄りとは限らないか。
  • で、どうやって最寄り？のKの倍数に行く最短操作を求めるのか…

• Aが奇数でKが偶数だったら絶対無理だよね。
  • AもBもKも偶数だったら全部2で割っても同じ答えになりそうな気がする
  • とかやって次々減らしてって互いに素に持ち込むとなんかGCDになったり
  • …わからん。

• うーん
• 残り25分

1000開く

• 600より1000が簡単だったりするのでは
• まとめると『9ノード以下のグラフに重さ9以下の有向edgeがたくさん張られてる時に、min以上max以下のパスの総数をmodなんか大きい数で数えてね』
  • minとmaxは10億くらい

• modなんとかということは探索ではなくてDPとかで、minとmaxが10億ということは下から律儀に埋めるのは無理で行列乗算とかだ。
• なんか9x9か81x81の遷移行列組んでどうにか…

• うーんまとまらない
• 残り15分。考えまとまってもちゃんとコーディングするの無理だなあ。600のコードなら10分あれば書けそう。

再度600

• まあしかし思いつかないので、
  • 幅優先の遅いコード書いておいて時間のかかるケースをみつけておき、あとで撃墜用に使う
• という戦略で行く。

• まあ5分で書ける。100000,100000,19999 とかで盛大に時間がかかって終わらない。よしこれで撃墜する。

• さっきの、Kの倍数ならA/K回で行ける、というのを下端にして枝刈り入れるとどうだろう。
• 入れてみた。
  • …いろいろ試してみても、手元で最悪1.4secくらいで通る…
  • 出しちゃおっかなー。行けたりしないかなー
  • システムテストは通らなくても仕方ないけど、そうそう撃墜できないはずだから…
  • そうだ！他人にunsuccessfully challengedの山を築かせる嫌がらせを！

• 出しちゃった
  • 撃墜タイムは突破、システムテストで死亡。そんな甘くはないよね、やっぱり

撃墜タイム

• 100000,100000,19999 で2人撃墜。
  • 二人ともただのBFSだったんだけど、片方自分のスタイルと違うやり方だったので読むのに時間がかかった。

感想

• 狙って撃墜できると満足してしまう
• 満足してないでまずはLv2問題を確実に解けるようにしなさい自分