20190502-20190514のatcoder埋め

たまにやってます。

abc104

  • a - 1:00でAC。
  • b - 4:50でAC。

abc105

  • a - 0:50でAC。
  • b - 4:50でAC。

abc106

  • a - AC。
  • b - AC。
  • c - AC。
  • d - 解説を見ながら40分くらいでAC。想定解法をpythonで実装するとTLEになったので、二次元累積和を使う方法でやったら通った。二次元累積和について前に勉強してたはずなのにとっさに出てこなくて悲しみ。

abc107

  • a - AC。
  • b - AC。意外とめんどくさかった。
  • c - AC。最初DPかと思って考えてたけどよくわからなくて、冷静に考えたら取るK本は必ず連続するということに気づいて、連続するK本の組み合わせを全て考えるという方針で解けた。
  • d - 諦め。解説を読んでもよくわからないので一旦おいておく。

abc108

  • a - AC。
  • b - AC。
  • c - AC。方針が立つまでにやや時間がかかった。
  • d - 諦め。一旦おいておく。

abc109

  • a - AC。
  • b - AC。
  • c - AC。問題文を読んで最大公約数でOKっぽいなと思ったらOKだった。最初、３つ以上数値の最大公約数を再帰でやったらREになったのでスタックオーバーフローかなと思ってfor文に書き換えたら通った。
  • d - 解説を見ながらAC。発想力が無。

abc110

  • a - AC。
  • b - AC。若干ややこしかった。
  • c - AC。最初、sとtのあるインデックスの文字が同じだった場合を無視してしまっていたが、これも同じ文字への変換とみなして考慮に入れないといけなかった。

abc111

  • a - AC。
  • b - AC。
  • c - AC。番兵的なやつを追加して処理を簡単にするのがうまくできた。

abc112

  • a - AC。
  • b - AC。
  • c - 解説を見てAC。実装の方針が難しくて、解説を見たにも関わらずかなり手間取ってしまった。
  • d - AC。最初partitionという問題名を見て反射的に分割数の組み合わせを求めようとしてしまったが、冷静に考えて間に合うはずがなかった。よく考えると、単に最大公約数の候補となる整数について、それが実際に最大公約数になりうるか試していくだけでよかった。

abc120

  • a - AC。
  • b - AC。
  • c - AC。なんか難しいことを考えなければいけないのかと思ったら、特にそんなことはなかった。
  • d - AC。問題を見て、橋を落としていくのではなく追加していくほうが簡単そうだなと思えた＆UnionFindを使うことがすぐわかったので成長を感じた。途中謎のREになったので、何度か怪しいところを直していったら無事ACになった。

abc121

  • a - AC。
  • b - AC。
  • c - AC。C問題にしては簡単すぎる。
  • d - 解説を見てAC。解けなかったけど、連続する整数のXORについての性質を勉強できたのでよかった。
    • 任意の整数nについてn ^ (n+1)は1
    • 連続する整数x - yのXORをf(x, y)とすると、自分自身とのXORは０よりf(x, y) = f(0, x-1) ^ f(0, y)