2020/4/9

Codeforces 1333 B

可能不可能

足す先は右の項だけ→右から決定していけばよい(先に変えても影響がないので)

aの要素は-1,0,1→下げるなら-1、上げるなら+1が左にあればよい

 

Codeforces 1333 C

区間和が見たい→累積和で考える

 

Codeforces 1333 D

操作列の構築

最小操作回数、最大操作回数はシミュレートで簡単にわかる

残りの操作回数に応じて操作を調節していくのは大変

→操作回数が最小になる場合の操作列を作り、適宜操作をずらしていく

 

 

Codeforces 1333 F

集合構築

使える数[1,N]と集合の要素数が決まっているとき、集合に含まれるある二要素のgcdの最大値を最小化したい

最初は素数を入れていけばよい、ここから合成数の要素を増やしつつgcdの最大値をなるべく少しずつ増やしていく

素数は全て入っているので、ある合成数xを新たに集合に入れたとき、gcdの最大値はxの(自身を除く)最大の約数となる

→結局自身を除く最大の約数が小さい順に集合に追加していけばよい

 

各整数に対して毎回約数列挙をしていた(は?)

あらかじめエラトステネスの篩と同様に最大の約数を前計算しておけばよい

 

 

AOJ 2386

グラフ構築

無向完全グラフの各辺をどのように向き付けしても、全ての頂点を通るパスが存在する

帰納法で示せる)

ハミルトンパス...全ての頂点を一度だけ通るようなパス

トーナメントグラフ...無向完全グラフの各辺を向き付けしたグラフ

 

 

Codeforces 1213 F

数列構築(可能不可能)

p,qのどちらかは1,2,3,4...として考えても一般性を失わない

アルファベットを便宜上整数として考える

このとき数列を1,2,3,4...とするとpに関する条件は満たす(必要条件から考える)、ここからqの順に数列の要素を見ていったときにも数列の要素が単調になるように、数列を書き換えていく

→qの順に要素を見て得られる数列をいくつかの区間に区切り、左の区間から順に、その区間の要素を全て区間番号(左の区間から順に1,2,3...)に書き換えるとき、qに関する条件は満たされる

→書き換えによってpの条件が崩れないような区切り方を見つければよい

→qの順に数列を見て、次に区切る位置を探すとき、今まで区切った区間に含まれていない数の最小値をmnとすると、最後に区切った位置より後に、"mn<=i<=x をみたすiが全て現れるようなx"が存在するタイミングで区切る必要がある

→この条件を満たすように前から貪欲に区切っていけばよい