700点3つ
D. All Your Paths are Different Lengths
問題：頂点１からｎが有向グラフでトポロジカルに並んでいて、１からｎのパスがL個あり長さが０～L-1であるものを構築せよ。ただし頂点数２０以下辺の数６０以下とする。二重辺を許す。
L<=１０＾６
考察：
１０＾６が２＾２０以下なことからbitをそれぞれの頂点間で表せばよさそうです。
桁DPみたく考えます。
２進数表記で10010000みたいなLがあったとします。
１番上の桁を０とすると残りの桁は自由になります。
したがってある頂点間に２＾kと０の枝を張っていきます
一番上の桁１で４番目の桁までを０とすると残りは自由です。
５番目の頂点に向けて２＾（一番上の位）の辺を張ります。
こうすることでどこから任意の桁以下を自由にできます。
あとはガチャガチャすれば通ります
D. Worst Case
問題：１からinfまでの順位が２種類ある。最終的な順位は掛け算して小さい順にします。Ai、Bi位を取った参加者より小さい順位の参加者は最大で何人いるか。
考察：
a,b位をとったとして、a*b=cとします。
2種類のコンテストで対称なので1つをx＜yとして考えあとで2倍します。
x＝１，２・・・としていくと、c^0.5通りあります。c^0.5*(c^0.5+1)＞=cのときー1します。
a<bとすると、必ずa<c^0.5より1組減ります。
以上からO(1)で求まります。
E. 高橋君とホテル / Tak and Hotels
問題：ホテルがそれぞれxi座標にｎ個ある。あるホテルからL以内のホテルまで、1日で移動できる。Q個のクエリ、ホテルaからホテルbまで移動する最小日数を求めよ
考察：
これです。
まずクエリはa<bとできます。
それぞれのホテルから一番右に行ける場所を前計算します。
このパスをaからｂ以上になるまでたどれば最小日数になります。
これはO(NQ)ですが、1回計算したパスの終着点と長さを記録しておきます。
b昇順でクエリを処理すればO(N+M)になります。
クエリ先読みなんですが、idx:加工クエリと加工クエリ：解の2つのmapをもって、重複に気を付けましょう。もっといいやり方知りたい。
C - Ants on a Circle
700点問題2問目も解説ACでした…
蟻本の由来になったとか？
典型なんでしょうか。全くわからなかったです。
問題：周の長さLの円にN匹の蟻がいる。蟻は単位時間に１進み、時計回り化反時計回りか最初に決まっている。蟻同士が出会うと２匹とも反転して進む向きを変える。時間Tが立った後それぞれの蟻はどこにいるか
解説：
まず弾性衝突と呼ぶらしいです。
確かに物質見ればそうですね。
弾性衝突では、お互いが入れ替わるとして考えてよいらしいので、N匹の蟻の位置はわかります。
このままではどの蟻がはじめどの番号だったかわかりません。
蟻の番号は入れ替わらないので、1~nの昇順で並んでいます。
ぶつかったとき、時計回りの蟻は番号が1増えて、反時計回りの蟻は番号が1減るとすればよいです。
1匹について愚直にシミュレートすると、1匹の位置からすべての蟻の番号が定まり解けました。
もし同じ座標に2匹いる状態なら、時計回りのほうが小さい番号、反時計回りのほうが大きい番号になるのでそうしましょう。
感想：
まず弾性衝突でのコツを知りませんでした。
そして、番号を求めるところでは結果だけ注目するという感じでしょうか。
弾性衝突ということを知ったあとは自力で解きたかったですね。
ぶつかる回数で番号の遷移がわかること、O(1)でぶつかる回数がわかることがポイントでした。
考察厳しいです。同じような考察できるようになる気がしません。
実装もまあまあ重めだったのでそのうちやり直そうと思います
Educational Codeforces Round 66 (Rated for Div. 2)
ばｔｙ６あ
A. From Hero to Zero
問題：1を引く、kで割るを何回すればnを0にできるか求めよ
考察：
nが非常に大きいので、n%kを使い前者の操作を効率よくやります
3分でした。よい
B. Catch Overflow!
問題：3つの命令が与えられる。初期値0から最後にいくつになるか
命令：for 数字 endまでを数字の回数繰り返す
add 1を足す
end 直近のforの終了地点
実装：
forを与えられたとき再帰しました。
for以下の＋を回数分かけて今の値に足します。
オーバーフローに注意しましょう
C. Electrification
問題：n個の整数とkが与えられる。ある整数xについて、|ai-x|がｎ個あり、昇順に並べたとき、k+1番目をfk(x)とする。最小化せよ
考察：
x-fk(x)~x+fk(x)にk+1個の値があればよいです。
したがってai~ai+kが区間になり、この中央値がxになります。
n-k通り探索すれば間に合います。
はじめ二分探索を考えたのもあって時間かかっちゃいました。ちょっと反省
D. Array Splitting
問題：n個の整数と整数kが与えられる。k個の連続する部分列に分割する。aiがj番目の部分列にあるとき、コストはai*jである。コストの和を最大化せよ
考察：
出ました、コストを最大化するよくわからない問題。普通最小化だと思います。
全てのaiについて1回はコストに寄与します。
2個目以降の部分列では2回以上寄与します。
このように考えていくと、後ろから見たときの累積和をk個足す問題になります。
これを最大化すればよいので、n個列挙して、ソートすればよいです。
7分くらいでした。結構はやかったとおもいます。うれしいね
E. Minimal Segment Cover
問題：区間がｎ個与えられる。ｍ個のクエリに答えよ
考察：マージして二分探索しましたが、嘘でした
解説：
座標がある程度小さめなので全探索から考えます。
ある座標より左側からスタートしたとき、一番右にいける1つの区間を見つけます。
xからスタートして、この移動を何回繰り返せばy以上になるかがクエリの回答です。
移動をする際に、動いた点ごとに、終着点と距離を記録しておきます。
これによって最大でも座標分しか調べないため間に合います。
移動不可能なときとかの実装が甘かったので、今度通します。
F. The Number of Subpermutations
問題：ｎ個の整数列の連続する部分列で、１～長さが1回ずつ含まれるものはいくつあるか。
考察：１を起点に左右に考えましたが、どちらからも要素を取るパターンに対応できなくて破滅しました。
そのうち解説読んで通します。
感想
早解きがうまくいって、200位台と良い順位が出せました。
リサブがなかったのもよかったですね。
その一方でEFが考察すらうまくいかなかったのはよくなかったです。
Eは解説読んでも実装に苦労しているので、2000点の壁を感じます。
がんばろー
Codeforces Round #563 (Div. 2)
バチャ。
３０分３完で２２００位でした…低い…
D通さないといけない回だったんですかね。リサブで減点されたことを加味しても悲しい順位でした。
A. Ehab Fails to Be Thanos
全ての要素が一致するときだけ-1で、他は構築可能です。
簡単な例としてソートした状態があげられます
B. Ehab Is an Odd Person
問題：ai+ajが奇数のときswap可能である。辞書順最小にせよ
考察：
もし偶数と奇数どちらもあれば自由にソートできます。
そうでなければ1回もswapできません。
前者であればソートして、後者であればそのまま出力すればよいです
なぜ自由にソートできるかというと、偶数同士A,Bをswapするとき、ある奇数とABAの順でswapすればよいからです。
ここで2ペナ踏んだのが痛かったです。いやでもこれ普通に難しくないですか？
C. Ehab and a Special Coloring Problem
問題：a2~anについてi,jが互いに素ならai!=ajであるような数列で、max(ai)が最小なものを構築せよ
考察：
まず問題文がわかりづらいです。互いに素である組では共通の素因数を持ちません。
この組は2~nの素数の種類と同じだけになります。
2~nを素数判定したらTLEしました（O(N√N)）。2~nで未探索ならnを超えるまで倍数を探索していけばよいです。高々O(NlogN)です。
D. Ehab and the Expected XOR Problem
問題：1~2^nを使って、連続する部分列のXORが0かxにならないような整数列を構築せよ。
全くわからん
解説：
まずできあがった整数列Aの前からの累積XORの列Bを考えます。
部分列のXOR：bi^bj(i!=j)
となります。
したがってbはdistinctである必要があります。
またすでに出たbiについてbi^xも使えません。2^n未満の正の整数について貪欲に追加すればよいです。
ai=bi^bi-1などで答えが求まります
感想：
天才か。累積をとるのは典型なんですけど、構築に使えるとは思いませんでした。
部分列＝累積を2つfしたものっていう考えは常に出せるようにしたいです。
E. Ehab and the Expected GCD Problem
問題：nの順列を考える。前から1つずつgcdをとったものn個のうち、distinctな種類を最大化する順列の個数を求めよ
考察：
最大化するケースを考えてみます。
2^k、2^k-1と順に減る場合が最大になります
ここで2^k-1*3がn以下なら3を含む場合があります。
以下のようなDPを用います
DP[i][j][l]：
i番目まで定まったとき、2^(k-j)までgcdが減っていて、l：gcdが3の倍数かどうかを表します。
このDPをするにあたって、2^iの倍数かつ2^i+1の倍数でないようなn以下の整数の個数をそれぞれ求めます。
またその中で3の倍数である個数も求めておきます
遷移は以下の通りです。
DP[i+1][j][0]=DP[i][j][0]*(2^(k-j)の倍数で使ってないもの)+DP[i][j][1]*(2^(k-j)の倍数で3の倍数でないもの)
DP[i+1][j+1][0]=DP[i][j][0]*(2^(k-j-1)の倍数)
DP[i+1][j+1][1]=DP[i][j][1]*(2^(k-j-1)の倍数かつ3の倍数)
初期値はDP[0][0][0]=1、DP[0][1][1]=1or0です。
この遷移をしてDP[n][k]を求めればよいです
実装してないです。こんな適当な遷移考察じゃ無理です。頭こんがらがったのでやめました。
D - Small Multiple
700点埋めそうそう解説AC…
典型っぽいので慣れたい（むずくない？）
問題：Kの正の倍数の10進法の桁和で最小のものを求めよ
考察：
桁DPで150桁くらいまで雑にやったけどダメでした。
mod Kだろうなって感じはしたんですけど、うーーん
解説：
グラフ問題に帰着
操作を分解する
１：1を足す
２：10をかける
1の位9の後に1を足す前に、10をかけて到達しているらしい（ほんとか？）
この2つに分解できたらあとは割と楽です。
k個の頂点、2k個の辺で1からの最短距離を求めます。
2~9は１の操作で到達するので初期化しなくてよいです。
感想：
一見算数の問題でも、DPかグラフに帰着って典型っぽいですね。
前も見た気がする。今回は制約が大きそうなのでグラフなんですかね。判断が難しいです。
1桁ずつ処理することはわかるので、それを分解したときにグラフに見えるかは割とひらめきゲーな気がしました。たくさん問題やって経験値つみたいですね、
Codeforces Round #580 (Div. 1)
初のdiv1が0完でしたが…
A. Almost Equal
問題：2n個の整数の順列が環状に並んでいる。n個の連続する要素の和2n個の、任意の2つの要素の差が最大でも1になるような順列を求めよ
3個だと思ってました（なぜ）
解説：
コンテスト終わった後に考え直しました
i個目とi+n個目の要素の差が1になります。
したがって、2*i+1、2*i+2を対角におきます。
和はそれぞれ偶数だけ足したものと奇数だけ足したものができてしまいます。
基本2*i+1として、ｎ個の対角ペアのどちらかに１足すことにします。
どこをとっても平均的になる必要があるので交互にしてみます。
そうするとnが偶数のとき2*n個目と1個目どちらも+1され、n個目とn+1個目がそのままになります。
差が2になってしまうので構築不可能です
奇数のときのみ上のように構築して出力しましょう
感想：
いやむずすぎ
1300点ってマジ？普通にわからなかったです。
B. Shortest Cycle
問題：ｎ個の整数が与えられる。各整数を頂点として、任意の2つについて論理和が1以上なら辺を与えるとする。最短の閉路を求めよ
ついてあで答えを見て実装したので書きます
各bitで見ます。そのbitが1である任意の2つの整数で辺があります。
つまり、同じbitで3つの整数が1であるなら、長さの3の閉路があります。
これに当てはまらないことを考えます。
制約から高々60bit程度で、各bit1整数は2つ以下なので、頂点120、辺60以下に抑えられます。これは全探索で十分間に合います。
ここからバグ祭り
１：TLE
このままだとなぜか間に合いません。
6*10^6って1secで間に合わないんですね。
nが120以上なら必ずどこかのbitで3つ以上になります。
判定する必要がないです
２：
上の頂点数に0を含めない。
0はこの問題で全く意味ない存在です。入力時点で数えて取り除くべきでした。
３：
二重辺を許さないので辺をsetで記録してまとめないといけないです。
これは提出前に気づくべきでした。
Bは1900らしいです。ま？
C以降は気が向いたらやります。
インタラクティブなのでC避けてDは普通にわからなかったです。
2500と2800なのでまあ無理かなって感じです。
感想
かなしい。Div1Ratedについて実力不足だとは思ってましたが、もうちょっと戦いたかったなって感じです。
まあ実力不足なので仕方ないやって気持ちのほうが強いですね
明後日のDiv2で挽回したいところ
D - 数列 XOR
https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_d
解説ACです。うーん難しい
問題：ｎ個の整数列Aに操作を好きなだけしてBと一致させたい。可能か。
操作：隣り合う2つの片方に、もう一方をXORする
解説：
ある2要素を入れ替える。
足すことができる。
この2つのことから整数列をbitごとの行列にしてRankを求めて一致するか確かめればよい。
掃き出し法：
n個の要素について、1があるところを軸にする。（一番上のbitにしたけどどこでもよさそう）
同じbitに1があるほかの要素すべてにXORする（引く操作）
最後にソートすると整う。
足す操作でいいのかーと思いました。
結構非自明な感じがします。
bitごとの行列に帰着は典型っぽく見えますけど、類題とかあるんですかね。
なれるの厳しそうですね。
