A | B | C | D | E | F | |
問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
自分の提出 | ■ | ■ | ■ | ■ | ■ | |
結果 | AC | AC | AC | AC | RE |
全体感想
ABCE の 4 完で、478 位です。
F をバグらせてしまい、本番中にとりきれなくて、いまいち順位になりました。
残り30分くらいの段階で、一応 5 完はしておこうかと思って E までを解きにかかりますが、この E もなかなかくせもので、E → A → B → C と提出したところでタイムアップしました。
F は、複数箇所バグらせていて。y 座標を一意な x 座標の値と比べて座圧していたりみたいなひどすぎるミスも発覚までに時間がかかりw 最後には 94AC + 2RE まで到達したのですが、線分同士が重なる場合にバグらせていました。
バグの要因特定には、ランダム生成ケースとの愚直解法合わせをする方法がありますが、愚直解法を書くのが面倒でやりませんでした。しかし、WA はともかく RE に対するテストに関しては、ランダムケースを作成してまわす労力は十分小さく抑えられるので、やるべきだったなあと反省。
問題C – : (Colon)
余弦定理の解説で話題になっていましたね。
問題文を見て、「座標が分かるよね」と反応するか「長さとなす角が分かるよね」と反応するか、どちらも十分自然だと思うので、先に考えたもので実装すればよいでしょう。特筆すべき面倒さの違いはほとんどないと思います。
z1 = A * complex(cos(t1), sin(t1))
指定の半径と偏角を持つ複素数の実装です。
z1 = A * np.exp(t1 * 1j)
z1 = cmath.rect(A, t1)
というのもあるようです。
余弦定理
余弦定理は、単純には、三角形の「二辺夾角」あるいは「三辺」が与えられたときに、他の辺の長さや角の大きさを求めるために利用できる定理です。「二角夾辺」であれば、正弦定理が使えます。合同条件に代表される三角形データの与えられ方に一通り対応できますね。
私は本問では使いませんでしたが、競プロでの使用経験は何度かあります。例えば、
問題 D – .. (Double Dots)
最短路に沿った木を作ればよくて、当然 BFS木 が条件を満たす。という問題です。
折角なので、BFS木について簡単にまとめます。連結グラフ
BFS木における根からの距離を「深さ」と呼ぶと、次の性質が成り立ちます。
(1) 深さが
(2) 深さは
BFS の探索順から容易ですね。 例えば
(1):深さ
(2):(1) より辺が深さを
本問題では、BFS木に沿って「道しるべ」を置けば、「深さ」の回数で根に到達できるため、(2) よりBFS木が条件を満たします。また、本問題では問われていませんが、(1) の知識が役に立つ問題もあります。
BFS 木、DFS 木はグラフを調べる基本的なツールなので、簡単な性質(他の辺はどこにできるのかなど)はおさえておくと、時々役に立つと思います。
問題 E – ∙ (Bullet)
まず、
全てのペア
正確には分数表記をすると、ちょっと分子または分母が
各有理数(あるいは射影直線
これは、だいたい
各
「グループ
例えば 「
これらの計算を各
有理数
約分したり、分母の符号を固定したりして同じ有理数に一意な表示を固定して対応します。あるいは、巨大な素数
考察も、実装の細部を詰めるところも、問題 E にしてはなかなか難しめだったのではないでしょうか。
問題 F – . (Single Dot)
解説がとても短いですが、んーまあ確かに、考察は一瞬という人も多いと思います。
グリッドグラフっぽい出題であることはすぐに分かります。平面全体をマス目に区切ってあげて、隣のマスに移動できるかを考えてあげることで、グラフの連結成分の大きさを計算する問題になりそうです。
今回は制約が「
今回の問題では、牛さんの移動は格子点から格子点と考えるよりも、領域から領域への移動と思った方が良さそうです。初期位置が頂点ですが、それは適当な領域に入れてしまいましょう。
領域を、縦に
地味に、通行止めの実装に悩み。はじめ移動可能方向を隣接リストで作って通行止めを削除していきましたが、効率は悪かったです(効率は関係ないけど、ここで同じ値を 2 回削除するバグを踏んでいました)。どの頂点からも
なるほどなー。中途半端に出っ張ってる線分は捨てちゃえばいいと(交点のできうる座標にしか興味を持たなくてよい)。頂点数が
→ (131ms) https://atcoder.jp/contests/abc168/submissions/13389928
numpy の import に 100ms 程度かかっていることを除けば、他言語の最速付近と比べても遜色ない実行時間ですね。