いつもAVRマイコンに書き込むためにArduinoISPを使っているのだが、いちいちArduinoを持ち出すのもばからしいので、ちゃんと専用のAVRライタを作ることにした。中身はArduinoISP。

コンパクトで取り回しやすくてPC繋いだら即ライタとして使えるような感じにする。AVRの開発効率を高めたい。

---

ARC157に出た。ここ最近連続でなかなかに調子いい結果を叩き出しているのでとても機嫌が良い。

A: XとYで出来た文字列をランレングス圧縮することを考えると分かりやすい。まず、XYなる部分とYXなる部分の数の差は1以下であることが分かる。これを満たさなければNoとしてよい。

XYとYXの数がいずれも0の場合、切り替わることがないので全てXか全てYのいずれかとなる。XXとYY両方が1以上ならばNo。

以上のいずれの条件にも当てはまらない場合、必ず構成することが出来る。

B: 必ずK個選ばなければならないのがミソ。出来るだけYを増やしたいがXも選ばなければならない場合がある。

Xの数がK以上の場合、全てXを選べばよい。問題はどのXを選ぶか。

もし連続したXを全て選んだ場合、両側がYで挟まれていれば、連続したXの数+1だけYの隣接箇所が増える。つまり連続したXの区間はなるべく多く選択したいので、短いXの区間から貪欲に選ぶのが最適になる。両端に連続したXの区間があった場合、これは両側がYで挟まれていないので最後に選ぶ。

KよりもXの数が多い場合、どうしてもYも選ばなければならない。まず、Yを出来るだけ増やしたいのでXは全て選ぶ。残った数でどのYを選ぶかが問題になる。

同じ数のYを選ぶ場合、繋がっていないほどYの隣接箇所の数が減るので、なるべく連続してYを選ばなければならない。そのためなるべく連続したYの区間から選んでいく。両端に連続したYの区間がある場合、これは両側がXで挟まれていないので端から選べば選んだ数しかYの隣接箇所が減らない。なので最初に選ぶ。要はXを選んだ時と逆の優先順位でYを選んでいく。

ちゃんと考察を進めれば基本的な方針はそこまで難しくなかったが実装が面倒くさく、ミスで2WAした。ややこしい問題なので2WAくらいは仕方なかった気もするが、結構見直しに時間をかけたのに単純な符号間違いとかbreak忘れとかしていたのでもうちょっと手早く正確に解きたかったと思う。

C: 「2乗」の総和というのが度し難いと思ったが、ちゃんと考えたらなかなかスマートに解けた。

あるマスに至る経路が$p_1,p_2,p_3,…$とあり、それぞれにおけるYの隣接箇所の数を$y_1,y_2,y_3,…$とすると、あるマスに至るまでのスコアは$y_1^2+y_2^2+y_3^2+…$となる。そこからYの隣接箇所の数が1個増えた場合、$(y_1+1)^2+(y_2+1)^2+(y_3+1)^2+…$となる。これは$y_1^2+y2^2+…+2(y_1+y_2+…)+1+1+…$と変形できるので、2乗の総和と1乗の総和をそれぞれ持っておけば遷移できることが分かる。いわゆる積の和典型というやつである。

前にちらっとその存在を知って「こんなの使いこなせるのか…？」みたいに思っていた積の和典型がスッと出せたのでとても気持ち良かった！基本的な考えはとても単純なので、式の導出を正確に行えれば十分使える。自信が付いた。

D: 本番中全く歯が立たず。解説を読んだらなかなかに唸らされた。bit全探索の改良を出発点にいい感じの動的計画法が出来ないかと考えていたが、もっと大局的な見方をする解法だった。この見た目から約数全探索をするとかいう発想は自分の引き出しにはない。なかった。

グラフを与えられたときにすぐBFSやDFSに飛びつくんじゃなくて次数に注目してみるとか、そういう感じの「全体で保存される性質に注目する」思考にもっと慣れる必要がある。グラフについては気を付けていたが、こういう感じでマス目問題でも問われるんだな。慣れていれば解けていたか、少なくとも齧り付けていたかもしれない。

橙パフォを未だに取ったことがないので、ここらでいっぺん取りたい気持ちがある。