transirubyをやっていた。普通にマップが広くて世界観があって良い。神巫女とエフェクトとか敵キャラとか使いまわしすぎみたいな感想を最初持っていたが、まさかのヤマトが出てきたので、どちらかというとスターシステム的なアレかもしくは世界観共通までありうる。どういう立ち位置なんだろ。
ABC335に出た。Eで変なミスをして時間を溶かすところだったが、気持ちを切り替えてFを解いた上で落ち着いてデバッグしたらEも通せた。本当は変なミスをしないのが理想ではあるが、リカバリできたのはできたので良いこと。
A: やるだけ
B: 21^3全探索
C: 面倒なのでvectorに次の頭の位置を次々詰め込んでいった。別に律義に尾を除く必要はない。
D: ぐるぐるさせればよい。実装としては壁orすでに書き込んだマスに当たったら90度方向転換という形にした。
E: BFSというか変則的なダイクストラというかDPというか。どうせ数字の大きい頂点から小さい頂点に遷移することはないので、優先度付きキューに(頂点の数字, 頂点)の組を入れて最大種類数をメモってやっていった。少し問題になるのは同じ数字が書いてある頂点の遷移で、そこは種類数を増やさず遷移させた。
「隣接頂点での最大種類数を更新するならキューに追加」としているところの実装をミスって時間を食ってしまった。if(nowvalue < newvalue) nowvalue = newvalueとすべきところをif(nowvalue != newvalue) nowvalue = newvalueとしていた。chmax&変化が起きるなら何かする、という処理はちょこちょこやるが、いい感じの書き方はないものか。
F: あんまり複雑なことはしない。塗り方のパターンは移動の仕方のパターンと1対1に対応するので、移動の仕方のパターンを数えればよい。各マスから配るDPをすればよいのだが、これだと$\sum N/A_i$かかってしまう。そこで、同じ値を持つ$A_i$はまとめて処理してしまいたい。それさえできれば調和級数で$O(N\log N)$になる。よく考えたら同じ値を持つ$A_i$があっても飛び越えてしまう場合を考えてなかった。解説を読む限り計算量$O(N\sqrt{N})$なのか？あまり理解していない…
「自分自身に到達するパターン数」と「同じ値を持つ前のマスから配るのを委任されたパターン数」をそれぞれ持っていい感じにした。もっといい言葉で整理できるかもしれんがめんどい。
G: 位数、原始根というワードは浮かんだが解けず。原始根を求めるアルゴリズムをググって頑張って実装していたが、よく考えれば位数さえ求まれば十分だった。位数が倍数(約数)の関係なら行けるというのは解説を読んで気付いた。だいたい解けたが、位数を高速に求めるアルゴリズムがよく分からなくてACがとれない。
Categories: 未分類