ABC 017
http://abc017.contest.atcoder.jp/
330/401の42/338位
いままでで最高順位ktkrうれちい！
A 100/100
先に掛け算すればいいお膳立て付き
http://abc017.contest.atcoder.jp/submissions/318701
B 100/100
パターン1 o,k,u
パターン2 ch
の2パターンでいろいろ考える
他にもっと難しい問題が山ほどあるから難しいってことはないけど，ABCにしてはちょっとややこしい気もした
http://abc017.contest.atcoder.jp/submissions/318919
C 100/101
101は無理ゲーだった．どうやら発想の問題らしい．
通らない区間を1個定めて他をかき集めるって方法で100点までのテストケースは通った
実装的には全列挙よりすごい楽だった
http://abc017.contest.atcoder.jp/submissions/319375
D 30/100
要素が重複しないところまで配るDP
念のため番犬を配置しておいたけど必要なかったっぽい
最悪でO(N^2)だから100点行けなかった・３・
http://abc017.contest.atcoder.jp/submissions/319645
部分点で妥協した場合で制約条件を超える値のテストケースについてはさっさと諦めreturnさせないとえげつない計算時間がかかるんで，自分の結果が中々わからないしジャッジ側にも無駄な計算で迷惑かかるし今後気をつけないといけないなーと
lognもバカにならないねというお話
ARC 028 B問題
B: 特別賞 - AtCoder Regular Contest 028 | AtCoder
ぼくのていしゅつしたこおど
http://arc028.contest.atcoder.jp/submissions/316795
この問題の解説は俺の適当で不正確なアレより公式の記事のスライドが素晴らしいので省略（４ページ目から）
AtCoder Regular Contest 028 解説
http://ufcpp.net/study/algorithm/col_heap.html
↑ C#に関してはお馴染みオブお馴染みなこ↑こ↓のサイトの記事を元に自分で優先度付きキューを実装したやつです
何が言いたいかというと，計算量はまったくヒープ型の優先度付きキューと同じってっことだけーーー．
ヒープを使えば，数値の追加や先頭の要素の削除はlognで行えるんで，
k+1からn回目に繰り返しキュー内が更新されるので，この問題だと最終的な計算量はO(klogk)に．なる．
ここからこの記事の本題で，今まで，lognならほぼ1とみなしたって問題ないっしょ!って思ってたけど，
性能を試してたときにこの優先度付きキューでn=1000000あたりからTLEを起こすくらい遅い．辛い．
これがわからないこれがわからないってなってたけど，
log_2(n)で底が2だから log_2(10^7) = だいたい7*3.3 = 20になるんで
n = 10^7 のときのn*lognは一段上がってしまって
n = 10^8のときのnと一緒くらいの重さになってしまう
底が違うから思ってるより重いっていう勉強になりました（小学生並みの感想）
ここまで書いてあれだけど，コレクションとかもろもろの操作で自分の作成した奴のオーバーヘッドがでかすぎるのかもしれない
マカロニダァイスキ
MultiSetの実装方法がわからない，コレクション使い回しでできないかなぁ
初めてARCのC問題を通したゾ！
ARCがBで時間切れ，Cもまぁむり，Dは論外ってレベルだったけど
C問題を初めて通せた＾ｑ＾＾ｑ＾＾ｑ＾ なお70分かかったもよう
問題のURL
http://arc017.contest.atcoder.jp/tasks/arc017_3
ぼくのかいたこおど
http://arc017.contest.atcoder.jp/submissions/316493
2^nがを用いるパターンは nが異様に小さいのがヒントになるね．
二分割でビットDPしてけば2^32/2 = 2^16で通るのも簡単に予想できる．
2^10 ≒ 10^3が目安になるかなーと．
逆に10^9が与えられたらオーダーに含めない形にするか，lognまでオーダー落とせっていう目安が与えられたり．この手のだとO(1)で求められる可能性もある．
New Year Contest 2015
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13題です．
2015を記念して13回書きました．
Bで終わった，しにたい
下にいろいろ書いてるけどまだ実装してません＾ｑ＾
A
うまくANDマスクとかビットシフト使ってforループ回して01文字構成
x = 2 (２進数で10)のときn && x / x で一つのビットが1か0かわかる
7が110じゃなくて011になっても対象かどうかの判定は問題なくできるのでそのへんは気にしなくてよかった
B
ソートして小さいものを敷いていく貪欲法
その時の和をメモっといて次の鏡餅が持つか判断
C
今考えてる．
先頭の文字,と連続する2文字以上のものを抽出してリストを作ればsとｔのやつで完全に等価じゃないとダメ
あと，リストの間の部分文字列にたいして，sの文字順通りにtを構成できるかどうか
のあたりが問題なければsからｔを構成できると踏んでる
計算量も問題ないはずだけど
D
幅優先探索考えてるけど，頂点も辺も無限に膨れ上がるんだよねこれ
無理ゲー感すごい，条件次第で∞まで増幅してくっそ離れたところ（-1000000？）以降を枝刈りしてもよさそうだけどどこまで刈ってもいいかの根拠が見つけられない（区間をうまく定めないと答えが求まらない可能性がでてくる）
メモ化再帰と幅優先探索で最悪O(メモの区間＊クエリ問い合わせ数)になるかなぁとは思う．
他の人の回答を見たところではメモの範囲を-100050～100050でとってたけど，どうやってこの最大容量を見積もったんだろ
E
n人にn-1本のひも
ひも 線？グラフ理論！
一人に対し1~3本つけるってのもミソで，一端2本繋ぐ人を省いて
まず１本,3本付く人で木が構成できる（閉路なし）
構成した木はただ一意に求まる． この1と3，3と３のつながった部分に2人の人を挟み込んでも木の構成は正しいまま
この1,3本の人の最小木に対する場合の数と2本の人の入れ方の場合の数に分割して
人の番号を区別して階乗とかもかけていくと求められるはず
いま k/n mod 1000007 ( k,n ∈N)の対策が考えられてないです．これもなんとかしないと求められない・・・
F以降
まだ問題の解釈ができてないです
Kからはハナから捨て問よぉ！
新年から軽いノイローゼになるくらい難しかった（小並感）
きれそう
code thanks festival A日程の覚書
Fまでいけた（Gでうまく実装できなくてつみ）
Hで100点取る方法は皆目検討つきませぬ＾ｑ＾
部分点は全探索してO(n^5)とかになるんだけど通るはずっしょ
やってないけど
G
うまりを○
空き席だけど隣に人がいるのを●にして
初期状態○●から○○●あるいは○●○●になる
これをみると○+1,●+0 , ○+1,●+1に遷移することがわかる
また，隣に人がいてもいいなら○●○●→○○○●で○-1,●+0とかもある
ここで，6席しかないと仮定して，○●○●○●の場合に隣に人がいるといやなら○+0,●+0
とかもありえる
こういった断片的な遷移をうまく組み合わせて確率を求めてくDPをすればよかったんじゃないかなぁ（できたとはいってない）
答えは，すべての席から○の個数を引くと開いた席の数（●は空席！）になるので，これに確率の重みをつけて総和求めればパパっと終わり
できたとはいってない
ほしいぜ実装力
code thanks festival 2014 B日程の覚書き
本番ではEまでいけた，(F,G,Hはこころがおれた)
でも本来はFも余裕なはず
A Max
B 全探索やるだけ
C やるだけ
D 配列用意してAi , 2Ai, 3Ai,に1プラスして，最大値を求めたら，それが答えになる
E 条件にそって二次元グリッドを塗りつぶしてから，メモ化再帰で
小さいから行ける
F
DP使う．n番目の文字からk文字のSを含んでたらdp[n] ＋= dp[n-k]
r文字のTを含んでたらdp[n] += dp[n-r]
するだけ．なんで諦めたのか謎謎謎クソザコナメクジ
問題文の前から読み込んでいってね！のヒントに気がつけなかった
G
N,Pが大きい状態で始めてしまうと全く検討つかない．NimとかGrundyとか当てはめようとしたのがうんちすぎた
逆に，N,Pが小さいうちなら簡単に判定できる ので D P
自分の手順でN ≦ Pなら明らかに勝ち
N>Pのとき，dp[i,j] = _dp[i-1,2] or _dp[i-2,3] or ... or _dp[i-j,j+1]
_dp[i,j]はdp[i,j]のnot論理値
与えられた入力に対して，相手を負けに落とし込める状態が一つでもあれば勝ち
dpは常に取る側視点で考えるのでnotを取る
H
まだできてない．
ごちゃごちゃしてるけど，先頭と最後尾だけに注目すればいいはず．
AB,BC,CD,EF,FC のとき，ABCDとEFC にしても，ABCFE,とCD にしても
結局追加で結合するための文字がひとついるから，とにかく貪欲法で結合してけばいいんじゃないかなと思ってる．
