ここ数日苦しめられていたタスクが終わった。
近所で祭りをやっていたので全力で楽しんできた。ものすごい人の群れだった。
子どもの頃、というかだいぶ最近まで、祭りの屋台なんかに行っても心行くまで散財するようなことは出来なかった。小遣いでは限度がある。今はバイトをしているから気兼ねなく好きなものを買える。大学生のバイト代の飛ばし方としては健全なもんだろう。
なんというか、そんな子供じみた欲求不満が自分の中にとぐろを巻いていたことに自分で驚いた。
ケバブやかき氷などを買ったほか、屋台で売っていた工芸品の団扇に一目ぼれして2本も買ってしまった。一人で行ったが、とても楽しかった。複数人で同じ時間を共有するのも良いが、気兼ねすることなくどこにでも歩けるのはとても楽だ。
祭りの屋台というのは良い。一人で来ていても、何の祭りかよく知らなくても、お金を持ってさえいれば祭りの空気に接続できる。開かれたインターフェースだ。
ABC310に出た。
A: min(P, min(D) + Q)
B: 問題文通りに実装する
C: Siと逆順にしたSiのうち辞書順で小さい方を保存することにすればよい。あとはsetに入れて行けばよく、計算時間は(ちゃんと証明したわけではないがたぶん)Sの長さの総和で押さえることができる。
D: DFSした。まだ決まってない人間の集合の中から、一番インデックスの小さい人間を含む形で部分集合を取って次のチームのメンバーとする。チームメンバーの中で相性の悪い組み合わせが存在しなければ残りの人間で同じことをやる。
計算量の見積もりが面倒だったのでえいやで投げたら通った。
E: $f(i, j)=A_i \bar{\land} A_{i+1} \bar{\land} … \bar{\land} A_j$とする。$f(i,j)$を二次元のマス目上にプロットしたとして、ある列にある0と1の数が分かればその右隣の0と1の数も簡単に計算できる。これを使えば$\sum_{1\leq i \leq j \leq k} f(i,j)$をk=1,…,Nについて順々に計算していくことができる。
F: 適切にサイコロを選ぶことによって出目の和として「0を作れる」「1を作れる」…「10を作れる」のそれぞれの状態を持って遷移していけばよい。これはビットパタンとして表現できる。
dp[i][j]:=(i番目までのサイコロを振ったとき、各数値の実現可能性がビットパタンjとして表現できるような出目の組み合わせのパターン数)として計算した。サイコロiを振って出目としてxが出たとき、そのサイコロを選ぶことも選ばないこともできることから(j | (j << x)) & (2^11 – 1)に遷移すればよい。これを$1\leq x \leq A_i$までの全ての出目について計算すると計算量が$\sum A$になってしまうが、x>10については全てjになるのでまとめて計算してしまえる。
出目の和として狙う数字(今回は10)をSとしておくと計算量は$O(N2^SS)$になる。
G: 解けず。なもりグラフなことは分かったが、ある回数操作したときにある高橋君に渡されるボールの数を上手く管理して求める方法が思い浮かばなかった。
解説だとダブリングしていた。なもりグラフの特性を使う解法もやはりあるらしい。
Categories: 未分類