CODE FESTIVAL 予選B

競技プログラミング

解いた。

 

問題A、B：やるだけ

 

問題C：

解説を見て、取り出せる範囲の境界を知って実装した。本番では、文字サイズ/2がmax(0, C3-C2)以上、min(C1, C3)以下の範囲にあるときに取り出せるということに気づけなかった。

 

 

 

問題D：

解説のうち、DP解を実装した。解説では端っこに無限大の高さのものを考えるいいと書いてあるが、whileの条件で必要以上に外にいかないようにすることで代替できた。

 

CODE FESTIVAL 予選B 解説

ARC28とSRM631

競技プログラミング ARC Topcoder

* ARC28 ○---
詳しくは以下。


AtCoder Regular Contest 028 解説
- A:
シミュレーション

- B:
priority_queue、pairの使い方が参考になる。


- C:
木構造。制約から、循環はしないことが保証されてる。（あるノードは自分より小さいものにしかエッジを張らない）
木をたどっていくdfsの書き方とか参考になる。
Submission #223649 - AtCoder Regular Contest 028 | AtCoder

- D:
よくわかってない。

*SRM631 Div2 ○--
- A:
N×Nの文字列が与えられて、WかBで埋まってる。列を見て、同じ文字が連続している数を数えて、もっとも長く連続している数を答える。

境界とか気をつけて数えるだけ。

- B:
時間tが経過した後、１つの場所にせいぜい1匹までしか猫がいられない。猫は初期場所とその場所に何匹いるかと時間が与えられて、各猫は時間ごとに左右1マスどちらかに動くか、その場にとどまるか選択できる。

どうやって1匹のみという状態があるのかを調べるかわからなかった。
→範囲小さいし、全探索ぽい。
→どう全探索する？

解法：
全探索ではなくて、貪欲。
<s>Impossibleなパターンが限られるぽい。</s>
>|cpp|
vector<pair<long long, long long>> p;
||<
とかにpositionとcountを入れて、猫のポジションを小さい順に並べる。
左から詰めて並べるようなイメージ。可能な限り左から並べる（直前の猫が並んでるところの右端か、いま見てるポジションで猫が最大限左まで行ける場所のうち、より右にあるほうから並べる）。かぶり発生したら、Impossible。最後までImpossibleにならなければ、Possible。


- C:
2^Kの価値のコインを２枚ずつ所持してて、それを用いてNを表す方法のパターン数を答える。

解いていない。

暇な時に確認する。

暗号化データ自体に情報を埋め込むモチベーションとは

メモ 暗号技術

特に参考文献を上げることもないメモ書きなので、ご容赦。

 

近年、暗号化したデータに対して情報を埋め込むというのが流行っている。ABE、IBEなどがそれである。これまで、わざわざ暗号文（や署名）自体に情報を埋め込まなくとも、そことは別でやるほうが実用的だと思っており*1、ABEなどの分野に手を出しても、効率性で実用的にならなければ（なったとしても）、一瞬で消えてしまう可能性のある分野だと思っていた。

 

しかし、まずは実用の話を考える以上に、考えられる選択肢が増える事自体歓迎すべきだし、Noarの放送用暗号など、情報の埋め込みを前提にした方式がかなり進んでいる*2ことを考えると、暗号化データ自体に情報を埋め込むモチベーションを理解できなくもない。

*1:今思えばこの考えは証拠不十分。実際近年の暗号界隈ではPairingの登場により効率性を改善できているものが多い。

*2:これだけで信用はできないが、長年の批判に耐えていることはある程度の評価はできる