C - Align

Quiz

https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

Submission

https://atcoder.jp/contests/tenka1-2018-beginner/submissions/7508948

ジグザグに配置

• editorialに書いてあるとおり、1, 3, 5と置くより1, 5, 3と置いたほうがよく、ジグザグ（上がる下がるを繰り返す）に置くことになる

Nが偶数の場合

• 上記画像の場合、上のラインは足される側、下のラインは引かれる側
• 端点のみ係数が1
• 係数が2のものから数字を割り当てていく
• A = [1, 2, 3, 4, 5, 6]なら、上ラインの係数2の部分に一番大きい値（5, 6）、下ラインの係数2の部分に一番小さい値（1, 2）を置けばよい
• Nが偶数の場合は、係数の対称性より、N型のみ考えればよく、「Nの上下反転型」は考えなくてよい

Nが奇数の場合

• M型とW型がある
• M型の場合
  • 引かれる数の方が多い（A=[1,2,3,4,5]なら1,2,3を引かれる数に割り当てる
  • 端点2つも引かれる数から割り当てる

• W型の場合
  • M型と同様に求める
• M, W型それぞれから値を求め、そのmaxが答え

学び

• ジグザグになる
• 絶対値を外すと係数が出てくる
• 係数を見ながら割り当てる

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

D - Face Produces Unhappiness

Quiz

https://atcoder.jp/contests/abc140/tasks/abc140_d

Submission

https://atcoder.jp/contests/abc140/submissions/7498421

解法

• editorialの別解の方だと楽です（別解じゃない方も通したけど苦労した）。つまり、
• 連続したL, Rは圧縮して1文字にする
• 例：LLRRLL => LRL
• 最大K回flipする(flipとは、LをRに、RをLにすること)
• flipの位置は、圧縮した文字列の奇数番目のみ、または偶数番目のみとする（２パターン試す）
• どちらのパターンでも、処理後に増えた幸せを計測し、maxを取って初期幸せと足せばよい
• 詳しくはコメントを多めに書いたコードを参照（上記）

#ABC 前回のABC-D, 解説読んでも理解に時間かかって、なんでこれ1500人も通せるねんって思ってた。別解の方ならシミュレーションするだけで、これなら1500人も納得 https://t.co/WChJBKmHky

— peroon_cp (@peroon_cp) September 14, 2019

A. You Are Given Two Binary Strings...

Quiz

https://codeforces.com/contest/1202/problem/A

Submit

https://codeforces.com/contest/1202/submission/60410011

解法

• 文字列をs, tとする
• 2^kをかけることは左シフトと同じ
• tを左に滑らせていき、足して反転させたものを辞書順最小にすればいい
• 最後の反転を考えなくていいようにするために、最初からs, tをreverseしておく
• tのleftmost 1 position以降で、sの1にぶつければ、右に繰り上がるので辞書順最小になる

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

D. Shortest Cycle

Quiz

https://codeforces.com/contest/1206/problem/D

• 2000人が解いているので解けなきゃいけない

Submit

なし

解法

• https://codeforces.com/blog/entry/69158
• まず、ビットで考えた時に同じビット位置が１のものが３つ存在したら、サイクルの長さ３で終了

• それ以外の場合、同じビット位置が１のものの数は多くても２
• a=10¹⁸なので、ビットは60桁まで考えれば十分で、エッジの数も60以下となり、グラフはとても小さい
• 以下を考える

• この場合、最小のサイクルは４
• これをどう見つけるかだが、各エッジ edge(u, v) を切ってみて、それでもu-v間にinf以外の最短距離があるか調べる
• 最短距離がある場合
  • サイクルの長さ = 最短距離 + 1
• 最短距離がない(inf)場合
  • そのエッジはサイクルと関係ない
• よって、求めることができました

B - Inscribed Bicycle

Quiz

https://atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_b

Submission

https://atcoder.jp/contests/cf16-exhibition-final-open/submissions/7185546

成果物のライブラリ

// ヘロンの公式（三角形の面積）
double heron(double a, double b, double c){
  double s = (a+b+c)/2;
  double temp = s * (s-a) * (s-b) * (s-c);
  return sqrt(temp);
}

// 内接円の半径
double incircle_radius(double a, double b, double c){
  double S = heron(a, b, c);
  return 2*S/(a+b+c);
}