| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
易しいセット。Fは少し時間がかかりましたが、他の問題は基礎技術を問うている印象でした。
6問全部完答したのに、順位はこれまでの中でも悪い方。遅いかぁ。
この日もAtCoderが重い日で、コードテストが動かないストレスでいい加減に投げてREしちゃったりとかありました。
問題A – Changing a Character
pythonでは文字列はimmutableオブジェクトなので、途中の1文字を書き換えたい場合には、
・新しく作る
・リストに変換して1元書き換えて文字列に戻す
などをやる必要があります。
問題C – Dice and Coin
必要回数ごとに範囲を計算して、$O(\log K)$ 解を実装した。
解説PDFは $O(N\log K)$ 解で説明されている。
$\log N$ 解の方が計算量はもちろん優れているけれど、どちらでも制限的に問題はない。バグや計算ミス確率を少しでも抑えて確実に短時間でACをもらうという観点では、敢えて計算量改善をさぼるという考え方も有益ですね。なるほど。
問題D – Even Relation、問題E – 1 or 2
この2問、ほとんど同じ出題に見えます。
問題Eも、$A_i$ と $A_j$ が同じ色であるか逆の色であるかが情報として与えられることと同値ですので。
問われているものが、塗り分けの実例・連結成分の個数とそれぞれ少し異なっているのですが、適当なグラフ上の探索（dfs or bfs）、連結成分の確認（union find treeでもいいし、問題Dが解けているのであれば、dfs / bfsしながら連結成分全体の訪問を何度かやればよい）。
問題F – XOR Matching
$a,b,c,x,c,b,a$ というような並びを使うことで、$x$ 以外の条件が満たせることは数分で気がついた。しかしそこからが進まない。他の方針をいろいろ考えながら、30分くらいして、最初の方針で $x$ も満たせることに気がついた。
