AtCoder黄色になりました

 2022/09/04 に行われた、AtCoder Regular Contest 147でAtCoderのAlgorithm Ratingが2008となり、初めて名前の色が黄色になりました！

せっかくなので、現時点での活動履歴的なものを残しておきます。

レーティング遷移

初めてのRated参加から4年と7か月

パフォーマンスが安定しない様子

多く解くタイプらしい

トータルの精進状況

AtCoder

AtCoder以外のサイトは少ないため省略

こどふぉは6~7回コンテストに出た程度。

黄色になるまでの変遷

競技プログラミングを始めるまで

（受験期当時）高校数学の範囲は大体出来た 京大理系受験で数学を武器に合格する程度

大学ではいろいろあってCSも数学もあまりやらず、概念をふんわり知っているだけになる

その後はゲームプログラマーになり、PHPでサーバサイドのプログラムを書いていた

灰色

ABC087にPHPで初参加。3完して575位(perf. 593)で32のレートがついた。コンテストのフォーマットや標準入力の取り回しに苦しむ。

2回目のコンテストでAPC001(5時間！)に出る。夜中に頑張った結果3完423位(perf. 1529)でレーティングは431まで上がり、灰色時代は終了。

茶色

ABC088, AGC021, ABC089でそれぞれ緑パフォ、水パフォ、緑パフォでレーティング822になる。Rated5回で茶色は終わり。コンテストの形式に慣れただけ。

緑色

ABC+ARCやAGCで荒稼ぎして2か月ほどで初めての水色になる。

このあたりまではトレーニングらしいトレーニングはしなかった。過去問もほぼ解いてない。

水色

Ratedコンテストの数が激減し、停滞する。また言語の速度がネックになる問題に遭遇し、PHPからC#にメイン言語を切り替える。

1450までレーティングが上がったのちABCが6問体制になる。典型知識に穴がある状態だと不利なコンテストが続き、レーティングが1300を割る。

2019年末ごろから過去問を解くトレーニングを開始し、2020年5月ごろに青に到達する。

2020年4月ごろ、言語アップデートを機にメイン言語をRustに乗り換える。

青色

レーティングに山と谷がたくさんできる。DPと比較的高級なライブラリの整備状況に穴があり、パフォーマンスが安定しない時期が続く。

特にABCの勝率が悪く、ABCは出場回数も多いためなかなかレーティングを上げることができなかった。

青後期はライブラリや典型知識が整ってきたおかげかABCが比較的安定し、ARCやAGCでプラスを積み重ねて黄色になることができた。

青になった翌月以降のコンテスト収支

AGC: 121

ARC: 151

ABC: 22

Other: 63

(直近27ヶ月)

今後の課題

・時期ごとのパフォーマンスにムラがある

　→過去問演習をした時期はレーティングが上がっているので、コンスタントに練習するしかない気がする　ゆきこ/こどふぉ も使っていく

・アドホックな問題に対する考察力が初参加のころから大きな変化がない。(時間をかけても一定以上難しい問題が解けていない)

　→ 重い考察が必要な問題を普段からやる必要がある

・ARC/AGCで難しい問題にチャレンジする時間が残っていない。

　→ 問題を解いた絶対数が足りない 実装/デバッグのスピードも足りていない

今のところARC/AGCで橙パフォ以上は出したことがないので、のんびりやります。

ABC017-C ハイスコア

 概要

https://atcoder.jp/contests/abc017/tasks/abc017_3

N個の区間とそれに対応する得点が与えられる。

それぞれ区間は1から始まる長さMの区間に含まれる。

区間を重ね合わせたときに1からMの区間と一致しないよう0個以上の区間を選ぶ。選び方について得点を合計し、その最大値を求めよ。

 解法

方針

区間[1,2)、区間[2,3)、...、区間[M, M+1)を含まないように区間を選んで得点を計算する。

求める解はその最大値となる。

優先度付きキューを使用し、将来使えなくなる区間と、現在使えない区間を管理する。

初期の除外区間を[0, 1)とすると、与えられた区間[L, R]はすべて将来使えなくなる区間に登録することになる。合計得点は与えられた区間の得点の合計値となる。

除外区間を1ずつ進めながら下記の処理を行うことで、すべての除外区間についての合計得点を求めることができる。

・将来使えなくなる区間のうち、左端が現在の区間にかぶるものは使えなくなるので、合計得点から得点を引き、現在使えない区間に登録する。

・現在使えない区間について右端が左のほうにあるものについて調べ、すでに左にあるものについては再び得点に加える。

https://atcoder.jp/contests/abc017/submissions/20210178

ABC013-C 節制

 概要

https://atcoder.jp/contests/abc013/tasks/abc013_3

N回次の3つの操作を選択する。初期値をHとする値hが一度も0にならないようにするとき、コストの最小値を求めよ。

・コストA払い、hにBを加算する

・コストC払い、hにDを加算する(C<A かつ D<B)

・コストは変化せず、hにEを減算する

解法

すべての日について3つ目の選択肢を選んだ場合、hはNEだけ減少する。

このとき、コストを払う選択肢を選ぶよう変更すると、最終的なhは(例えば)B+E増加する。

hが0以下になることが許されないので、求める答えはコストを払う選択肢をN回以下選択することで、H-NEを正の値にできる最小のコスト ということになる。

これは、以下の2つのパターンで

・k日間、1つ目の選択肢を取り続けたとして、H-NEに満たない場合については2つ目の選択肢を足りない分だけ加える

とすると、各日についてO(1)で払うコストを求めることができるので、全体としてO(N)で解を求められる。

https://atcoder.jp/contests/abc013/submissions/20193158

ABC027-C 倍々ゲーム

概要

A, Bの2人が交互に、2種類の操作から1種類を行う。Nを超える操作を行った方の負け。

初期値は1とする。
操作1: 数を2倍する。

操作2: 数を2倍し、1を足す。

解法

Nを2進数表記した際の桁数の偶奇により、A、Bがどちらの操作を選ぶが反転する。

完全二分木を書くとわかりやすい。

方針が決まればシミュレーションすれば正解できる。

ABC018-D バレンタインデー

ABC018-D バレンタインデー

概要

https://atcoder.jp/contests/abc018/tasks/abc018_4

N(<=18)人の男、M(<=18)人の女からそれぞれP、Q人選ぶ。

得点についての条件が、以下のような内容でR(<=N*M)個与えられる。

・男xと女yを含む選び方のとき、z(<=10000)点が得られる。

合計点を最大化せよ。

解法

　まず、男をP人選んだものとして考える。

このとき、各女を選んだときの得点がO(R)で求められる。

よって、男の選び方1つに対してO(R + MlogM)で得点が最大化できる。

　また、男の選び方は2^18通りを全探索することでP人選ぶパターンを網羅でき、26万通りの探索で最大 18P9 = 約45000通り が得られる。

　男のすべての選び方について得点を計算すると解が得られる。

https://atcoder.jp/contests/abc018/submissions/20169029

近況

表題

・歯の治療を始めた

・BMSは継続プレイ中

・Beatorajaのスコアビューアを作ってる

・ボルダリング始めた

・AtCoderで青コーダーになった

歯

スケジュールが難しくて通えないでいた歯医者に在宅勤務になってようやく通い始めました。
1本抜いて、3本被せものして4本目治療中、もう40万くらいかかっています...
かみ合わせが良くなっていろいろなことに対してイライラしにくくなりました、歯は大事にしましょう。

BMS

3日に2日くらいのペースでプレイ、段位は発狂十段のまま。(皆伝ラブジャス落ち)
表内未クリアは7個まで減らせましたが残りが厳しい面子です(23: L9, M-A 24: 自強号, foon, ephemera 25: 察し)。
上位を倒すべく地力をつけて、23の残りは時々狙ってみる感じの練習をしています。

クリア状況

発狂表

Stella

★2全フルコンはえらいポイントです。えらい。
st1は結構つらいのが残っていて全白は割と厳しい状況です。

スコアビューア

既存のスコアビューアに不満があったので、自作しています。

フロントエンドはVue.jsで、GitHubPagesに載せました。

バックエンドはRust(warp)で、EC2に。

リンク

今はグラフと難易度別に楽曲データを表示するだけですが、日付指定で難易度表の過去の状態を出力できるようにしたりする予定です。

ひとまずはGUIからスコアのアップロードを実装する気持ちです。

ボルダリング

7月下旬くらいに天候の変化に強いスポーツとしてはじめました。

最高グレードは3級で、5級なら1～2トライでだいたい登れるくらいのレベル帯です。

手の皮が剥けまくる時期は終わりを迎えつつあるのですが(つらかった...)、体のあちこちに擦り傷や打撲傷ができるようになってこれはこれで悩ましいです。腱は傷めないようにしたい。

AtCoder

ぼちぼちコンテストに出続けて、5月末のNOMURAコンで青になりました。

が、現在1620±50くらいで行ったり来たりしています...

年内に黄色くなりたいところですが、果たして。

連皿と手首皿について

覚書

前提

2P 1048式＋ベチャスラから手首皿完全固定に移行

移行時 発狂八段 ★★3DISCHAREGD RUSHイージー

現在 発狂十段 ディスチャージは小指皿を使わないとクリアできない(体力切れ)

起きたこと

皿絡みの認識にかかる負担が減り、物量譜面に対する地力が伸びた
下記のような譜面が難しい(できないor疲れすぎてしまう)
　・縦連と複合する(ex. 24ephemera)
　・連皿部分が極端に速い(ex. 23トイレ)
　・一曲に渡って皿が入る（ex. 21あめふりこねこ）

対策案

短い連皿でも肩に力が入ってしまっているので、手首のスナップで回す練習をする
2枚～7枚は個別に練習すべし
手が小さくて5鍵を軸にすると届かないので5～6鍵の両軸を意識する

長い皿はどうしても腕～肩の体力が必要
皿表を活用するなどして体力増強を目指す
筋力が左右アンバランスになってくるはずなので筋トレで補う