ICPC2019国内予選に参加しました
ICPC2019国内予選にwe regret to inform you...というチームで参加しました。3完86位という結果で完全に実力不足ということで納得していたのですが、ホスト校枠の関係で85位の慶応のチームがアジアに行く見込みらしくてwe regret to inform you...という結果になりました。
僕はD問題担当で、3時間ずっと「DPだよなぁ・・・」と言い続ける係をやりました。区間を結合していくDPを考えていて、想定解のやり方は全く考えていなかったので完全にダメでした。あとは一応Cの考察もしました。予定通りですが僕はキーボードを1秒も触っていません。
おそらく今後は競プロを頑張ってやることはないと思うのですが、楽しかったので良かったです。チームメイトの2人、いつもありがとうございます。ICPCは終わりですが今後もよろしくお願いします。
M-SOLUTIONS プロコンオープン
いつも通り自明早解き青パフォだった。そろそろ黄パフォが欲しいなということはずっといっているが、実力が付いてきていない。
CかEは解けるべきだった。なんだかmodの逆元の扱いが頭の中でまとまっていなかった。
AOJ2511 Sinking islands (JAG Domestic 2013 D)
時間を逆から辿り、連結であれば最小全域木を構成して、状態を保存する。ただし、遡る過程で連結でなくなった場合には状態をリセットする。
連結でなくなったときに建設を止めるというところの認識を間違っていて、後々連結になったら建設を再開すると考えていてバグを産んだ。しかし読み直してみても若干問題分が曖昧だと思うので、そこを考えなければ致命的なバグはなくて一時間程度で解けていたので悪くはないと思う。プリム法は難しくはないが実装に慣れていないので少し遅くなってしまったし、簡易版なので計算量が少し多いものを実装した。今回は制約が緩かったが、速い版が必要になっても対応できるようにしておきたい。
AOJ2510 Twin book report (JAG Domestic 2013 C)
まず本を読み終わる時間を最短にするには一人目が所要時間の長い順に本を読み、二人目の子供は二冊目から同様に読めば良い。一人目が一冊目を読む間に、二人目が二冊目以降を読み終わらない場合は最適性は明らか。全て読み終わったあとに仲良く感想文を一緒に書けば、最短終了時間も明らか。
二人目が二冊目以降を読み終わってしまう場合にも、とりあえず本を読み終わる時間は最短であることが分かる。二人目は一冊目以外を読み終えたあとに一人目が一冊目を読み終えるまでの間で最も長い時間を作文に費やすのが最適となるので、これはDPで求められる。
確かに分かってしまえば簡単だが、長い順に読むというのも自明というほどではないのでC問題にしては難しいと思う。
AOJ1236 Map of Ninja House (ICPC Asia 2002 E)
AtCoder Beginner Contest 126
AOJ2586 Wish upon a shooting star (JAG Domestic 2014 E)
AOJ-ICPCで500点までの問題のICPC国内予選過去問は概ね解いたが、バグも多いし時間もかかってしまっているので、この辺りの難易度で模擬国内やアジアの問題を少し解いていきたいと考えている。
この問題は一見すると幾何問題だが、実際には幾何の要素は薄い。星の半径変化と星の距離に関する二次方程式を計算することで接触時間を求める問題。あまり競プロでこういう問題は見たことがなかったので方針があっているか不安なのだが、いま模擬国内のサイトが落ちているようで講評が見られない。
方程式の係数を求めるのが面倒なのでバグらせることが目に見えていたためコーディングを始めるまでに10分以上使って念入りに構成を考えた。その結果、なんとバグなしで実装することができた。最近はバグらせてばかりだったので逆に驚いてしまった。実装にはなんだかんだ1時間かかってしまったのでコーディング速度を上げる必要はある。
