Codeforces Round #601
レート爆上がりでこれは勝ち申したってなりました。
A問題
差の絶対値をとって5ずつ、2ずつ、1ずつとやっていく（+5-1とかは+2+2と手数が同じなので+のみ、-のみで考えて良い）。
B問題
全ての冷蔵庫には2本ずつチェーンが繋がってなければならないのでまずは輪状に冷蔵庫を繋げる。チェーンが足りなければ-1。余ったチェーンはコスト最小のところに全て繋げる。n=2のコーナーケース見逃して1WA。
C問題
pairでmapを作って例えば(1,2,3)だったら1,2に3を登録、2,3に1を登録、1,3に2を登録（pairは小さい方が前になるようにソートしておく）。それと同時に各数が出た回数をカウントしておく。次にカウントが最小（＝１）の数字を探して、カウントが次に小さい（＝２）の数字であってカウント最小の数字とのpairがmapに含まれているものを探す。これを1番目、2番目とするとmapから3番目の数を探せる。あとは登場済みのものを弾きながら2番目、3番目のmapを見て4番目を探す、3番目、4番目から5番目、としていく。バグりまくったので泣きながらやった。
D問題
蛇腹状に領地を分けるとRを任意の個数含んだ分け方にできるので差が0または1が最善。文字コードよくわかんないからググったけどそれでもよくわかんなかったので9ならA、Zならaに移動、それ以外は+1ってした。
E1問題
合計の約数(1以外)ずつの区間に分けて区間内の中央値であるところに持っていく。こういう系中央値なのか平均値なのかで迷いがちなのでこれからはちゃんと覚えます。終了1分前に書き終えてお願いします！って叫びながら提出したらWA出た。見直してみたらintがオーバーフローしてたのでllに直したら普通にACになって辛かった。脳死でllできるAtCoderに甘えちゃダメですね。
Educational Codeforces Round 75
A問題
bool関数で奇数回連続で出た文字はtrueにしていく。もう初心者じゃないので最後i=n-1の処理は忘れない。cout << 'a'+iとかすると数値が出力される仕様を忘れていたのでそこでタイムロスしたが特に問題なし。
B問題
任意の回数スワップできるやつは一度全部取り出してそれから当てはめていくと考えることができるので、文字列の長さ偶奇ごとにカウント、0と1の出た回数の偶奇を管理、いい感じに場合わけでいい感じに答えを出す。
C問題
ここからが地獄の始まりだった。バブルソートの最悪計算量はn^2なのでバブルソートごっこしたら通るわけないのですがそれ以外に何も思い浮かばなかったのでとりあえず書いて出す。TLEじゃなくてWAですって。目も当てられない。ここで順位表を見るとフレンドの強い方々はC、D両方通しているもしくは両方通していない状況で、参加者全体の正答数もそこまで大差ないのでD問題へ進む。
D問題
medianの金額について二分探索、median<rになる範囲について二分探索、priority_queでその範囲内からmedian以上にすれば良いのかを貪欲に選ぶ、という解法を書いたけど実行時エラーが消えない。そもそもこの方法で合ってるのかもわからないし・・・、という状態が続く中、残り40分ほどになったので順位表を再確認。正答がC問題＞＞D問題になってて順位が急落していたので焦ってC問題に戻る。
C問題（再）
戻るとすぐに解法が思い浮かんだ。C問題に戻るという選択は間違っていなかったらしい。偶数のかたまり、奇数のかたまりが繋がっている部分について頭から順に比較をしていき、小さい方を前にすれば良い（説明がしにくいけどマージソートのマージ部分のような感覚）。焦って書いていたせいかコードが100行を超え、さらに制限時間残り20分を切ったがなんとか書き終えた。ここでWA出ても流石にこの残り時間でこの量は間違いを見つけられないと感じ、これを最後の望みだと思いながら提出。ACが出て達成感と脱力感を覚えながらコンテスト終了を待つ。
Codeforces Round #５３３ B. Dima and a Bad XOR
今まで参加したコンテストやイベントのことしか記事にしてなかったのでたまには個人的に面白いと思った問題を記事にしようと思います。
問題概要（自分で和訳したので誤っている可能性あり）
各項が非負整数のn*mの行列aが与えられる。数列c1,c2,...,cnであってa(1,c1) xor a(2,c2) xor ... a(n,cn) > 0となる数列はあるか？なければ”NIE"をあれば出力し、あれば”TAK"、そして数列c1,c2,...,cnを出力せよ。（文字を80％より小さくする方法がわからなかったのでa(i,j)でaのi行j列目を表しています。リンク先の問題本文を読んだ方がわかりやすいかも）
着目点
xorを取って>0、と言っているが非負整数でxorを取ると0より小さくはならないので≠0と言い換えられる。a(1,c1) xor a(2,c2) xor ... a(n,cn)が0になったとするとこのうちの整数を一つ変えるとxorを取った値が0ではなくなる（これはある数xとxorを取って0になる数はx自身以外に存在しないことを考えるとわかりやすい（？））。
解法
まずは数列cを1,1,...1としてxorをとる。これが0でなければそのまま出力。0であって全ての行が単一の整数で構成されている行だったら”NIE"、そうでなければ複数の整数で構成されている行のうち1つをx行目とするとcx=1をa(x,1)≠a(x,cx)となるcxに変更する。
KUPC 2019
オンラインから参加しました。
A問題
ソートして最大-Xの要素を数える。
B問題
200点問題なので簡単ですね（）。まずUnionFindして次に根以外は根に重み、価値を付加して自信の重み、価値を0にする。最後に普通のナップサック。
C問題
今回一番面白かった問題。とりあえず1gのやついっぱい欲しい！と思ったので1gをk個は確定。これでkgまでは測れる。次に2k+1gが欲しい（1gをk個反対側に置けばk+1~測れるので）！となるので2k+1gを用意する。いっぱいあった方がお得感あるのでまたk個用意する。これでk(2k+2)gまでは測れる。・・・、とやっていくと答えが出る。2倍とかkの累乗とかが出てくるので（語彙力不足）時間が足りる。
D問題
とりあえず0が連続している部分と1が連続している部分に分けて考えればいいことがわかる（0と1の境目のところで両者の持っている枚数が等しくなる必要があるので）。次に分け方を例えば1~6をAが勝つように分配するならBBBAAAとかBABBAAとか、Aの数が途中でBを超えない並べ方を数え上げればいいことがわかる（かっこの並べ方みたいに）。ここでよく考えるとカタラン数、という言葉がふと頭の中に浮かび上がったのでググるとまさにこれだということがわかる。OEISより天啓の方が早くて楽なのでオススメですよ。modの逆元めんどくさいけど10^5は流石に埋め込めないのでちゃんと計算する。
E問題結構考えたけどわからなかったので撤退し4完。順位表見た感じまあまあいい結果（その後のこどふぉ爆死したけど）。
AtCoderで水色になるまでにやったこと
9月28日のABCで水色になったのでかなり今更感ありますがAtCoderでは色が変わったら記念ブログを書くことが通例（？）なので水色になるまでのことをまとめようと思います。
はじめに
既に水色になってからもう1コンテストあったので画像の通り現レートは1227になってます。他の方の記事だとこのアルゴリズムは必須だよね、とかこのアルゴリズムはなくてもいけるよね、とかいうのが多いので被らないように僕はアルゴリズム等以外の要素のやったことについてまとめます。
競プロ始めてからの時系列まとめ
プログラミング関連の講義を取る（4月頃：体感パフォ100上昇）
アルゴリズムの授業を取ったのですが深さ優先探索やら幅優先探索やらDPやら競プロでガッツリ使うようなアルゴリズムが多く取り上げられていたのでここで割と強くなりました。競プロ関連の講義は競プロの精進にもなって単位も楽に取れていいですね。
競プロを始める（5月下旬：体感パフォ100上昇）
競技プログラミングを始めました。競プロを始めるとパフォーマンスが上がります。
VSCodeを入れる（7月頃：体感パフォ10上昇）
コード書きかけで別の問題に移る時とか便利です。あと自動補完があったりタブの切り替えが紛らわしくなくなったり背景を好きに変えられるのでモチベが上がったりします。（）
テンプレートを整備する（7月頃：体感パフォ200上昇）
今までは全部インクルードとstd::省略をAtCoder公式のチュートリアルページからコピペしていましたがせっかくVSCodeを入れたのでテンプレートを作りました。
intのINFはmodで代用しています。dx[4]とdy[4]は使ったことないですがそれ以外は全てかなりの頻度で使ってます。
オンサイトに行く（9月中旬：体感パフォ300上昇）
強い人に会ってモチベが上がりました。あと思考が詰まった時みんなどうしてるのかとかちょっと観察して参考にしました。
ツイッターで競プロerをフォローする（オンサイト後：体感パフォ100上昇）
オンサイトに行った時にお会いした人をフォローして、せっかくなので競プロerを大勢フォローしたら入ってくる情報量もライバルの人数も格段に増えました。ツイッターは偉大ですね。
ペイントツール考察を始める（オンサイト後：体感パフォ100上昇）
これより前は脳内考察だったのですがオンサイトで隣の方が紙考察してたので試しにペイントツールで考察してみたら法則見つけやすくなって良かったです。紙ではなくペイントツールを使ったのはレイヤー分け、色分けができるというメリットがあったからですがどちらも全く使いませんでした。
蟻本を買う（9月末：体感パフォ300上昇）
AtCoderやってる人々から推されているバイブルです。このとき既に水色になっていますが細かいことは気にしない。
CodeForceを始める（9月末：体感パフォ100上昇）
AtCoderで適切な難易度の問題が少なくなってきたので始めました。AtCoderであんだけ苦労した水色に一瞬でなれたので複雑な気持ちになりましたがAtCoderとは問題傾向やシステムがちょっと違うので守備範囲が広がった気がします。もうすぐCodeForceで青色になるまでにやったこと、の記事を書けるような気がします。
ライブラリを整備する（10月〜：体感パフォ100上昇）
せっかく蟻本を買ったのでry。
紙考察を始める（この前：体感パフォ300上昇）
マウスのついていないノーパソでお絵かき考察するよりも紙の方が描きやすかったです。
これからの目標
青色になりてぇ。
AtCoder Grand Contest 039
A問題
絶対に許さない。
B問題
紙にテストケース3つ全てを書いて考察。どうやら長さ奇数の閉路があるとダメ、それ以外なら可能、らしい。最大のkは元のグラフの端から端までの長さだな、と思ったのでとりあえず先述の可能かどうかの条件は置いといて（この時点では適当な点からBFSして既に深さが書き込まれている所に新しく深さが上書きされるようなシチュエーションがあったらダメ、とかで考えていたがめんどくさいので後回しにした）、ワーシャルフロイドで全点間距離を求める。ワーシャルフロイド書き終わった時点である点AからB,Cへの距離が同じで、B,Cに辺が張られていると奇数の閉路になることに気づいたのでそれを奇数閉路検出に使った。
第一回日本最強プログラマー学生選手権参加記
予選落ちなのでセミナーから参加しました。
予選
A問題
正直あまり印象に残っていませんでしたがコード見た感じ全探索です。
B問題
天才なので数列Aの内部にある転倒数とAを並べた際にできる転倒数を分けて数えて、最後に足し合わせれば良いとわかる。転倒数を数える方法をググるとバブルソートすればいいことがわかる。ネット上のソース見ながらバブルソートを実装する。WAする。完。
コンテスト後によく見てみるとバブルソート部分が厳密なバブルソートではない（隣接項ではなくても交換できる）コードになっていたので、うまくいかなかった。1完の2333位でAt Coder初参加回を含めてもパフォーマンスが自己ワースト1位となった。本戦は無理でも懇親会参加したかったので絶望して泣いた。招待メール来て本当に良かった。
決勝戦当日
セミナー
電通のグループ企業（？）の方が講演してくださった。これが45分続くのかあとため息をついていたら丁度いいくらいの長さだったので良かった。内容は電通がどんなことしてるのかとかプログラミングがどう企業で役立ってるのかとか知れて面白かった。
表彰式
聞いたことある名前ばかりが呼ばれていてすげえ（語彙力皆無）ってなった。
休憩時間
交流が始まる気配がなかったので蟻本を購入するか検討していたので近くの本屋にいってざっと立ち読み。購入を決意するもお金が足りなかったので店を出る（今日買った）。現場がどうなってるか知りたくてツイッターをみるとすでに交流が始まっているっぽかったので急いで戻る。
名札とか見ながら知ってる人探してたらゆるふわオンサイトで話した方がいたので会話する。色々話した後でchokudaiさんのハンドスプリングを見ていないことに気づき、ロビー的なところに戻る。ハンドスプリングはしてなかったが、紙芝居のおじさんみたいにchokudaiさんが真ん中で喋ってて周りで人々が聞いていたので混じる。At Coderのレートが最近きつくなってきてる理由とか色々聞けた（ハンドスプリングは結局終了後にツイッターで見た）。その後ツイッターアカウントの教え合いみたいなのが始まったのでツイッターを交換していると会場に入れるようになる。
懇親会
ツイッターのFFがいたので喋った。飯解禁された瞬間寿司に向かったけど寿司早解き勢が強すぎて遅れをとったので並んでいると隣にyosupoさんがいたのでレート差のあまり気絶した。決勝進出者と同じ飯食べてるの申し訳ねぇと思いながら胃ナップザックをしていくと胃の容量を超えてしまったのでうずくまった。終了間際に会場隅でうずくまってる人いたら僕です。
その他
今週末はこれ以外にも水色になったりこどふぉ初参加したりイベント過多だったのでそれについても後日書きたいです。
