こんにちは、CPPXのP1です。 CPPXのブログモチベが低そうで悲しいところですが、今週も更新していきます。 今回は、競技プログラミングの中でも重要な考え方(？)である計算量のはなしです。 計算量の求め方ではなく、どのくらいのオーダーが何秒くらいで終わるかなーっという記事になります。 方針が立ってから実装前に、この実装で間に合うor間に合わないが分かると捗りますよね。 まず基本として、プログラミングコンテストチャレンジブック(蟻本)には、 制限時間が1秒の場合、 10の6乗　余裕を持って間に合う 10の7乗　おそらく間に合う 10の8乗　非常にシンプルな処理でない限り厳しい とあります。(C++を基準として書かれています) 手元で試した感じでも、かなりシンプルな処理の10の7乗で 10の8乗で くらいでした。8乗の方は1つif文を増やしただけで2秒を超えたので、現実的な処理を考えると、A

gets.splitこれは余談ですが一応。標準入力から1行とって空白で区切って配列にします。最終的にto_intで整数化するためchompでの改行削除は省略します。 ここまでで標準入力が’1 2 3\n’だとしたら、データは[‘1’, ‘2’, ‘3\n’]という文字列の配列になっています。 Enumerable#map（EnumerableはArrayの親クラス）はブロックを受け取り、配列の各要素を引数としてブロックを評価し、結果を配列にして返すメソッドです。これによって各要素にto_iを行い整数の配列とするのが今回のコードの目的です。 わかりやすく書くと a = gets.split.map {|n| n.to_i} こうで、これを理解するのは簡単だと思います。ブロックをそのまま記述していますから。これがどうして&:to_iと省略されるのかというのが今回の話です。 Procクラスブロッ

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

0 はじめに プログラミングコンテストチャレンジブック (通称、蟻本) は日本の競技プログラミングの普及に多大な貢献を果たしています。多くの競技プログラマたちが蟻本を手に取りながらコンテストの世界に没入して行きます。しかしながら発売から 6 年以上経過する間に競技プログラミング界隈には大きな変化がありました。蟻本的に影響が大きいのは以下の点です: POJ が国内ではあまり使用されなくなった (計算速度が遅いなど) AtCoder 上で問題を解くことが盛んになった 今回はこの完全解決を試みます。具体的には、蟻本に載っている例題たち (ほとんどすべて POJ 上の問題です) を AtCoder 上でジャッジできる問題に対応付けようという試みです。今回は初級編を扱い、中級編、上級編は別記事に続きます。AtCoder 上で見つからなかったものは AOJ, yukicoder 上の問題も載せています