yukicoder161-170

yukicoder161 制限ジャンケン

マッチングを貼ってもいいが、先読みできるので貪欲に点数を獲得していけば良い。対応する手が出せるならば出すことを決めておけば良い。
勝ち、引き分け、負けの順番で確定させていく。
計算量:$O(|S|)$
Submission

yukicoder162 8020運動

思考停止メモ化再帰を書こうとすると遷移が$2^{14}$ぐらいある気がしてくる。
上下の歯が独立しているように、歯も一度抜けてしまうとそこを境界に独立する。これを活かして、
$dp[i][tooth]:=$あと$i$年あるときに$tooth$本歯が残っている期待値　として求めれば計算量が軽くなる。
遷移の数は部分集合以下の集合しか無いので、これは二項定理の母関数から$3^N$でも解ける。
計算量:$O(Year*Tooth^2*2^{Tooth})$ $(Tooth<=14)$
Submission

yukicoder163 cAPSlOCK

tolowerとかtoupperがあるのでこれを使う。解説の$xor 32$は賢い。
計算量:$O(|S|)$
Submission

yukicoder164 ちっちゃくないよ！！

独立して計算していいので、一番大きい数よりも大きい基数を全探索する。
計算量:$O(N)$
Submission

yukicoder165 四角で囲え！

4点決めてしまえば四角形を全探索できる。3つ決めても二次元累積和をとっておけば四角形を作ることができる。
x,yのどちらかの範囲を決めるとする。そうすると決めてない方向に関して、一次元のしゃくとり法が適用できる。
計算量:$O(N^3)$
Submission

yukicoder166 マス埋めゲーム

modKとするとずれるのでそこだけ調整する。
計算量:$O(1)$
Submission

yukicoder167 $N^M mod 10$

$N$の下一桁について場合分けをする。$M$についてmod4で周期を持つので、これを埋め込む。
あるいはmod4をとった後にpowする。
計算量:$O(1)$
Submission

yukicoder168 ものさし

とにかく大きいものさしがあればつなぐことができる。よって繋げられる中で短いものさしを求めればいいことになる。
これは二分探索でできる。連結になるかの判定はUnionFindで適当にできる。$O(NlogN)$でもできる。
計算量:$O(N^2logX)$
Submission

yukicoder169 何分かかるの！？

$\displaystyle{Ans*(1- \frac{K}{100}) = S}$を変形する。
計算量:$O(1)$
Submission

yukicoder170 スワップ文字列(Easy)

next_permutationで全部列挙した。
計算量:$O(|S|!log|S|)$
Submission