ABC109完走しました
ABC109完走しました。
今回は自分の苦手な計算量圧縮系が出なかったので、相性が良かった。
計算量圧縮系苦手なのは知識面が不足しているからなので、そのうち、ガンガン300-400点問題解く期間作ってもいいかも。
A問題
難しく書いているが、C=1とすればA*Bが偶数か奇数かという問題に落ち着く
B問題
今まで使ったWordを配列にしてかぶっていないかを調べる
前の言葉のお尻と今の言葉の最初がおなじ文字かを調べる
一度でも違ったらフラグ折ってbreak
C問題
Xとx1~xNをsortして差分を配列にする。その配列の最大公約数を求める。
最適を求めるなら配列作らずに都度最大公約数を求めるほうが、メモリ的に優しいはず。
D問題
操作回数の最小を求めなくていいので、奇数なら右か下に移動しまくればよい。
一度だけしか一つの座標に対して操作できないことに注意。
蛇腹型に指定するか、全て右に寄せて右端は下に寄せる(こちらで実装)のがきれいか。
回数最小を求めるにはどうするのだろうか。急に難しくなる。