記録

競プロとか

AtCoder Beginner Contest E Mex-Min

競プロ Mex

はじめに

アウトプットと、自分の理解のために、自分の理解についてまとめています。

問題

atcoder.jp

方針

配列によるMexの管理

最初のMexは、先頭の要素からM個の要素を見ることで求められる。


mex_{0} = mex(A_{0}, A_{1}, ..., A_{M-1})

Mexの求め方は、配列 cnt を用意して、M個の要素の出現回数をカウントする。そして、配列のindexを0から見たときに1度もカウントされていない値（ cnt \left[ v \right] = 0 となる v)がMexになる。

次に、最初のMexと次のMexの違いについて考える。

最初のMexは、


mex_{0} = mex(A_{0}, A_{1}, ..., A_{M-1})

次のMexは、


mex_{1} = mex(A_{1}, A_{2}, ..., A_{M})

一般化して考えると、Mexを求めるための A_iからの整数列は、 A _ { i-1} がなくなって、 A _ {M+i} が追加される。

配列 cnt の変化について考えると、 cnt \left[ A_0 \right]-1 されて、 cnt \left[ A_M \right] + 1 というように更新される。

このとき、Mexがどう変化するかについて考えると、Mexに成りうる値は、 -1 された A_0 である。（ cnt \left[ 0 \right] から一番最初に現れる cnt \left[ v \right] = 0 となる v がMexとなるので、 cnt \left[ A_0 \right] = 0 となれば、その値がMexとなりうる。）

ただし、 A_0 が実際にMexであるかどうかについては考えていなさそう。（求めたい答えは個々のMexの最小値なので、Mexと成りうる最小値のものだけ考えれば良さそう。）

数列を横にずらして更新しながら答えを求めることができる。

提出

atcoder.jp

AtCoder Beginner Contest 197 D Opposite

はじめに

アウトプットの練習と精進。

問題

ABC 197 atcoder.jp

D問題「Opposite」 atcoder.jp

解法

N=6のときの例。 f:id:dsytk7:20210402134817p:plain

Nが偶数なので、対角線から中心点を計算できる。 f:id:dsytk7:20210402134915p:plain

中心点を原点に持ってくる。 f:id:dsytk7:20210402134925p:plain

P _ 0 を \theta 分回転させて、元の位置に戻せば答えになる。 f:id:dsytk7:20210402134936p:plain

\theta は、 \frac{2 \pi}{N} で計算できる。

回転は、回転行列により、 (x, y) を \theta分回転させた座標 (x', y') を計算できる。

x' = x \cos{\theta} - y \sin{\theta}
y' = x \sin{\theta} + y \cos{\theta}

提出

atcoder.jp

  • 本番解けなかった。数学の勉強をしましょう。

HACK TO THE FUTURE 2019 本戦参加記

future-contest-2019-final.contest.atcoder.jp

HACK TO THE FUTURE 2019予選を20卒枠で通過したため本戦へ参加しました．
11/36位（346065509.22）．賞金枠に入れなかったため悔しいが，とても楽しかった．

考えたこと

  • スキル
    • スキルレベルが低いと討伐報酬がかなり下がってしまうのでスキルレベルは大事そう
    • 適当にお金を稼いでレベルを上げてみると案外早く全レベル10にできる
    • 全レベルが10になった後は討伐報酬が下がることがなくなるので嬉しい
    • できるだけ早く全レベル10にする問題か？
  • レベル上げの順番
    • わからない
    • 2ターンぐらい先の分の討伐依頼を先に決めておいて，それに必要なスキルを優先して上げるようにした（効果はあまりなさそう）
  • レベルの上げ方
    • お金があればスキルレベルを優先で上げる
    • なければ，適当に決めた討伐依頼を受けてお金を稼ぐ
  • 全スキルレベルが10になった後の討伐依頼の選び方
    • 後ろから，貰える金額が一番多い依頼を選ぶ貪欲で埋めた（厳密解ではないらしい？）
    • 最小費用流や焼きなましを使ってる人がいた（？）
  • スキルレベル上げる途中に討伐報酬が大きい依頼がくることがあるのでこれを上手に拾う必要がある
    • これを終了10分ぐらい前に気づいた
    • 雑に実装したら328045302.44から346065509.22になった
    • これにもう少し早く気づいていれば...

感想

探索とかで頑張らないといけないのかなと思いつつ貪欲っぽくやった
割と成績が良かったが，何故良かったのかがあまりうまく説明できないため良くない
次回は就活枠が使えないため，実力で通過しなければいけない（マラソンの精進をする必要があり）

どういう会社なのかも知らずに好感度が高かったフューチャーアーキテクト社さんなんですけど，会社紹介があったのでどういう会社なのかがわかった

わりと色んな人と交流できて楽しかった

パーカー嬉しい．AtCoderのステッカーももらえたので嬉しい．

ACM-ICPC 2016 国内予選に参加した

競プロ

初参加。
悔しかったので書いた。


問題

A

印刷している間に解き始める。
簡単だと思ったけどサンプル合わずに問題読み間違えていた。
もっと早く通せたので悔しい。

B

これに時間を吸われてたところ、C担当してたチームメイトが解法を提示してくれて通せた。
思ってた解法と違ってパニクってた。
もっと紙の上で頑張らなければ。

C

本番ではこれを通せなかった。
解法は合っていたが篩は使えないと思い込んでいて他の実装の検討がつかず終了した。
終了後、篩で通せることに気づき絶望していた。

反省点
  • 3問通すことを目標としていたが、達成できなかった
  • チームで出ることが初めてだったので、チーム戦っぽいことができなかった
    • ペアプロとかすればC通せたことはチーム内反省会ででてきたので
    • もっとチームで練習をしておけば3完はできたかな
  • Dからは読んでないけどそれもダメ。ちゃんと問題読む
  • もっと紙の上で考察すべき
  • パニクると死ぬことが分かったので何かしらの対策を講じる必要がある
  • そもそも演習量が足りていない

精進。

終わり

チームメイトが競プロに興味を持ってくれて嬉しい。
何故かCTFにも興味を持ち始めていた。
チームメイトの🍣君が本番終了後に隣で蟻本をポチっているのを見た。

来年はもっとチーム戦したい。