AtCoderで入水した話

 

1．はじめに

お久しぶりです。ragnaです。

この前のABC336で入水したので緑の間にやったことを残しておこうと思います。予め言っておきたいのですが、僕はめちゃくちゃ精進量が少ないです。なので「やっておけばもっと早く入水できたかもしれなかったこと」も書こうと思います。

 

２．やったこと

2-1．ABCに出る

とりあえず(用事がある時を除いて)ABCには毎回出ましょう。僕はとりあえずA-Eの5完を目標にしていました。実際に5完出来たのは5回くらいでしたが、いい感じの目標だったんじゃないかと思います。

 

2－2．ABCの復習をする

ABCに出たら基本的に「解けそうで解けなかった1問」を(difficulty<1600なら)ACしました。典型の組み合わせ方や新しく典型を覚えられてよかったです。

 

2－3．過去問を埋める

ABC200以降の水diffのEまでを埋めようとしました。まあそんなに埋まってないんですが……

 

2－4．オンサイトに行く

そこそこの数のオンサイトに出ました。直接的に効いたかは分かりませんが、モチベーションの維持には貢献したと思います。

 

2－5．典型90を埋める

星4以下を低難度から埋めていきました。まだ星4がちょっと残ってますが……

正直これがかなり効いた気がします。

 

3．やった方が良かった(かもしれない)こと

3－1．ARCに出る

僕はARCに出ないという誓いを立てているので(途中から)出ませんでしたが、忌避感がないのなら出た方がお得だと思います。

 

3－2．作問をする

既存の問題をちょっと変えた問題を考えてみて、解けそうならTwitter(自称X)に投げる、とかでいいと思います。何なら解けなくても投げていいと思います。多分優しい人が教えてくれます。

 

3-3．鉄則本を埋める

やった方がいいのは確実なんですが、ABCで出てきた時に確認するので十分な気がしてるのでそこまでやってません。苦手分野が自分で分かっているならそこだけ解く、とかでもいいと思います。

 

4．新しく覚えたアルゴリズム/データ構造

4-1．fenwick_tree

ACLのやつです。累積和を基本的にO(logN)で管理できるのでたまに使います。

 

4-2．lazy_segtree

ACLのやつです。segtreeで出来ることはlazy_segtreeで(多分)出来るので、これを使えるようにすれば十分だと思ってます。

betrue12.hateblo.jp

僕はいつもここからコピペしてます。おすすめ。

解けそうなのに解けなさそうな問題はこいつを使えば大体解けます。

 

4-3．bitDP/ダイクストラ法

これは入緑時点である程度は使えてましたが、問題を見てすぐに見抜けるようになったと思います。実装もかなり早くなった実感があります。ダイクストラ法は抽象的なライブラリがあればもっと楽なんだと思いますが、作るのが面倒なので毎回書いてます。結局は4完でもいいので早解きをするのが重要な気がします。

 

5．おわりに

いかがでしたか？精進量の少なさにびっくりしたと思います。僕もびっくりしてます。

今後はrating1400を目標にしつつヒュや作問も頑張りたいと思います。

ところで最近『空の境界』の文庫版を読んで神妙な気持ちになってたら入水してから1か月経ってました。気になった人はぜひ読んでみてください。マジですごかったです。

効率的に太るために必要なこと

1．はじめに

 

この記事は「でぶ Advent Calendar 2023」の9日目の記事です。

adventar.org

 

こんにちは、ragnaです。

 

いきなりですが、この記事を読んでいるあなたは「でぶ」に対するある程度の興味があるはずです。もちろんありますよね？

 

そこで今回は僕が10年以上肥満体型をキープしてきた経験をもとに、効率的に太るためのポイントをいくつか紹介しようと思います。それでは早速見ていきましょう！

 

2．具体的なポイント

2-1．食べる

 

当たり前ですが、食べなくては太れません。それはそうですね。

 

とはいえ、ただ食べまくればいいというわけではありません。以下に挙げるポイントを意識しましょう。

 

  • 1食の量に固執せず、食事の回数を増やす
  • 間食を意識する
  • 油を多めに摂る
  • 塩は控えめに

 

個人的には武蔵野アブラ學会がオススメです。二郎系は行ったことがないので分かりません(え？)

 

あと朝食は軽くで済ませる人もいると思います(僕もそうでした)。そんな人にはカレーパンが良いと思います。ただ朝は食べなくても間食をすれば問題ないので気にしすぎなくても良いです。

 

2-2．運動しない

 

この記事の中でここが一番重要です。運動するな。

ここでいう運動には「走る」も含まれます。走るな。

もちろん歩きすぎも良くないですが、ある程度は仕方ないですね。

 

具体的には、

  • バス・電車内では出来るだけ座る
  • 出来るだけバス・電車を使う
  • 家では出来るだけ布団の上にいる

です。歩きすぎてしまった日は多めに食べることで調整しましょう。

 

2-3．その他細かい注意

 

ここまでいろいろと書いてきましたが、この記事を読んでる人の中には「いくら食べても太らない」というギャル曽根みたいな人がいるかもしれません。そういう人の大半は自然とストイックになっているだけなので怠惰になってもらえればいいんですが、一部本当に体質で太れない人がいると思います。それはどうしようもありません。ごめんなさい(え？)

 

あと受験生期間はチャンスです。学校がなくなってからはあまり動かなくなると思うのでたくさん食べましょう。僕は3か月で5キロくらい太りました。多分。

 

3．おわりに

 

いかがでしたか？

この記事がでぶになりたい人の助けになれば嬉しいです！それはでは皆さん良いでぶライフを！

緑コーダーが初めて作問した話

1．はじめに

 

12/2に開催された第2回緑以下コンテストの運営に参加し、そこで初めての作問をしたのでその途中で思ったことなどを書いていこうと思います。作問してみたいが何から始めればいいのかが分からない人の参考になればうれしいです。

 

2．Extra-D(自分の問題)について

2-0．運営に参加することになる

 

緑以下コンの主催のくしらっちょさんの運営募集ツイートを見かけ、参加することに。

 

 

2-1．題材を考える

 

初めての作問で何もわからなかったのでとりあえず題材から考えることにした。自分の個性を生かそうとし、数学路線で考えてみた結果、カタラン数を題材にすることに決定。

 

この時点で既に6問ほど作られており、少し焦る。ちなみにこの時点できょさんが2問(最終的なDとK)を作っていた。すごい。

 

2-2．どういう形式でカタラン数を活用するか

 

カタラン数といえば受験数学でグリッド上の移動経路で出てきたな、と思い、直線上の点を通らない移動経路にすることに。ただカタラン数の知識問題にすると面白くないと思い、運営のdiscordに投げたのが下の問題。

 

 

で、それに対する反応が

 

 

2400！？

 

そんな馬鹿な、と思うも、、、

 

 

そ、そんな……

 

とりあえずa=1としておくも、そもそもカタラン数を貼るだけで青以上、となるとどうしようもない気がしてくる。

 

グリッドDPにすれば緑になるだろ！と思うもそれだと面白みがなくなり、一旦保留に置かれることに。

 

2-3．Extraで使えることに

 

このまま没になるのかと思われたが、1か月以上経ってメインの問題作成が進んできたところで全完者用のおまけ問題として何問か使えることに。

 

 

さらに問題ページを作ることに。

 

 

2-4．問題ページ作成

 

問題文と制約、サンプルケースはテンプレート通りに書くだけなので割愛、テストケース作りに取り掛かる。

 

qiita.com

 

とりあえずこの記事を参考にやってみるも、何故か複数ファイルに対する実行が出来なかったので手動でコピペすることに。テストケース生成にかなり時間がかかる(N=1e5のケース1個で5分くらいかかった)ので、

  1. テストケース生成コードの実行時のオプションで「> in.txt」とかで出力
  2. 想定解のコードで「< in.txt > out.txt」として実行
  3. in.txtとout.txtをコピペし、random01などと名前を付けて保存

とするのが良さそう。これで1ケース6分くらい、20ケース作るとすると2時間かかるのでまとまった時間を取ってからやりましょう

 

2-5．解説ページ作成

 

あとは解説を作り(ここは問題文と同じで普通に書くだけ)、想定解で通ることを確認して想定解に指定すればひとまず完成、想定解の提出はマクロを使わずに書くのが一般的なのでオーバーフローに注意。僕は何も考えずにintを使ったらオーバーフローしてテストケースの解答側を全て直す羽目になりました。

 

テスターにURLを送ってフォーマット(変数の前後に半角スペースを入れる、とか)の修正案をもらい、直して完成！

 

3．Extra-A,Bについて

 

原案はそれぞれループさんとはちじさんで、僕が代理でページを作ったので一応紹介しておきます。

 

3-1．Extra-A はじめてのおつかいHard

 

本編のIの完成版として考えられていたのがExtraに入り、ページを作ることに。

 

問題自体はそこまで難しくなかったが、テストケース作成に苦労した。

Nが2e5、Mがmin(N(N-1),2e5)なので最大ケースとしてN=2e5のケースとNが小さくM=N(N-1)になっているケースを用意しなければならなかった。

 

最終的に運営の中でも良問だという評価になった。Extraの中でも簡単(水下位？)だったことからかなりの方に解いて頂けて(ページ作っただけだけど)嬉しいです。

 

3-2．Extra-B 最大最大公約数

 

実はこれのページを作る時点では解法に自信がなく、はちじさんに確認を取ってからスタート。

 

これもテストケース作りが少し面倒で、

  • とりあえずランダムにAを取ったケース
  • Aを特定の値にし、最大K回ランダムな項を+1or-1する、としたケース

の2つを作る必要があり、それぞれに合わせたテスト作成コードを書いた。解いた人はhand01を見ると面白いかもしれません。

 

ちなみにこの問題の計算量の見積もり(解説の最後でd(x)と書いている部分)にはこの記事を参考にしました。

noshi91.hatenablog.com

 

あとこの問題のタイトルは「GCD Maximizer」だったんですが、Maximizerって(Maximizeの派生として)存在しないんですね。かなしい。

 

結果的に水中位(K<Nに気づければ緑中位？)くらいにはなったと思っていて、正直今回のExtraの中で一番お気に入りの問題になりました。

 

ところでこんな問題があって……(こっちはかなり難しそうですが)

atcoder.jp

 

4．作問上の注意点

 

  • とにかく自分より強い人に見てもらう
  • AtCoderで既出かどうかのチェックも怠らない(これはテスター時も)
  • サンプルケースの1つ目には簡単な説明を書く
  • テストケースは20個以上用意する(ランダム10個、Nが最大/最小5個ずつとか)
  • 出来ればコーナーケースも用意したい(思いつけば)
  • テストケースは1個ずつ確実に保存してからページを移動する(1敗)(2時間の努力が消し飛びます)

 

5．これから作問したい人に言いたいこと

 

  • とりあえず原案が出来たらTwitter(現X)で放流するか、(少し大変だけど)yukicoderで問題ページを作るかをしましょう。そのためのSNS、そのためのyukicoderです。(一応MojaCoderのほうが気軽に投稿出来るらしいです)
  • 困ったことがあったらSNS上で聞いてみましょう。教えてくれる優しい人がいるはずです。(僕に聞いてもらっても良いですが、まともなアドバイスをできるとは限りません)
  • 最近はオンサイトの機運が高まっている(気がする)ので、運営に参加できそうならとりあえず参加しておくと不可抗力で作問できるのでおすすめです。うまく作問できなくてもテスターの経験になるし、界隈の人と仲良くなれるので参加するだけ得かも？
  • もっと知りたいことがあったら気軽にDMください。加筆するかもしれません。あと間違ったこと言ってたらこっそり教えてください

 

トヨタ自動車プログラミングコンテスト2023#6(AHC026)参加記

０．はじめに

トヨタ自動車プログラミングコンテスト2023#6(AHC026)に参加したので、やったこと/コンテスト中に考えたことを振り返ってみようと思います。前回のトヨタコンでは青パフォを出していたのでまあまあ期待しており、気合は十分。早速見ていきましょう！

１．問題を見て方針を探る

atcoder.jp

重要そうな条件として、

  • 箱を取り除く順番が決まっている

があるため、焼きなまし系は厳しそう。ということで貪欲ベースに決定。

２．とりあえず正の得点を得る

次に取り出す箱(=残っている箱の中で最小のもの)をiとして、iが山の一番上にあれば無条件で取り除いて良さそう。

iが山の途中にあった場合、iより上の塊を別の山に動かさないといけないが、とりあえず(iがある山以外で)ランダムに選んで移動させ、山の一番上になったiを取り除く。

 

提出してみたところ、1216354点。30分弱しか経過しておらずまだ順位を気にする段階ではないのでこの解法を育てることに集中する。

３．時間いっぱい回してみる

この解法だと一回悪い移動をするとそれが点数に直接響いてしまうので、時間いっぱい繰り返し、一番よかったものを最後に出力してみる。

また、箱がなくなった山(山とは)を記録し、優先的に移動先にする工夫もしてみる。

 

提出し、1295764点を得る。少し伸びたが、やはり解法の中身を改良しないと上位には近づけなさそう。この時点で約1時間経過。

４．ランダム移動先を工夫する

具体的にランダム移動先について考えてみると、i+1やi+2がある山に移動させてしまうと次の移動で動かす量が増えて損、ということに気づく。そこで移動先をi+1~i+5がない山の中からランダムに選んでみる。

手元で動かしてみるとseed0で8100→8800くらいに伸びたため、期待を込めて提出。

結果は1343716点で223位/498人、かなり伸びてテンションが上がる。

1343716点で223位

５．ランダム移動を小分けにする

移動させる塊の中に比較的小さい数(i+3とか)が入っていたらそれを山の上に露出させておけば数回後で移動しなくてもよくなり得だと思い、

  1. iより上の塊の中で最小のものをjとする
  2. iより上の塊を、jより上の塊とj以下の塊に分ける
  3. 上の塊をランダム移動→下の塊をランダム移動
  4. jは確実に山の上に露出する

とする。勿論移動先はi+1~i+5が含まれない山の中から選ぶ。

ということで提出。

結果は1366399点で160位。まさかここまで伸びるとは。

1366399点で160位

6．その後

実は前日に徹夜しており、かなり眠かったため改良案が思いつかず寝落ちを決断。ここで撤退することにした。

7．最終結果

結局341位まで落ちてフィニッシュ。

Twitterで周りの反応を見てみると1356657点の貪欲の人が多かったらしく、ランダム移動が功を奏していたらしい。また、1343716→1366399で一気に伸びたのもその人たちを(知らぬうちに)追い越していたかららしい。

 

一応seed0で9115点のビジュアライザを貼っておきます

seed0で9115点

 

上位の人たちは各山をソートしていたらしく、かなり衝撃を受けた。が、よく考えてみたら

  • 塊を移動させるのを小分けにしても労力は変わらない
  • 塊を小分けにしまくれば(昇順になっている塊ごとに動かせば)ソートに近くなる

ということで、自分の解法からでも到達できそうだったことに気づく。後で自分でも実装してみようと思う。

８．反省と感想

  • 前日に徹夜をしない(自戒)
  • 乱択要素を入れたのは良かった
  • 複数ケースで実験(今回はseed0でしか実験していなかった)
  • 提出ごとに順位表のスクショを撮っておく(最初の2回は撮り忘れていた)

AHC023参加記

はじめに

AHC023に参加したので何をやったのかを書いていこうと思います。文章を書くのが絶望的に下手なので早速始めようと思います。

 

注意：これは自分がやったことのメモ程度のものなので、それを読みたい物好き(？)の人だけ読んでください

問題の概要

atcoder.jp

H*Wのグリッドの土地があり、K種類の作物を育てたい。各作物には収穫する月が決まっており、植えていなければいけない月も決まっている(それより前に植えても構わない)。植える時と収穫するときには出入り口から耕地まで水路を跨がず、作物が植えてある耕地を通らずに移動できる必要がある。出来るだけ多くの作物を植えたい。

やったこと

9/6(4日目)

問題文を読む。思ったよりシンプルだけど焼きなましが刺さらなさそうだったので貪欲ベースでいこうと思う。この時点で「作物をSi以前に植えるメリットなくね？」と思ってしまう。これが全ての過ちの元凶だった。

直感的には奥から詰めていけば効率よく植えれそうな気がする(stackのイメージ)。

とりあえずグリッドをそのまま使うと水路の判定が面倒そうだったのでグラフにする。

9/7(5日目)

とりあえず全マスを「道」と「耕地」に分けようとする。

出入り口のあるマスを始点にBFSをし、遠い順に「耕地か道かが決まっていなければ耕地にし、入口までの道を作る(道と繋がるor入口に着くまで)」を繰り返す。

 

9/8(6日目)

とりあえず耕地にしたところ(行き止まりを想定)にDiが遅い順に詰めていき、提出。得点は13051050点で456位。上位の人たちが35Mあたりで戦っていたので20Mを目標にしようと思う。

 

9/9(7日目)

昨日の提出をもとに、植えていない作物を選び、耕地(行き止まり)の手前のマスに植えられるかどうかを判定、植えられるなら植える、を繰り返す。これをビジュアライザで確認したところ、「道に植えたせいで別のところから収穫できなくなる」ところがあることが分かる。「どうしようかな……」と思いながら一日が終わる。

 

9/10(8日目、最終日)

この時点で500位/750人くらいになっており、焦る。

植えた時点で出入口までを最短距離まで辿り、SiとDiを予約することでgot a kotonaki……と思いきやなぜか収穫できないことがあり、頭を抱える。追加植え付けの回数を手動で決めるという苦肉の策も、ほぼ上がらず13066100点、システス537754225点で580位。

 

反省

・作物をSi以前に植えるメリットを思いつけなかった(これがとても本当に一番重要)

・手元で実行してファイルにする環境がなく、コードテストで実行していたので慣れていなかった(これ手元でどうやるか知ってる人いたら教えてください)

・普段通りの生活をしていたため、あまり時間を取れなかった(AHCはどんな活動にも優先されるべきです)

AtCoderで入緑しました！

はじめに

この記事は僕がAtcoderで緑色になるまでにやったことなどを箇条書き形式で書いていく記事です。この記事が緑coderを目指している人の役に立てれば嬉しいです。

(空いている期間は受験期でやってなかっただけです)

緑になるまでにやったこと

正直ほとんど何もやってないです

  • ABC過去問埋め：やった方がいいのは当たり前ですが、僕はあんまりやってないです(200~最新のD以下を埋めるくらいでいいかと)
  • 鉄則本：僕は買ったのが遅かったので新しく学ぶことはそこまでなかったのですが、具体的なコードが参考になるのでコンテスト中、精進中にそばに置いておきました。お守り？
  • 典型90埋め：埋めようと思ったのが先週なので、23問ほどしか埋められていませんが、それでも結構力になっていると思います、とりあえず星(難易度)4以下を埋めましょう
  • ARCにRatedで出る：Aを気合で早解きすればレートを盛れるのでちょっとだけ出てみましたが緊張から空回りしがちだったのでやめました

緑になるまでで使ったアルゴリズム・データ構造

  • 全探索：言わずもがな。半分全列挙は使う機会がなさすぎるので思いつけなくても良さそう。
  • 二分探索：伝家の宝刀。かなり使うので、めぐる式二分探索をすらすら書けるように。lower_bound/upper_boundで事足りることもしばしば。
  • 貪欲法：貪欲が刺さった！って問題はあまりないけどとりあえず貪欲を試してみるのは大事。
  • DP：最近のABC-DorEはDP率がかなり高めなのでDPに気づけるかが大事。桁DPやbitDPはできなくても困りません
  • 累積和：使う機会はそこまで多くないけど一応使えるように。
  • DFS/BFS：DFSはstack/再帰の両方を使えるように。意外とどっちも使う。
  • ダイクストラ：たまーに使う。BFSはほぼほぼダイクストラで書き換えられるのでこっちに慣れておいた方がコスパは良さそう？
  • Union-Find：めちゃくちゃ便利。中身は理解しなくていいので使えるように。
  • deque：ごくたまに使う。queueに慣れてれば普通に使えると思う。
  • set/multiset/map：最適解ではなくとも楽をしたいときに使える。便利。

参考にしたサイト

めぐる式二分探索

DFS

qiita.com

今後の目標

ひとまずはアルゴ水よりもヒュ緑~水を目指したいですね、とはいえ精進は怠れないので典型90埋めとABC埋めは続けます。

 

あとこの記事書いて疲れたのでABC312の解法記事は書かないかもしれません

ABC311の解法、感想など

はじめに

ABCの問題の解法を(Twitter以外で)残しておきたいと思って記事にすることにしました。そこまで大層なものでもない上に続くかもわからないです。言いたいこと(アドバイスとか)がある人は気軽にコメントしてください。

成績証：

atcoder.jp

A.First ABC

atcoder.jp

A,B,Cそれぞれが登場したかのboolを持っておいた。setの.size()で判定した方が簡単だったが、思いつかず。

atcoder.jp

B.Vacation Together

atcoder.jp

vectorに「その日までに連続で何日全員OKな日があるか」を持っておく。具体的には、s[0][i]~s[n-1][i]が全て'o'ならans[i]=ans[i-1]にし、*max_element(ans.begin(),ans.end())を出力。

atcoder.jp

C.Find it!

atcoder.jp

まず与えられるグラフが連結ではない場合について、各連結成分の辺数と頂点数が等しくなることから、各連結成分内に閉路を持つことが分かる。ということで頂点0から辿っていき、通った頂点を順に記録していく。すでに訪れている頂点に再び訪れたらそこから辿りながら出力する。

atcoder.jp

ans[i]が訪れた頂点の配列、閉路を見つけた時点でその番号をメモしていき、配列を最初から見てメモした頂点が出てきたら(この時点で閉路の長さもわかるので出力し、)そこからの頂点番号を出力した。

D.Grid Ice Floor

atcoder.jp

大まかな方針としてはstackを使ったDFS。ただ今回は進む方向に制限があるため、stackには{次に進むマスのpair,進む方向(0~3)}を入れる。また、それとは別に各マスを踏めるかどうかの配列grid(踏めるなら1,踏めないなら0,岩なら2)や、各マスの各方向について進んだかの配列gone(マス(i,j)から方向kに進んだならgone[i][j][k]=1)を持っておく。特にこのgoneがないとループがあった際に回り続けて終わらなくなるので注意。

最後にgrid[i][j]==1となるマスを数えて出力する。

ちなみにスタートから動けないコーナーケースのケアを忘れて2ペナしている。良くない。

atcoder.jp

 

コンテスト中に解けたのはここまで。

 

E.Defect-Free Squares

atcoder.jp

コンテスト中に考えたこと：

  • サンプルケースから、正方形一つ一つを数えると解法だとTLEする
  • 穴のないgridに穴を開けていき、「穴の開いていない正方形」の数が何個減るかを計算する？
  • 包除原理っぽい？
  • 実装分からん！

 

ということでコンテスト後に解説AC。公式解説があまりにも分かりやすすぎた。

atcoder.jp

atcoder.jp

感想など

  • Dの実装が遅すぎた上に2ペナ出してるのは良くない。もっと早く書けていれば今回で入緑できたかもしれないのに……
  • EがDPだということに気づけなかったのも良くない。
  • でも「そのマスを右下隅とする穴の開いていない正方形の一辺の長さの最大値」を遷移させるのは思いつくわけないだろ
  • 来週こそ入緑する！