はじめに このページはAtCoderを始めてAtCoder Beginner Contest(以下ABC)のA問題、B問題は解けるけど、C問題が難しい…と感じている主にPythonユーザー向けに作成しました。制約と計算量の考え方や、制約と計算量を踏まえて知っておくべき考え方を簡単にまとめました。 そもそも計算量って何？ 何回かABCに参加したことがある方なら、$O(N^2)$や$O(NlogN)$といった計算量オーダーが書かれた解説を見たことがあるかもしれません。正直これが書かれてあっても、何が言いたいのかよく分からない、logがどこから来ているのかが分からない、という方が多いと思います。 この計算量オーダーという考え方は、競技プログラミング界で有名なけんちょんさんのページである計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜から言葉を引用すると 計算実行にどのくら

お久しぶりです！ アルゴリズムと整数好きのけんちょんです！ 今回は俗に「数学ゲー」と呼ばれるタイプの問題のうち、整数について語ります。 【他シリーズ】 AtCoder 版！マスター・オブ・整数 (最大公約数編) エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜 フェルマーの小定理の証明と使い方 拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜 (書籍画像は amazon ページ より) 追記：整数問題を練習できるオンライン教材 本記事に準拠した、整数アルゴリズムを学べるオンライン教材を作ってみました。素数判定から始めて、段階的に学べる教材としました。 整数問題などのオンライン練習問題集 1 問 1 問は下図のような構成になっています。各問題に対して、ユーザが実装したプログラムを提出すると、その場でサーバー上で実行し、正しく挙

okumuraです。前回の記事で異様にいいねがついて少々驚きました。その記事の最後に「余力があればよく使うライブラリー集とかも出すかもしれません」とかいってて何もしてなかったので、まとめました。 0. はじめに この記事は半分自分用のために作りました。私自身あんまりライブラリを使わない方なので、結構抜けているかもしれません。「推しライブラリがないぞ！」などなどはコメントに記入していただけると幸いです。また説明が雑な箇所や個人的見解、ミスなど多々見られるかもしれません。これは私の理解力不足と経験不足などなどからくるものです、申し訳ございません。 一応各項目の後には私のAtCoder,Codeforcesでの使用例も載せておきました。問題のネタバレも含むので読むときには注意してください。参考になればいいと思います。 1. sys sys.exit プログラムを終了させます。私がsysモジュール

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0 はじめに プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほと

Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? okumuraです。前のコンテストでAtCoder青になったのでそれを記念して初投稿いたします。(すぐに水色に落ちそうなので怖いんですが) そのほかの人も結構こういう記事が多いので、今回は個人的にやったこと半分とPythonで気をつけること半分で話したいと思います。 1 AtCoderやり始めたとき AtCoderをやるまでプログラミングはif,for,while文ちょっと知っているぐらいでした。とりあえず、問題解いたらPythonの他の文法とか覚えるだろーと思ってやり始めました。 Pythonを選んだ理由は友人がやってたのと、文法が楽

競技プログラミングの問題を解くためには２つのステップがあります。 問題で要求されていることを言い換える知っているアルゴリズムやデータ構造を組み合わせて解く 必要な（知っておくべき）アルゴリズムやデータ構造は色々なところで学ぶことができます。 しかし、「問題の言い換え」や「アルゴリズムを思いつく」というのは、非常に様々なバリエーションがあり、問題をたくさん解かないとなかなか身につきません。 そこで、この記事は以下のことを言語化し、練習のための例題を提示することを目標とします。 問われていることを、計算しやすい同値なことに置き換える方法アルゴリズムを思いつくための考え方競技プログラミングで「典型的」と思われる考え方 ※一部問題のネタバレを含むので注意 ※良く用いられるアルゴリズムやデータ構造については競技プログラミングでの典型アルゴリズムとデータ構造 を参考にして下さい。 入力の大きさ(制約)

気が向いたら後で検証したりで増やしたりするかも 割と当たり前のこととかそんなに使わないこととかが混じってる PyPy を使う これ必須 AtCoder で使える言語には PyPy があって Python の代わりに使える Numpy が使えなかったりするけど速い 特にループが 3 重とかになるときに効果的 （オーバーヘッドが大きいので最初使ったときに微妙だなって勘違いしがち） 同じコードでの比較（もっと差がついたのもあった気がするけど忘れた） Python (TLE) https://atcoder.jp/contests/abc073/submissions/2692814 PyPy (841ms) https://atcoder.jp/contests/abc073/submissions/2692842 入力の基本 下の 5 通りをコピペできるようにしておくと便利 # 整数 1 つ

はじめに 最近，よくPythonを使って競技プログラミングに参加しています．そこで競プロの問題を解くときに書くことの多い単純な処理について，Python3のコードを基本的なところからまとめてみます．文字列操作やデータ操作に慣れると，本質的なアルゴリズムに専念できてより楽しくなると思います．競プロやってみたいなと思っている人の参考になればうれしいです．（もちろん競プロ以外でも参考になると思います） まずは基本 まずは基本的な入出力からです．ここで躓くと面白くないのでしっかりと押さえておきたいところです． 基本的な入出力 最近自分がはじめたAtCoderや2018年のGoogle Code Jamは入力データを標準入力で受け取り，回答を標準出力に出して結果を判定してもらいます．Pythonでは入力はstdin.readline()，出力はprint()を使うとうまくいきます． 入力データの末尾

自己紹介 こんにちは、HIROSHI0635です。今は、金融関係で働く社会人2年目です（仕事でプログラミングは全くしませんOrz...）。大学時代は文系で、プログラムの「プ」も触ったこともなかったですが、競プロ始めて１０ヶ月でなんとか緑になれましたので、やってみたかった「〜色になりました」の記事を書いてみました。自分語りの自己満記事ですが、AtCoder始めたてのPythonコーダーなら少しは役に立つことが書いているかもしれません。 1.AtCoder始めるまで 始めた動機は、今の仕事に向いてないなと思って本当に辞めようかと迷ってた時、じゃあ次は技術力で勝負できる仕事がいいなと思って、「今からでもやれるもの」という発想でプログラミングに行き着きました。ただ、プログラミングの「プ」もわからない状態で、何か作りたいものもなかったので、どうしようかと迷っていた時に、大学時代の先輩が薦めてくれたの

この記事は、かなり主観が入っています。より客観的な色とレベルの関係が知りたい方は、AtCoder コンテストについての tips という記事が参考になると思います。 目次用語解説ABCAtCoder Beginner Contest のこと。初心者～中級者向けのコンテスト。 レーティング 2000 未満（青色まで）の人が Rated（レート変動あり）になる。 以前、ABC が 4 問体制だった頃はレーティング 1200 未満（緑色まで）が Rated だった。その頃の ABC は初心者向けのコンテストだったが、今の ABC（6 問体制）は中級者も対象になっている。 特に E,F 問題は中級者向けの問題（初心者には手が出ないことが多い）なので、はじめのうちは E,F 問題が解けなくても大丈夫。 AGCAtCoder Grand Contest のこと。上級者向けのコンテスト。 Rated の

（これは AtCoder関連サービス Advent Calendar 2018 の25日目の記事です） AtCoder Unit Test という、ブラウザの拡張機能を作りました。 これは、どういうものかというと「AtCoder の問題ページから、自動でテストケースを生成するツール」です。 AtCoder Unit Test – Get this Extension for 🦊 Firefox (ja) AtCoder Unit Test - Chrome ウェブストア 現在の対応言語は、Java, Kotlin, C#, Python 31 です。 その他の言語については Pull Request をお待ちしています。 動作確認を手動でやってますか？ AtCoder にコードを提出する前に、たいていの場合は動作確認をします。その時に、以下の手順でやるのが一般的です。 プログラムを実行

Pythonのカンニングペーパー こんばんは。しゃもじです。 競技プログラミングでPythonメモを作成することにはまっているので、続々と投下していきます。 二番煎じですが、自分の辞書は自分で作らないと気が済まないタイプなのと、もっと詳しい人が追加でコメントしてくれることを期待して書いています。 忘れたらここをみてカンニングすべし #(追記) Pythonで競プロするときの注意点 未だにこの記事を読んでくださってる方もいらっしゃるようなので注意喚起すると、 基本的にPythonはバチクソ重いので、通らないときはC++で同じアルゴリズムを実装するとアッサリ通ることが多めです。 でもPython書きたいときは同じコードでpypy3で通すとかなり早く行くのでおすすめです。 詳細はこちら #入力 まず基本的なところから。input()は1行だけを取ってこれます(python2ではraw_input

0問目 PracticeA - はじめてのあっとこーだー（Welcome to AtCoder） 1問目 ABC086A - Product 2問目 ABC081A - Placing Marbles 3問目 ABC081B - Shift only 4問目 ABC087B - Coins 5問目 ABC083B - Some Sums 6問目 ABC088B - Card Game for Two 7問目 ABC085B - Kagami Mochi 8問目 ABC085C - Otoshidama 9問目 ABC049C - 白昼夢 / Daydream 10問目 ABC086C - Traveling 終わりに 全く違うサイトにはなりますが、 drken 氏がQiitaで投稿された AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ -

本記事を終えた次は？ AtCoder Beginners Selection を終えたら、AtCoder 上の過去問が AtCoder Problems に集大成されていますので、片っ端から埋めるような気持ちで精進していきましょう。本記事の続編として AtCoder 版！蟻本 (初級編) AtCoder 版！蟻本 (中級編) AtCoder 版！蟻本 (上級編) AtCoder 版！蟻本 (発展的トピック編) も執筆しましたので参考にしていただけたらと思います。また、アルゴリズムとデータ構造に関するトピックを集大成した書籍として、 問題解決力を鍛える！アルゴリズムとデータ構造　(通称、けんちょん本) を上梓しました。ぜひ読んでみてください。 1. AtCoder とは AtCoder は以下のコンテストサイトを運営しています。今後常に訪れることになるサイトです: AtCoder コンテスト

最新の情報はAtCoder公式情報サイトAtCoderInfoに記載されています info.atcoder.jp 以下、古い記事の内容となります。 近頃「AtCoderの色を就活等でアピールしたい時に上手く出来ない！」と言われるので、「どれくらいのレベルの人なの？」という説明と、エンジニアさん向けに「実際どういう問題が解けるの？」というまとめを書いておきたいと思います。解き方のヒントが書いちゃってあるので、自分で解きたい人は、ヒントを読む前に解いてください。 Update履歴 2020/6/22 茶色・緑色に関する評価を書き足しました。参加人数を更新しました。 2022/10/02  アップデート要求が多くありますが、現状でも大きな変化はありません。（この文章を追記しました） 2023/12/09　公式サイトへのリンクを冒頭に追加しました。この記事は昔のものになります。 大前提：AtCod