AtCoder Beginner Contest 124に参加してみました録

　１週間前のABC123に引き続きAtCoder Beginner Contest 124にも参加してみました！！

　この競技プログラミングコンテストは４問出題され、難易度順にA問題、B問題、C問題、D問題とある内の今回はA,B,C問題を答えることができました。

　前回から、とりあえずABCの過去問にあたってみたところ、D問題はまずよく分からなくて、C問題も解けるか解けないか、まあ大体解けないんですけど、みたいな感じでありました。

　して今回の目標はC問題を時間までにどうにか解くという感じなので今回のはいやあ、良かったです。

　とりあえず次の目標はD問題か…あ…むず…できない…ああ、ああ、

　…ということで今回の問題を解いた時の感想をば。

Contents

A問題

　とりあえず入力例出力例を追ってみることにしてみました。まずこんな図を書いて、なんだ(A,Bのうち大きい方)＋(それ-1)じゃないかと思ったんですが、

　A=Bの時だけ（A,Bの大きい方）×2になるということで、その時だけ場合分けしました。

　とりあえずH1の旅館からは必ずSEAが見えるということで、まず出力k=1とかしておいて、あとはHnがH1~Hn-1以上かどうか調べてみて、そうだったらその都度k++;するプログラムを、勘違いとかコンパイルエラーとか無いように（当然これは重要）、頑張って書くという感じでやってみました。

　1と0が隣り合わないようにするということで、結局のところ0から始まる0101010101…という数列か、1から始まる1010101010…という数列のどちらかにするしかありません。じゃあどっちにしたらより少ない変更回数でできるかという問題になります。

　10101010…にするには奇数番目の0を1に、偶数番目の1を0にしなくてはならず、変更回数は

　（奇数番目の0の個数）+(偶数番目の1の個数)

　であり一方、0101010101…にするには奇数番目の1を0に、偶数番目の0を1にしなくてはならないので変更回数は

　(奇数番目の1の個数)+(偶数番目の0の個数)

　ということになります。よって上の2つの式のうち小さい方が答えという気がしたのでそうしてみました。

　今回はC問題まで解けた所で時間がまだあったのでD問題も考えてみたのですが、まず０と１の連続する個数を記録する配列を作っていろいろ場合分けしたらまあできなくはないんじゃないかと思ったんですが、残念ながら文字列の扱いが難しくまずその配列が作れずという感じでした。うーむ勉強しないと…ああ…。

　とりあえずC問題と戦えるようにはなったので、次はD問題もちょくちょく触っていけたら…難しい…ああ…と思います。

　なんか難しい問題の典型パターンみたいな技を全然しらないこと、まだプログラムを書きなれてない感じもあるのでまだ上達する余地はあるかなーということで頑張れたらいいなと思います。

今回のレート変化 : 17 → 98

AtCoderの筆者マイページ: