つちのこの日記

競プロと音ゲーがメインです。

AtCoder橙になりました

はじめに

この記事は 競プロ Advent Calendar 2021 - Adventar の11日目の記事です。遅刻してしまいごめんなさい…

本題

競プロを始めて1年と8ヶ月、ようやく橙コーダーになることができました!

f:id:tsuchinok:20211213142913p:plain

皆さん、沢山のファボ及びお祝いリプライ本当にありがとうございます!

自己紹介は以前の記事(入緑しました!! - つちのこの日記)で書きましたし、ポエムは恥ずかしいので赤になるまでは取っておきます。 また、先人の皆さんがモチベーションの維持、コンテストの立ち回りなどの話は書いていたので、今回は別の視点から書きます。

本記事では、黄コーダーから橙コーダーになるための実力向上に役立ったことを、お薦め順に書こうと思います。

CodeForces Div.1 バチャ

  • 効果 ☆☆☆☆☆
  • 手軽さ ☆☆
  • 総合評価 ☆☆☆☆☆

最強です。ARC以上の難易度のセットを、緊張感を持って練習することができます。まったり精進をするのも大事ですが、やはりバチャは時間内に通し切ることが求められるため、考察と実装の精度力、速度力をバランス良く鍛えることが出来ます。 Upsolve をすることで新たな知識も身に付きます。

欠点としては、英語を読まなければいけない(これは利点かもしれません)、拘束時間が長い(最低2時間、Upsolveもするならばそれ以上)などがありますが、欠点を補って余りあるほどの利点があるので、是非やりましょう!

人のブログ・解説記事を読む

  • 効果 ☆☆☆
  • 手軽さ ☆☆☆☆☆
  • 総合評価 ☆☆☆☆

新しい知識や、他人の考察手順、コンテスト中の立ち回りを学べるなど、実は様々な利点があります。 知識ゲーはARC以上ではあまり出ないし、効果が微妙だと考える方もいるかもしれませんが、実は高度典型はARCで何回も出ています。実際、私が橙になった回も高度典型(k値PSP)が ARC-E として出題され、maspy さんの解説ブログを読んでいたおかげでコンテスト中にその問題を解き銀パフォを得ることが出来ました。 何より、コンテストに役立つ役立たない以前に、新しいことを学ぶのは人間の知識欲を満たすことが出来て非常に楽しいです!

記事を読むのは通勤・通学中等いつでも出来て、疲れている時でもやりやすいので、本当にお手軽です。貪欲に知識を仕入れていきましょう!

おすすめのブログ(HP?)は maspyのHP です。

AtCoder 橙diff埋め

  • 効果 ☆☆☆☆
  • 手軽さ ☆☆☆
  • 総合評価 ☆☆☆☆

AtCoderのレートは、基本的にちょっとした成功を積み重ねるよりも、一発大成功を当てた方が上がりやすい仕様となっています。そして、大成功を当てるためには異常早解きをする、もしくは自分の適正難易度以上の高難易度を解く必要があります。

高難易度を解くための練習として、橙diffを考えるのは非常に有用です。橙diffは、黄色程度の実力があれば時間をかければ大抵は苦労しつつも解けることができると思います。その経験を繰り返すことで、本番でも橙diffを通せる確率を上げていけると思います。

AtCoder 黄diff埋め

  • 効果 ☆☆☆(レートが2200以下なら☆☆☆☆くらい)
  • 手軽さ ☆☆☆
  • 総合評価 ☆☆☆

黄diffは、橙になるためには基本的に解けるべき難易度です。(といってもまだまだコンテスト中解けないことはあります…) 黄diffを埋めることで、抜けている典型を抑えられたり、ちょっとした ad-hoc の練習ができるので、特に黄色下位のうちはおすすめの精進方法です。

AtCoder 赤diffを考える

  • 効果 ☆☆☆-☆☆☆☆
  • 手軽さ ☆☆
  • 総合評価 ☆☆☆

橙diff埋めでも言及したように、高難易度を通す練習は大事です。ただ赤diffはむずかしいので、中々解けなくて大変だったり、解けなすぎてモチベが低下する危険もあります。まずは橙diffを埋めにいく方が良さそうな気がします。

作問

  • 効果 ☆☆
  • 手軽さ ☆ (原案を考えるだけなら☆☆☆)
  • 総合評価 ☆☆(楽しさは☆☆☆☆☆)

正直、作問で実力がすぐに向上するかと言うと微妙ですし、テストケースまで用意するとなるとやや面倒であることは事実です。ただ競プロの実力を上げたいのであれば、上に示した他の方法を行う方が効率はいいと思います。

しかし、作問は本当に楽しいです!自分が考えた面白そうな問題が解けた時は本当に気持ちいいですし、皆さんが自分の問題を解いてこの問題は面白かった、このテクニックは勉強になったなどと褒められるととても嬉しくなります。

ぜひみなさんにも作問を楽しんで頂きたいです!

おわりに

競プロを楽しんで続けることで、橙にまでなることができました。まだまだ知らないことばかりですし、これからも勉強していくことで強くなる余地は無限に残っているように感じています。長い道のりですが、赤を目指して頑張ります!

明日の記事は Rute さんの 「Sushiを食べながらSushiを解く」です。

Berlekamp-MasseyやBostan-Moriを使うことで殴れる問題一覧

はじめに

最近Berlekamp-MasseyやBostan-Moriで殴れる問題をよく見るので、そのような問題をメモしていこうと思います。 以下の説明はお気持ちなので間違ってる可能性が大いにあります。もし間違っている点がありましたら教えていただけるとありがたいです。

この記事ではアルゴリズム自体の解説はしません。世の中にはたくさんわかりやすい記事があるので、そちらを参考にしてください。

また、殴れる問題を見つけたらコメントやtwitterなどで教えていただけるととても助かります!

Berlekamp-Massey ってなに?

線形漸化式で与えられる数列の最初の何項かがわかっている時に、その漸化式を求めるアルゴリズムです。 計算量は、求める線形漸化式が $d$ 項間線型漸化式のとき $Ο(d ^ 2)$ です。

Bostan-Mori ってなに?

$d$ 項間線型漸化式を満たす数列の $N$ 項目を $Ο(M(d) \log N)$ で求めるアルゴリズムです。 ここで、 $M(d)$ は $d$ 次多項式同士の積を求めるために必要な計算量です。

$\bmod$ が $998244353$ のときなどは NTT を用いることで $M(d)=d\log d$ となります。 $\bmod$ が $ 1000000007$ のときは (任意modNTT を用いない限り) $ M(d)=d ^ 2 $ となります。

使い方

以上の二つのアルゴリズムを組み合わせることで、線形漸化式の導出が容易ではない(もしくはめんどくさい)場合に、愚直な解法で数列の最初の何項かを求め、Berlekamp-Masseyで線形漸化式を求め、Bostan-Moriで数列の $N$ 項目を求めることで容易に問題を解ける場合があります。

以下ではその手法が使える問題のリストをあげます。(随時教えていただけるとありがたいです)。

殴れる問題一覧

atcoder.jp

OEISを見ると漸化式が乗っているので、Bostan-Moriを使うだけです。

atcoder.jp

周期性がありそうなので、線形漸化式だと思うと、上記の手法で殴れます。

この問題は、あまりを求めるわけではないので、適当に2つの $\bmod$ を選び、復元する操作が必要です。

  • Many Bus Stops (easy) (yukicoder)

yukicoder.me

  • Many Bus Stops (hard) (yukicoder)

yukicoder.me

このように、行列累乗っぽい問題は大体線形漸化式なので、上記の手法が使えます。

  • Tetrahedron (mojacoder)

mojacoder.app

想定解法は対称性から状態を頑張ってまとめて行列のサイズを落とすものですが、この問題も殴ることができます。 愚直に最初の方を求めると、綺麗な漸化式が求まるのであとはやるだけです。

atcoder.jp

  • simple 門松列 problem Re:MASTER (yukicoder)

yukicoder.me

現在のFastest Codeは、これで殴ったものです。

  • Next Rational (yukicoder)

yukicoder.me

線形漸化式であることを信じましょう。 信じるものは救われます。

codeforces.com

周期性!(素振り)

atcoder.jp

頑張って計算すると $Ο(1)$ で解けますが、めちゃくちゃ大変です。

上記の手法で殴ると、とても簡単に解くことができます。 maspyさんの以下のブログが詳しいです。

maspypy.com

  • Good Sequence (yukicoder)

やるだけ

yukicoder.me

随時加筆します。

懺悔一覧

コンテストやバチャ等での失敗を懺悔します

一般的な話

  • 部分問題(や,制約を弱めた版)ですら,これでしか解けない → それに近いアルゴリズムを使う

例題:

atcoder.jp

  • 区間に対する操作や区間和など -> 累積の二要素への作用or演算の言い換えを考える

例題:

atcoder.jp

  • swapをすることで区間を連続にする → $B_i:=A_i -i$ の置換をした上で, $B_i$ を一致させると考えると筋が良い。

例題:

atcoder.jp

  • 総和の期待値 -> $i$ 以上の個数の期待値を $i$ を動かして足し合わせる。 決めうち二分探索とお気持ち的には近いかも、忘れがち。

例題:

atcoder.jp

最適化関連

  • 実は自明な上界 or 下界が達成可能です!!!!!!!!!! ←解けない時には一回疑う!!!

例題: atcoder.jp

  • gcdは,一つ決めれば候補はその約数のみ $ 10 ^ 9 $ 以下の高度合成数の個数は $1344$ 個

例題: atcoder.jp

  • 最適化であっても,最終形の判定問題を最初に考えるとうまくいくことがおおい.

例題:

atcoder.jp

atcoder.jp

  • 絶対値の最大化 は max$(x,-x)$ の最大化で言い換えるとうまくいくことが多い.

atcoder.jp

atcoder.jp

動的計画法関連

  • bitset高速化でもしない限りbool配列でDPは基本的に良くない 何か情報を持たせたい

  • DPの遷移で、使用しない場合の chmax(dp[i+1][j], dp[i][j]) みたいなのを忘れない!!(やらかしが多い)

  • 結果としてありうるか状態を判定する -> 判定問題は貪欲にできる -> 貪欲法をDPに落とす の思考をスムーズに出来るようにする

例題:

https://techful-programming.com/user/event/session/I1Hs4VIF/problem/coding/18306

計算量関連

  • 素直な全探索$ Ο(N ^ 2) $ が間に合うなら,まずそれを試す.

例題:

atcoder.jp

  • 調和級数も疑ってみる(特に数列がdistinctだったりする時)

例題:

codeforces.com

置換関連

  • $i$ から $p_i$ に有向辺を貼って考えるとうまくいくことがおおい.(2点swapなどでも)

例題:

atcoder.jp

実装関連

  • bitのi番目を取る時の bit >> i & 1 この & 1 を忘れない!!! (もはやライブラリ化したほうがよくないか?)

  • if(i == j == k) とか書かない! C++pythonじゃありません!!

メンタル面

  • 落ち着く
  • 冷静になる

純粋培養競プロerの応用情報技術者合格体験期

令和3年4月の応用情報技術者試験に無事合格したので、合格体験期を書きます。

試験勉強前のスペック

都内の大学生(情報は専門外)で、かつPCいじりとかの趣味がなかったので、そこらへんに関する知識は0でした。 競プロは少しやっていた1ので、プログラミングだけは出来るかなーという感じでした。

受験のきっかけ

前回の試験の後に、合格した人のツイートが沢山流れてきて存在を知りました。 春休み暇だし、一個くらい資格取れるといいなーみたいな軽いノリで受験を決めました。

使った参考書

キタミ式イラストIT塾 応用情報技術者 令和03年 | きたみ りゅうじ | コンピュータ・情報処理 | Kindleストア | Amazon

評判が良さそうだったこの本を試験の2ヶ月くらい前に優しいフォロワーさんから頂きました。 かなり噛み砕いて書いてあって2、重度のパソコン音痴だった私にもわかりやすかったです。

午前の勉強でやったこと

自分が怠惰すぎて、気づいたらほぼ何もしないまま試験1週間前くらいになってました。時がすぎるのって早いですね。。

そこで

www.ap-siken.com

のサイトを使って午前の過去問をやってみたところ、40%くらいしか点が取れなくて絶望していました。 そこから毎日少しずつ過去問をやってわからないところを参考書で調べて、当日には55~65%くらい取れるようになりました(合格ラインが60%なので、危ない)

午後の勉強でやったこと

友人に午前が出来れば午後も出来ると言われた3ので、当日まで何もしていませんでした。4 本当に心臓に悪いので、少しは前から見ておきましょう。

当日

天才なので、起床試験に無事合格しました。5

会場に着いたら、全然人がいなくてびっくりしました。結局椅子は3-4割くらいしか埋まらなかったです。(受験料、もったいなくないですか?)

午前試験

テスト直前まで参考書を見てめっちゃ詰め込んでいました。6

午前試験はとりあえず60分くらいで全問埋め終わり、手応え6割強だな、受かってるといいなと祈りながら途中退出しました。

お昼

お昼は八王子でラーメンを食べました。八王子ラーメンを食べるのは初めてだったのですが、上に乗ってる玉ねぎがいいアクセントでおいしかったです。

ラーメンを食べながら、午後の選択科目を何にするか考えてました。この時点ではプログラミングを選択することしか決めていませんでした。

文明の力であるグーグルさんによると組込みシステム開発がプログラミングに近いらしいので、これを選択することに決めます。

残りは2つです。データベースはなんかプログラミングっぽいので選択することにして、後一つを悩んでいました。

すると国語力でシステム監査が解けるという噂を見たので、最期の一枠をシステム監査に決めました。結果的にはこれが大成功でした。

その後は会場に戻り、午後の過去問を見ながら、プログラミングはいけそう、データベース何もわからんという気持ちになっていました。

午後

解いた順番に書きます。

  • 情報セキュリティ

まともに午後の勉強していないのでそれはそうなのですが、何もわかりません。適当に埋めて次に行きます。

  • プログラミング

情報セキュリティが全く解けなくて嫌な気持ちになったので、得意なプログラミングに行きます。 全問を10分くらいで解けて、全知の気分を味わえました。

かなりプログラミングに近い内容でした。一応全部の問題を20分くらいで埋めて次に行きます。

  • システム監査

国語の試験のような感じでした。読解することで知識ゼロでも大体埋められました。

  • データベース

最後にデータベースをやります。 sql 文も大体プログラミングみたいなものだと思って舐めていたのですが、全然違ってなにもわかりませんでした。とても悲しい気持ちになりました。

全部終わったので、1時間強を残して帰りました。手応えとしては五分五分くらいでした。

結果発表

f:id:tsuchinok:20210625125155p:plain

無事合格しました! 午後の点数は、体感ですが

  • 情報セキュリティ 7点

  • プログラミング 20点

  • データベース 7点

  • 組込みシステム開発 17点

  • システム監査 18点

くらいだと思います。

感想

ギリギリでしたが、合格できて嬉しいです!

勉強の過程で、様々な知識が身につけられて面白かったです。

次に試験を受けるときは詰め込まなくてもいいように計画的に勉強しようと思いました。

競プロer向けのおすすめ科目

個人的には以下の3つがおすすめです。

  • プログラミング

緑コーダー以上なら全く勉強せずとも十分満点が狙えると思います。 正直取らない手はないです。

これもプログラミングに近い科目でおすすめです。

  • システム監査

競プロで難読な問題文を読んでいる経験があれば、これくらい読めると思います。知識をほぼ要求しないのでおすすめです。


  1. 現時点でAtCoder2200

  2. その分ページ数は多くて持ち運びは不便です(電子版のほうがよかったかも?)

  3. 要出典

  4. 午後試験の問題を見たのも、当日が初めてでした

  5. 起床試験で足切り食らう人を多く見かけます

  6. 結局直前の詰め込みは正義です(?)

AtCoder Beginner Contest 205 一言解説

30分で解き終わって暇だったので書きます。

A.kcal

$\frac{AB}{100}$ を出力します。

B. Permutation Check

与えられた配列をsortして、 $1,2,\dots,N$ になってるか確かめましょう。 std::iotaを用いると配列 $(1,2,\dots,N)$ が得られるのでこれを用いるのが簡潔でしょう。

C.POW

$C$ の偶奇で場合分けしましょう。 $C$ が奇数ならば $A,B$ の、 $C$ が偶数ならば $|A|,|B|$ の大小関係を判定すればよいです。

D.Kth Excluded

$X$ が小さい方から $K$ 番目 $\leftrightarrow X$ より小さい数が $K- 1$ 個あるという同値変形を行いましょう。

$X$ を二分探索し、判定にはsetのlower_boundを用いることでこの問題に答えられます。

E.White and Black Balls

カタラン数を知っていますか?カタラン数は競プロで頻出なので、知らなかった場合は覚えておくと良いでしょう。

知っていればあとはその考えを用いることで答えが $\binom{N+M}{N}–\binom{N+M}{N-K- 1}$ となります。

$M+K<N$ ならば答えが $0$ になることに注意しましょう。

F.Grid and Tokens

蟻本210ページのDiningとほぼ同じ問題です。辺を湧き出し口→行番号→駒→駒→列番号→吸い込み口の順番で貼ります。

aclのmf_graphを用いると実装が簡潔でしょう。

CodeForces div.1 バチャの記録

6/7からdiv.1バチャをすることになりました。

せっかくなので各回について記録と解けなかった問題の分析をメモっていこうと思います。

解けたけど消化しきれていない問題や、解けなかったけど大事そうな問題については個別に解説記事を書くかもしれません。

よろしくお願いします。

6/7 Codeforces Round #499 (Div. 1)

結果

ABCD4完

一言解法

  • A.こういうのは逆から見ます 1のやつがあったら無理で他は最小にすればよい、簡単でした
  • B.ちょっと悩んでしまった。。 クエリの回数見るとにぶたんで、最初のN回 1以上かという結果が自明なクエリを投げれば真偽が特定できます。
  • C.無限回見ました、GCDをとるだけ K進法のくだり、いりますか?
  • D.やることは割とすぐ見えて、各場所のbitを確かめてからdfsでどうなるかを決めます。実装が170行で破滅してしまいました。。

感想

A-CがDiv.1にしてはかなり簡単でびっくりしました、Dみたいな実装問でうまい実装方針にたどりつけるようにしたいです。

6/9 Codeforces Round #691 (Div. 1)

結果

AB2完

一言解法

  • A.gcdと差は相性が良いのではい
  • B.一瞬貪欲を疑ったがうまくいかないので実家のようなDPをします
  • C.逆置換をうまく処理する方法、初めて知りました(全然見えなくて飛ばした)
  • D.ARCとかにありそう、うーん
  • E.解けそうでしたが終了後に一個勘違いに気づきました。(翌日通しました、考察はEにしては軽かったですが実装でバグらせまくりました、、、)

感想

やー、CからEのどれか一つは通したかったですね。 Bで0.5出てくるのにint / 2 をして1ペナ出したの本当にもったいない、反省です。 E、めちゃくちゃ面白かったです。

6/11 Codeforces Round #580 (Div. 1)

結果

ABC3完

一言解法

  • A.+1と-1に着目するシンプルな構築
  • B.同じbitが立っている数が3つあれば終わりなことには気づいたのに、頂点数が120以下なことに全然気づかなくてロス、勿体なかったです
  • C.仮置きすると大体決まる 特定パートは未証明でやっちゃいました(反省)

感想

Bみたいなギャグをパッと通せるようになりたいです。

6/14 Codeforces Round #485 (Div. 1)

結果

ABCE4完

一言解法

  • A.多始点bfs
  • B.転倒数
  • C.反転させたやつとかにいい感じに辺を貼る、むずかしいです。。。
  • D.めんどそう
  • E.素因数ごとにイベントソートしてHL分解でパス和取得 面白かったです。

感想

Cがむずかしかった、こういうのパッと思いつけるようになりたいです。 Eはかなり好きな感じでした。

6/16 Codeforces Round #692 (Div. 1)

結果

ABCE4完

一言解法

  • A.むずかしい お気持ちでUF
  • B.こういうのは0と1集めた方がいいのでBITでシミュ
  • C.よく考えると後ろ2つ以外自由 コストが2ベキなので貪欲が正当性を持つ
  • D.めんどそう
  • E.終了後に通しました どちらもすごい面白かったです
    • 方針その1 grundy数が $ 512 $ 未満なことに着目すると、連立方程式立てて履き出せる
    • 方針その2 操作が $f(x) = \sum cnt_i x^{i}$ をxor畳み込みでかけることに対応しているので、 $\frac{1}{1-f(x)}$ みたいなのを求める invは FWTしてから各点逆元とってIFWTすればもとまる

感想

Cまで割と素早く解けて成長を感じました。Eは知見が得られてよかったです。

yukicoder contest 291 のwriterをしました

はじめに

yukicoder contest 291 ご参加ありがとうございました! ご参加下さったみなさん、testerを引き受けて頂いたみなさん、本当にありがとうございました!

以下では各問題の講評を記します。ネタバレが含まれるので注意してください。

A.esreveR dna esreveR

原案,解法:PCT

FA:tuteさん(1分45秒)

割とシンプルで個人的には好きな問題です。1問目としてちょうどいい難易度だと思います。

B.Lamps on Graph

原案の原案:2020年度麻布中学入試数学第5問

原案,解法:nok0

tester:むかでさん

FA:uwiさん(6分49秒)

久々に算数の問題を見てたらめちゃくちゃ競プロっぽかったので改題して出題しました。 やることはただの貪欲なのですが、割と面白いと思います。

2問目にしてはやや難しかったかも?ごめんなさい。

C.Simple Sugoroku

原案,解法:nok0

tester:おてらさん

FA:SSRSさん(11分38秒)

すごろくとか考えてたら生えた問題です。Sugoroku 2より前に思いついたので、ABCですごろくが出てびっくりしてました。 後ろから全探索していくことで線形で解けます。(実はQCFium法で Ο(M2) が通ります)

最初の1時間、全然ACが出なくてびびっていました。

D.Matrix Eraser

原案:fairy_lettuce 解法:nok0

tester:ながたかなさん

FA:tabrさん(11分6秒)

writerの解法が嘘貪欲だったので(!?)、解法を提供しました。THE 典型枠ですがとても好きな問題です。知らなかった人は最大流で出来ることについて色々調べてみるといいと思います。

E.Many Complete Graphs

原案:PCT 解法:PCT

tester:蜜蜂さん

FA:NyaanNyaanさん(7分32秒)

沢山の組に辺を貼る時は超頂点っていうのはかなり典型的な気がします。

DとEでどちらが難しいか悩んでいたのですが、いい感じにD<Eになったようでよかったです。

F.Rotation ABC

原案,解法:nok0

tester:chineristさん

FA:tatyamさん(22分56秒)

Ad-hocだったり実験だったり枠。難易度評価が難しかったです。実験すればわかると思います(多分)

G.Swap Many Permutations

原案:nok0 解法:nok0,PCT

tester,賢い解法:tatyamさん

FA:hitonanodeさん(101分54秒)

むずめの数え上げ枠。必要十分条件エスパーして頑張って式変形すると畳み込みに帰着できます。 全然解かれないと思ってたのですが、結局5人もの方に解いていただきました!すごいです!!

なんと実は線形で解けます。 tatyamさんに畳み込みを使わない線形解を教えていただきました、ありがとうございます〜

H. Many Graph in Namori

原案:PCT 解法:PCT

tester:beetさん

全完阻止枠。誰も時間内には解けないと予想しています(beetさんが10時間掛かったらしいので)

↑結局ACは出ませんでした Ω\ζ°)チーン

まとめと感想

優勝はSSRSさんでした!!おめでとうございます!! 参加していただいたみなさん、並びにtesterを引き受けてくださったみなさん、ありがとうございました! セットとして出題するのは今回が2回目ですが、共同作問はいつもとは違った刺激があり、またお互いに問題を強化したりできるので凄い楽しかったです。 作問は問題をただ解くのとは違った楽しみがあるので、とてもおすすめです!

またいつかyukicoderにはセットを出したいと思っているので、その時はよろしくお願いいたします。 最後になりますが、ありがとうございました!!