135B. Rectangle and Square

Codeforces Haskell

概要

2次元平面上の8点を4つずつに分けて、それぞれを正方形、長方形の頂点にできるかどうか
できるならその分け方を答える
8C4通り試す
実行結果を見る限り、両方正方形の場合はどの順で答えてもOK

ソース

https://github.com/mkut/cf/tree/master/01-99/97/135B/haskell.hs

出展

Round #97 Div.1 B
Round #97 Div.2 D

135A. Replacement

Codeforces Haskell

概要

数列の値を1つ変えてソートすることで辞書順最小の数列を作る
一番大きい値を1にすればいいが、絶対に値を変更しなければならないので
全部1の時だけ最後が2になる

ソース

https://github.com/mkut/cf/tree/master/01-99/97/135A/haskell.hs

出展

Round #97 Div.1 A
Round #97 Div.2 C

137D. Palindromes

Codeforces C++ C+++

概要

文字列をk個以下の回文に分割するのに必要な最小の文字の書き換えを求める
分からなかったのでEditorialを読んだ
まずi文字目からj文字目を回文にするコストcnt[i][j]を計算する
初めからi文字をj個に分けた時のコストz[i][j]は
z[i][j] = min { z[k][j-1] + c[k][i-1] } でうまくkで回せばok
500^3なのでC++で解いた

ソース

非常に汚い
https://github.com/mkut/cf/tree/master/01-99/98/137D/c++.cpp(C+++)
https://github.com/mkut/cf/tree/master/01-99/98/137D/main.cpp

出展

Round #98 Div.2 D

137C. History

Codeforces Haskell

概要

区間の包含関係で半順序を作ったとき、極大でない要素の数を求める
境界は気にしなくてよい
片方でソートして順番に極大かどうかを判定する
foldlで普通に書くとTLEしたので、foldl'で正格評価した
ついでに入力もByteStringにした(多分いらないと思う)

ソース

https://github.com/mkut/cf/tree/master/01-99/98/137C/haskell.hs

出展

Round #98 Div.2 C

137B. Permutation

Codeforces Haskell

概要

数列が与えられて、[1..n]の並べ替えに変えるのに必要な数の変更回数を求める
[1..n]の範囲の数が何個あるか数えればよい
変更は+1か-1しか出来ないものだと思って少しハマった
範囲内だけユニークして数えるのが早かったか…

ソース

https://github.com/mkut/cf/tree/master/01-99/98/137B/haskell.hs

出展

Round #98 Div.2 B