209位
突如来襲したオトンと8時半まで仙台駅でお酒を飲んでいました．
全力ダッシュで帰宅して参戦．実はお酒を飲んだ直後に猛ダッシュすると酒が回りまくって半端なく気持ち悪くなることを発見しました．
F, simplified reversi, 見た瞬間beatsを貼りました．ごめんなさい．
BCでペナを吐いたので順位がゴリゴリ落ちて涙を流しましたが，データ構造のおかげで辛勝．
Cが最も難しいです．

ACL Beginner Contest

76位
僕は考察力が皆無な割には割と高度なデータ構造を少しだけ勉強したため，ACL Beginnerコンでトーナメントを戦えることになり，これ以上ない運が僕に巡ってきました．
D, Eともに遅延セグメント木を使い，Fは解けませんでしたが1回戦目と同じ順位である76位を獲得．
F，感動しました．

ABC 180

72位
そろそろABCトーナメントに負けたくなくなってきた頃です．
Eまでに通し，Fがそんなに自明に見えないので一度順位表を確認したところ，この時点で相手の方に数分負けていることを確認して一度死にます．
ですが，手元で思いついた辛そうなDPを丁寧に丁寧に丁寧に1時間こねこねするとなぜか通ります．正直うれしかったです．

ABC 182

151位
バチャを何度かやったことのある方との対戦で，いつも負けていたので，正直もはやこれまで，と思っていました．
Eまで通した時点で負けており，やはりもはやこれまで，と思いつつ泣きながらFを考えます．
正直こういう問題は解けたためしがありません．見るからに考察力が必要そうです．
しかし桁DPを解けばいいことに気付き，またもや怪しそうなDPをガチャガチャしてみると通りました．なんで？

ABC 183

30位
この大一番で競プロ人生の最高順位を出しました．
Fが水diffで，さらに重点的に対策したことのある問題だったので爆速で駆け抜けることができました．
奇跡．

おわりに

自分はABCで勝つためにド典型を対策し続ける精進をしてきたと思っていますので，この結果はそれが形となったような気がしてとてもうれしかったです．
その代わりにAGC, ARCではレートなみの力を全然発揮できないカスであることが最近わかってきたのですが...
この催しがあったおかげで，対戦相手だった方々と，ツイッターでお近づきになれたことが一番うれしかったです．
また対戦することがあったらよろしくお願いします．
これを開催してくださったkenkooooさんには感謝の気持ちしかありません．楽しいひとときをありがとうございました．

2020-11-13

Educational Codeforces Round 43 D Degree Set

はじめに

これすっげぇおもしろい．
純粋に構築で面白いと思ったの本当に始めてクラス．（いつも構築は解けないので）

問題概要

Problem - D - Codeforces

n
{d1, d2, ... , dn}
が与えられます．
dn + 1 頂点のグラフを構築してください．多重辺，自己ループは認めません．
最後に，グラフの次数を全てsetに突っ込みます．その時，setの内容が与えられた，{d1, ... , dn}と同じになるようにしてください．

この時，必ず条件を満たすようなグラフが構築可能です
↑これ，めちゃめちゃ大事です．（問題でこの文言が与えられています）

考察

とりあえず例を考えます．
d ={2, 4, 5}のような場合を考えます．最初にdn+1頂点を用意しましょう．最初はすべて次数0です．
次数 = [0, 0, 0, 0, 0, 0]
この時，次数5の頂点を作るには1頂点選んで，他の頂点に全て辺を張るしかありません．
ですので，そのように辺を張り，例えば，
次数 = [1, 1, 1, 1, 1, 5]
のような状態になります．
この時，重要な考察なのですが，もう一番右の頂点には辺を張ることができません．多重辺，自己ループは許されないため．

f:id:MUGEN_1337:20201113122830p:plain

そして，この後，辺を張ることを考えるのですが，頂点6にはもう辺を張れないので，これを以降無視していいです．
そして，それ以外の頂点にはもう次数が1増えているので，以下のような問題を次に解けばよいです．
d={1, 3, 4}
次数 = [0, 0, 0, 0, 0]
これは，dの要素を全て1引いて，頂点6を除外した姿です．

ではまた，解いていきましょう．同じように，dの最も大きい要素が，頂点数-1に等しいので，同じような操作を行います．
次数 = [1, 1, 1, 1, 4]
になります．グラフ全体としては以下のようになります
f:id:MUGEN_1337:20201113123508p:plain

同じように頂点を除外します
次に解くのは以下のような問題です．
d = {0, 2, 3}
次数 = [0, 0, 0, 0]
この時なのですが，dの内容物に0が含まれています．
ですので，頂点を1個，これ以降その頂点に辺を張らずに，そのまま残しておきたいです．よって一番左の頂点を残すこととします．
よって上の画像の頂点1をこれ以降触れません．除外します．
f:id:MUGEN_1337:20201113123748p:plain
次に解くのは
d = {2, 3}
次数 = [0, 0, 0]
となりました．
で，もうこの状況で次数3の頂点は作れません．dからpopします．
d = {2}
次数 = [0, 0, 0]
を解いていけばいいです．
同じように，解いていけば，最終的に以下のようなグラフが出来上がって終わりです．
f:id:MUGEN_1337:20201113124106p:plain
次数は最終的に，
次数 = [2, 4, 4, 4, 5, 5] となります．

Submission #98207940 - Codeforces

まとめ

問題で，与えられる入力に対しては必ず答えがあると証明できるといわれているのでガンガン1つの頂点の次数を決めて，再起的に小さい問題を構築することができれば，解ける，というのがこの問題のおもしろポイントだと感じています．
不可能なら不可能と示せ，と言われると，一段と難しくなるような気もします．わかりません．
とりあえず面白かったです．

2020-10-26

ICPC 模擬国内 2020 参加記

はじめに

リハーサルもやってなかったし，メール来てるのも模擬国内開始20分前くらいまで気づきませんでした．チームメイト，すまん！

結果

state_of_the_art (mugen1337, sotanishy, renjyaku)で出ました
5完23位(ABCDE)でした．
本番なら大学2位で通過していたみたいです．ホッと一安心

f:id:MUGEN_1337:20201026001853p:plain

流れ

開始前

renjyaku「遅れます」
sotanishy「遅れます」
僕「君たちブレないですね．僕はつきました」

もう集合時間の15分後につくようにいこうかな...

前日のARCでAtCoderのhighestがsota君に負けていたので，僕が1-indexedで2番目，sota君が3番目をみることに，

コンテスト

AとBが瞬間で解けます．
Bを担当しました．
UFを書いてしまうか，書かないで実装するか，かなりどっちでもよかったのですが，なんかUF書いちゃった方がバグらないかなと思ったので写経しました．めんどかったけど問題なし．

Aを高速で終わらせたrenjyakuがDの読解に，僕が遅れてBを終わらせてDへ．

sota君が「C，いや解けるんですけどめんどくさい．う～ん．」みたいなことを言っています．
「手伝いますか？」と聞いたところ「いや，大丈夫です」と帰ってきたので信じてDへ

ここから僕はこの後コンテスト終了3分前までDにはまります．
1. 嘘解法で実装をしてその実装がかなり怪しくて何度もバグる
2. 1度提出するまで嘘であることに気づけない．具体的には( ( ) ) ( ) ) )で1を返してしまっていました．
3. そもそも問題が難しい．え，難しかったよね？ねぇおい．難しかったよな？
僕とrenjyakuがうんうん唸っている間に，Cをsota君が通します．いや優秀．ホンマありがとうな

renjyakuがいったんDを離れ，renjyakuとsota君がEへ，sota君が瞬殺します．
なんかSCCだったらしいです．チームメイト，優秀．

sota君がSCCを写経，EをAC．優秀すぎひん？

僕はまだDではまっています．

僕がはまっていた原因として，最初にカッコを正規の方法で消していくことを考え，両側にどれだけ消せるかを考えていました．
左右のカッコをそれぞれ独立に考える発想にどうしてもならず，((()))は両端に3まで追加で消せるから~みたいな考察を一生引きづっていました．

みんなでDを考えることにします．僕が考察できているところまでを話してそこからの続きをみんなで考えてしまうため，かなり筋が悪い考察が進んでしまった気がします．
ここらへん本当に僕が圧倒的に悪くて，かなり反省．

そして何も終了15分前まで行きます．
僕は考察が行き詰まるとなんでもかんでも口に出して考えます．すまんチームメイト，うるさいよな．
ところがトリガーはよくわかりませんが一気に考察が飛躍しました．
「...いや～なんか左からガーッてやってそのあと右からガーッってできないかなぁ～～...う～～ん....え？できます．できます．できるので．左右のカッコそれぞれ独立にやります．できますはい．書きます」
みたいなセリフを言った気がします．
詳細をチームメイトに軽く話しますが，理解を得られなかったと思います．ですが実装するしかありません
PCを掴んで慌てて実装を始めます．残り9分でしたがなんとか6分で実装が終わり，死ぬほど焦って提出してAC．死ぬかと思った...いや5回くらい死んだ.
本当にお荷物にならなくてよかった．いやすでにお荷物だったかもしれません．

おわりに

結果的にDが通せてよかったのですが，これに苦戦しちゃ，だめだろ...
とりあえず目標としていた5完ができてよかったです．

うちのチームはICPC用の対策的なのをあまりしていないのでそれが今後の課題ですかね．(構文解析，幾何など)

2020-10-14

区間をsetで管理するやつでもうバグらせたくない

はじめに

バグらせたくない

この記事ができたのはえびちゃんさんのおかげです．ありがとうございます．ありがとうございます．
なんかまずかったら消します
rsk0315.hatenablog.com

本題

たまに出てきます．バグらせたくありません．どうしたらいいんだろう．ライブラリ化しましょう.

これがコードです．

mugen1337.github.io

バグっていたら教えてください．

閉区間をsetで管理しています．
だいたいどれもO(logn)で機能します．erase, insertで区間をたくさん消す時ヤバげに見えますが，結局今まで追加したものを消しているし，erase, insertで増える区間は高々1個なのでならしO(logn)とかいうやつになってるんじゃないですかね？ならしの計算量の概念がいまいちなので言葉をにごさせてください．

実際の使用例と解説

この問題を例に解説します．
codeforces.com

問題概要

最初1~nがonです．クエリl, r, kが飛んできます．k=1なら[l,r]をoffにします．k=2なら[l,r]をonにします．各クエリごとonの数を数えてください．

まぁなんというか，セグ木をしたくなります．が，nの制約がでかいです．ので，このデータ構造を脳を止めて貼ります．
insert, eraseをするときに区間の増減量を返すようにしているので無事に解けます．main内しか新しく書いていないとするとかなり楽な気がします．

このデータ構造のinsert部分だけ解説します．
はい．たいしたことしてないので15秒で書いた絵でゆるし帝

これも解けるよ！

covered_byを使って変更された区間をとってきて幅でchmaxすればいいです．

yukicoder.me

おわりに

コンテスト中に書くコードは少ない方が，いいよね？

こんな機能の追加したらどう？みたいなの募集しています．やろうと思えばいろんな機能を付けれると思っているので．

追記 (2020/11/10)

先日のABC182 E - Akariもこれで解けます．(これじゃなくても解けます)
僕はこれが割と楽だと感じています．

↓が提出です．

Submission #17994184 - AtCoder Beginner Contest 182

列ごと，行ごとに各マス，明かりが届くかを解きます
この時に，このデータ構造を使うと比較的記述量を少なく解くことができると考えています

壁ごとに仕切られた区間の集合stを用意します．最初，-1, wの位置に壁があるとして，st.insert(0,w-1)をしておきます
st.erase(壁の位置)をすることで，区間を壁で仕切ります．
[l, r] = st.covered_by(明かりの位置)をすることで，明かりが届く区間の範囲を取得できます
[l,r]の位置にチェックをつけます．これはセグメント木でチェックしてもいいですし，それこそこのデータ構造を使ってもいいです．1個ずつチェックすると多分TLEします．
最終的にチェックがついているところには明かりが届きます

やっぱり区間をsetで管理するヤツ，そこそこ殴り力があると思っています．いや，もっと簡単にこの問題は解けるんですけど．
あと，こんなふうにデータ構造で殴れるよって言っておいて僕は本番この問題で2ペナはいています(おい)