2019年を振り返って～競プロ編～

f:id:ysystem57:20191229094045j:plain

昨日のAGC041で2完して水パフォを出し、highestを更新しました緑が見えてきましたが、本日のABCには参加できないので年明けにでもなりたいです ARC級が2つあるのでそのあたりで

アルゴリズム実技検定受験記
- G 組み分け/Division
AGC041
- B Voting Judges
2019年を振り返って
- 灰色の時期
- 茶色になってから

アルゴリズム実技検定受験記

有効期限が2年ということもあり、受験するか迷いましたが、力試しにと思い受けてみることにしました

認定級は初級茶コーダーにしては頑張った方かと解けた問題はA-B-C-D-F-Gで、合計点は45点でした解けて嬉しかったのはGですねその週に勉強した成果が出たので

G 組み分け/Division

ABC147-Cでbit全探索の問題が出ました当時はそんなことを知らなかったのでもちろん解けず... その後勉強して無事AC 類題も解いてみて書き方は徐々に分かっていきました

このGはbit全探索を応用して解きましたグループが3つ以下なので、組み分けを三進法表記したとき各ビットの数字が同じ人同士で同じグループに入ればよい、と考えましたあとは各ペアを見ていって $O(3^ NN^ 2)$ で解けると思いますグループを区別していますが今回は特に問題ないです

また2年以上後に受験しようと思いますその時にはもっとレベルアップして臨みたいですね

AGC041

＜以前の記録＞

AGC038:nosub撤退

AGC039:1完緑パフォ +113

AGC040:0完 -9

参加前は本当に不安でしかありませんでしたですが

＜今回＞

AGC041:2完水パフォ +153

見事大勝利ですが...

Ctrl CするはずがCtrl VしてしかもCtrl Sしてたから書き直すはめに... 20分くらいロスしました
— ysystem (@ysystem7) 2019年12月28日

もっとパソコン強くなろうと思いました

B Voting Judges

僕の解法です（長いです（笑））

f:id:ysystem57:20191229141401j:plain

数列 $A$ をソートします（以下0-indexedとする）上のような図を考えます投票の際は各 $A _ i$ に対してブロックを積み上げていくイメージです各 $A _ i$ に積み上げられるブロック数の最大値は $M$ です $A _ {N-p}$ から $A _ {N-1}$ の $p$ 個の問題は確実に採用されますあとは $A _ 0$ から $A _ {N-p-1}$ をすべて見ていきます $s:=N-p$ とします

$0 \leq i \leq s-1$ について

(a) $i+1-V \geq 0$ のとき

$A _ {i-V+1}$ から $A _ i$ にそれぞれ $M$ 個のブロックを積み重ね、 $A _ i +M \geq A _ s$ となれば $A _ i$ は採用されます

(b) そうでないとき

f:id:ysystem57:20191229141405j:plain

$A _ 0$ から $A _ i$ にそれぞれ $M$ 個のブロックを積み重ねます残った $k:=V-(i+1)$ 個のブロックの山（山の高さ $M$ ）をどこに積み重ねるかを考えます

(b-1) $N-k ＞ s$ のとき

$A _ i +M$ と $A _ s$ の大小関係が分かれば十分なので、 $A _ {s+1}$ から $A _ {N-1}$ のいずれか $k$ 個にブロックの山を積み重ね、 $A _ i +M \geq A _ s$ となれば $A _ i$ は採用されます

(b-2) そうでないとき（ $N-k \leq s$ のとき）

f:id:ysystem57:20191229141416j:plain

まず、 $A _ {s+1}$ から $A _ {N-1}$ までそれぞれブロックの山を積み重ねますそうすると $t:=k-(p-1)$ 個のブロックの山が残ります次に、 $A _ {i+1}$ から $A _ {i+t}$ までそれぞれブロックの山を積み重ねますそうすると上図のように $A _ i+M$ より大きくなる部分（緑斜線部）ができますこれを赤斜線部に移動させることを考えます（このときブロックの山の形は変えてOK）赤斜線部に収まれば $A _ i$ は採用されます

2019年を振り返って

競プロ活動はまだ三か月ほどですが、今年を振り返っていこうと思います

灰色の時期

正直言ってつらかったです AGCで1回うまくいったことはありましたが、ほかの回ではレート微増程度なかなか伸びないなあと早く色が付いてほしいという気持ちでいっぱいでした特につらかったのはオーバーフローでACできなかったことこれが2回連続で続いたときはメンタル相当やられましたそれでもコンテストには毎回参加していました

茶色になってから

色変してからの伸びは灰色の時とは比べ物にならないと思いますコンテスト中に茶diff後半の問題が解けるようになり、茶パフォ以上は安定してきました考え方も以前に比べればだいぶ身についてきたのではないかと思いますコドフォに参加してたのもよかったかもしれません基本は深夜開催ですが、出られるときにはなるべく出ていました

まだ緑にはなっていませんが、緑になってからは今まで以上に精進が必要になってくると思いますまずはB1のうちに緑になり、そこからさらに精進していこうと思います

それではよいお年を