はてなブックマーク

この記事はCompetitive Programming (2) Advent Calendar 2019 - Adventarの4日目の記事です。 私がC++で競技プログラミングをやり始めた際によく分からなかったものの筆頭がイテレータでした。便利でv.begin(), v.end()のようなお決まりの書き方はできても、少し普段と違うことをしようとすると混乱しがちです。 このようなものは手元で図を描いて整理できるようになる、つまり視覚的に理解できることがとても大事だと思います。そこでイテレータについて「こういう風に理解すると図示しやすくなるかもよ」という視覚的な理解を提示したいと思います。 競技プログラミングでよく使う処理を中心に扱っていきますが、それ以外でC++を書く人にとっても理解の助けになる…かもしれません。 std::vectorのイテレータ まずは一番分かりやすいものからいきます

概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力データを乱数で大量生成して、提出コードと愚直解法の結果を突き合わせ、答えが一致しないものを探すという方法があります。もちろんそのようなデータを確実に得られる保証はありませんが、もし見つかればデバッグの大きな助けになります。 今回の記事はその手順を紹介します。また、生成コードの例としてC++とPythonを扱います。 手順1：愚直解法コード作成 まずは問題に対する愚直解法のコードを書きます。小さな入力データで回すので、 だろうと だろうと気にせず書きましょう。これがバグっていると破綻するので計算量よりも正しさ優先です。 C++等の場合はコンパイル時に提出コ

「スクリプト言語」と呼ばれるRuby、Pythonなどの言語に代表される、比較的実行速度の遅い言語で競技プログラミング（特にAtCoder）をすることについて。 最近色々ともやもやすることが多いので、思っていることを書きます。まさにこれらの言語を使っている方々、これらの言語を使うことについて何か物申したがる方々、そしてコンテストを運営されている方々それぞれに向けて。 長いです。興味があれば読んでください。 2023/03/06追記 この記事の内容は、公開当時である2019年頃のTwitter競技プログラミングコミュニティに関するものです。いくつかの要因で現在このような風潮は弱くなっていると感じます。記事を読まれる際はその点にご注意ください。当時のような風潮が再び蔓延しないことを願います。 私の立場 私は競技プログラミングを始めた当初はRubyを使っていました。AtCoder青まではRuby

5月4日のAGCで、ついに橙になることができました！！！ 初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。 ということで記事を書きます。ここまで来ると体系的に書けることがなくなってきたので、全体的にポエム成分が多めです。 解いた問題 AtCoder ProblemsのAC数と、AtCoder Scoresの精進グラフです。何だかんだでStreakをずっと繋いでいます。 全て埋めたのはABC全部と、ARCのE（昔のC）まで、AGCのDまで（今回のやつ解いていませんが）。最近はARC/AGCで残っている問題がかなり難しくなってきたので、JOIとか過去の企業コンとかを細々とやっています。 このゴールデンウィークは、コンテストに出る他はCodeforcesでDifficult

先日Twitterで少し話題になったので書いてみます。データ構造とアルゴリズム Advent Calendar 2018 の8日目の記事でもあります。 「01-BFS」というものをちょっと丁寧に解説します。これは以下のような問題を解くことができるアルゴリズムです。 辺の長さが0または1である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。 ※図のグラフは非循環（DAG）ですが、必ずしもDAGである必要はないです。 この記事では01-BFSの解説の前に「ダイクストラ法」「幅優先探索」をそれぞれ復習し、その流れで01-BFSを解説します。必須ではありませんが、これら2つのコードを書いたことがない人は是非そちらからやってみてください。 ダイクストラ法 多くの人は 深さ/幅優先探索→ダイクストラ法 の順に学ぶと思いますが、今回は逆の記載順にしています。 ダイ

前回の記事にも書きましたが、AtCoderのレートが1600を突破し、青色になることができました！ 「まずは青を目標に」と思ってやってきたので、とても嬉しいです。TwitterやSlackなどで交流や情報交換などしてくださった方々、本当にありがとうございます。今後ともよろしくお願いいたします。 コンテスト履歴＆ちょっと自分語り コンテスト履歴はこんな感じです。 先週の時点でレート1465、あと3～5回くらい良いパフォーマンスが出せれば青に届くなーと思っていたら、自己ベスト大幅更新の数値が出て一気に届いてしまいました。嬉しいより前に、超ビックリしました。AGCこわい。 初参加のABCでパフォ1600とか出してたりしますが、情報系で修士を出てエンジニア6年目、数学もプログラミングも元々好きだったので、最初から経験値の高い状態で競プロを始めています。RPGでいうと「初期レベルの高い途中加入のおっ

「Rubyでポン」の制作でバグを作ってしまった話を書きます。おおっ、技術者ブログっぽい！ Rubyでポンとは（というか、パネルでポンとは） 「パネルでポン」を知らない方も多いと思うのでかるーく紹介。20年前にSFCで出たパズルゲームです。 基本的には「ぷよぷよ」に代表される落ちものパズルのように、パネルの色を揃えて消していくゲームになります。色々ユニークな特徴はあるのですが今回は省略。とりあえずプレイ動画を貼っておきます。 SFCパネルでポン １人で最高レベル同士ガチンコ対戦 - YouTube そして、「Rubyでポン」はそんな「パネルでポン」のクローンゲームです。Rubyで作ってます。 コード内容 バグってたときに書いてたコードを、思いっきり単純化したものです。配列panelsにそれぞれのパネルが格納されていて、消える条件を満たしていたら配列から削除する、というようなコードを書いていま

最近、やれ社内向けの説明資料作りだ、やれ雑用だ、という感じで、仕事で開発っぽいことができていません… 社内資料ではExcelかPowerPointを使わないと一部のオジさん達が嫌な顔をするので（何故かWordは使わない）、ファイル名に日付入れてメールで送るみたいな儀式をやっていますが、開発文書くらいはplaintextベースで作ってgitで管理・メンテしたい！ということで、過去の遺産をMarkdown化する作業をこそこそと少しずつ進めています。 んで、Markdownで書いたものをPDF化する際に、試してみたのがPandocです。 Pandocについて Pandocは異なる形式のドキュメントやマークアップ言語を変換することができるツールです。HTML、Markdown、LaTeX、そしてWordのdocxファイルなども対応しています。 Pandoc - About pandoc ここに書い