【競プロ】 AWS Cloud9でAtcoderLibraryを導入しよう
こんにちは
前編では「Cloud9を使うと簡単にc++環境が整うよ」という話をしました．今回はその続きで，「AtcoderLibraryを導入しよう」という話をします
前編はこちら
sojisan-kyopro.hatenadiary.com
AtcoderLibraryを導入しよう
1.AtcoderLibraryをダウンロードして解凍します
2.解凍したフォルダ内の，「atcoder」フォルダをcloud9上にドラッグし，コピーします
ファイル名の上にドラッグしないとコピーされないので注意しましょう
3.コンパイルコマンドを書き換える
#include<atcoder/all>を含めてコンパイルしようとしても，これのファイルがあるのはインクルードパスではないので怒られてしまいます これを解決します
下記画像のRunner→Edit Runnerを選択します
内容をコピーします
下記画像のRunner→New Runnerを選択し，開かれたファイルにコピーした内容をペーストします
七行目を
" g++ -ggdb3 -I . -std=c++17 -Wall $file -o $file.o ",
十一行目を
" g++ -std=c++17 -Wall $file -I . -o $file.o",
に書き換えます
Ctrl+Shift+Sで適切な名前に書き換えて保存します
おわり
プログラムを実行してみよう
先程保存したrunnerを選択します(画像ではc++_withACL)
Runを押してプログラムが実行できることを確認します
おわり
いかがでしたか
簡単ですね．
おまけ expander.pyを使おう
codeforcesなどではACLを使えません これの対策として，公式から「expander.py」というツールが提供されています(これの内容については，ACLをダウンロードするとついてくるマニュアルをご確認ください)
cloud9でもこれを使おうという話をします
cloud9にexpander.pyをコピーします
New Terminalを開きます
ターミナルに「python3 expander.py (展開したいファイル名)」と入力し，実行します
combined.cppが生成されます
おわり
【競プロ】 AWS Cloud9で簡単！ C++環境構築
こんにちは
AWS Cloud9は，AWS上で動作するエディタです．以下の言語のコンパイラ，強調表示機能，基礎的なスニペットが最初から用意されています．
競プロerへの道の最初の関門がC++環境の構築ですが，AWS Cloud9を用いると簡単に環境構築ができてしまいます．
私は二年近く競プロをやっていますが，未だにVSCodeなどを用いた環境構築の方法がよくわかっていないですし，特に困っていないのでずっとCloud9を使っています．
オンライン上で動作するエディタなので，どのパソコンを用いても同じ環境でコーディングできるのが強みです．自分のように，研究室でも研究をサボって競プロをやるような人種に向いていると思います．
適切な設定をすれば，最近流行りのAtcoder-Libraryも使えちゃいます(やりかたは後編に記します→【競プロ】 AWS Cloud9でAtcoderLibraryを導入しよう - sojisanの競プロ日記).
注意1 クレジットカードが必要です．お持ちでない方はデビットカードをご用意ください(webmoneyとかでもいけるかもですが，確認していません)
注意2 AWSのEC2インスタンスは一年間無料ですが，それ以降は有料となります(それ以降も月数ドル程度ですが)
環境構築をしよう！
1.AWSのアカウントを作成します．
2.cloud9のページにアクセスし，create environmentを選択します
https://console.aws.amazon.com/cloud9/home/product?#
3.適当な名前をつけます
4.インスタンスの設定をします デフォルトの設定で問題ないです
5.確認画面を確認します
6.エディタが立ち上がります 環境構築はおしまいです
プログラムを実行してみよう！
1.New Fileを選択して新しいファイルを作成します
2.Ctrl+Shift+Sで名前をつけて保存ができるので，「適当な名前.cpp」と保存します
3.適当なプログラムを書きます
4.上記のメニューバーからRun→Run With→C++を選択します
5.プログラムが実行されます
6.おわり
F5を押すと前回実行されたプログラムが自動で実行されるので便利です．
いかがでしたか
簡単ですね．
後編へつづく
sojisan-kyopro.hatenadiary.com
AtCoder青色になって一ヶ月半がたちました
こんにちは．sojisanです．
2020年8月15日に開催されたAtCoder Beginner Contest 175で青コーダーになりました．
青コーダーになって一ヶ月以上立ちましたが，今更ながら色変記事を書いてみます．がんばって書いたのでがんばって読んでください．
青変記事なんて無限にあるし，それらより優れた情報や新たな情報はおそらく提供できないし，めんどくさいし，当初は色変記事を書くつもりがありませんでした．しかし，よく考えたら自分が色変する機会なんて人生に数回しかない(AtCoderに限っていえば多くてもあと3回しかない)し，黄コーダーになれるかもわからないので，せっかくだし記念になにか書いとけという気持ちになりました．どうせ書くなら公開しちゃえということで，公開しました．
自己紹介
名前:sojisan AtCoder(twitter:@50j1_)
レート: Atcoder:1699(青) Codeforces:2091(紫) TopCoder SRM:1365(青)
第三回アルゴリズム実技検定：上級(88点)
現在の研究内容 蒸気機関で問題となる損傷現象の定量化を目標とした研究
職歴 来春から非情報系企業の技術職として就職する予定
プログラミング歴 高専時代に反応流のシミュレーションをテーマとしており，Fortranを少し触っていた
現在の状況
競技プログラミングとの出会い
高専専攻科時代(大学3，4年に相当します)に研究でFortranを使うということで，プログラミングの勉強法を調べていたときにAtCoderに出会いました．はじめは暇なときに灰diff・茶diffの問題をFortranで解いていただけでしたが，次第に競技プログラミングそのものにのめり込んでいくようになりました．
大学院入学を期に本格的に競技プログラミングをはじめようとロベール本と蟻本を買い，C++とアルゴリズムの勉強をはじめました．
～水色になるまで
ぶっちゃけ何も覚えていません．本当は各色になるまでやったことをそれぞれ書こうと思っていたのですが，本当に何も覚えていないので省略します．
暇なときに虚無埋めをしていたことだけ覚えています．なので，簡単な問題の早解きが同レート帯の人と比較して得意だったと思います．
また，レートが1000になるまではFortranでコンテストに出ていました．Fortranは配列の記述を省略しまくれるので，早解きに適した言語だと思います(例えば以下の画像のような書き方ができます)．
とにかく早解きでレートを稼ぎまくっていた記憶があります．特に平成ABCの時代は，茶diff下位の問題(これ自体も今の茶diffより遥かに簡単な気がします)を早解きできれば水パフォが出るようなこともしばしばありました．
～青色になるまで
習得したアルゴリズムについて書いていこうと思ったのですが，雑多になってしまったので本記事末尾に記します．
そのほかにAtcoder青になるまでにやったことを記していきます．
海外コンテストに参加する
Codeforcesをはじめとするコンテストに参加するようになりました．自分は意志が弱く，問題が解けそうにないとすぐに投げ出して他の問題を解いてしまったりすることがしばしばあります．ratedのコンテストに参加すると本気にならざるを得ないので，強制的に集中モードに入ることができます．
私も英語苦手人間ですが，google翻訳とdeepl翻訳を使えばなんとかなります．最初はなんとかならなくても数回コンテストに参加すれば次第になんとかなるようになっていきます．慣れです．英文が難解でなんとかならないこともたまにあります(Readforcesと呼ばれます)．そういうときは大抵みんなもなんとかなってないので平気です(？)
バーチャルコンテスト(バチャコン)に参加しまくる
最初はAtcoderProblemsのバチャコンに参加しまくりました．他人と競い合うので楽しいですし，集中して問題に取り組むことができます．unratedコンの思わぬ良問と出会えることがあるといったメリットもあります．
ただし，青コーダーになる頃には解いたことがある問題の割合が増えてきたので学習効率が悪いな，と思うようになり，最近はもっぱらCodeforcesのバチャコンに多く参加していました．Codeforces Anytimeというサービスがあり，バチャコンの結果によって疑似レートが変動するので高いモチベーションでバチャコンに参加できます．
コンテスト終了後にtwitterに各問題の解法をつぶやく/他の人のtweetをみる
いい復習になります．他の人が自分の説明を「わかりやすい」と言ってくれることもたまにありとても嬉しいです．また，他人のtweetを見ることでわからない問題の解法や解にたどり着くまでの思考過程を理解できたり，別解を知れたり，それが典型知識であることを知れたり，と有益なことがたくさんあります．
解いた人数が多い順に問題を解く
AtcoderProblems を用いることで未AC問題をACした人数順にソートできます．解いた人数が多い問題は他の記事で紹介されていたり，有益な問題が多いように思えるので(たとえばEDPCはunratedなのに，多くの人に解かれています)，自分の知らない典型知識に触れることができるように思います．
ただし最初の方は灰diffばっかりなので，ひたすら無益な虚無埋めが続きます．
自分は，やる気が出ない日に虚無埋めをしまくる癖があり，自分より明らかに弱い問題をほとんど解いていたのでこの方法を取れましたが，そうじゃなければ効率は最悪だと思います．おすすめしません．
黄色になるために
黄色になるためにやる必要がある，と考えていることを以下に示します．
数学的考察力の向上
私は中学受験や大学受験を経験していない上に高専出身なので，同レート帯の人と比較して算数力・数学力が大きく劣っているように思います．高専でも無論数学をやりますが，工学への応用を前提としているため，数学的な性質の証明問題などは非常に軽視されているように思います．難しい競技プログラミングの問題を確実に解けるようになるには，解法の正当性を適切に証明する能力が極めて重要になると考えていますが，その実力が非常に不足していると感じています．どうすればいいですか．効率よく数学的考察力を向上する方法を知っている人は私にこっそり教えて下さい(切実)
複数の強い人が「数学力向上のためにはSRM Div1 easyをやれ」と言っていた気がするので，とりあえずSRM Div1 Easy Huntingをやろうと思っています．
蟻本をちゃんと読む
上級編とかはまだ読んでなかったり，それ以前の内容でも難しそうな問題は飛ばしていたりします．一回精読をしたいなあと思っています．
これまで学んだアルゴリズムをしっかりと理解する
ぶっちゃけダイクストラ法すらなぜ動いているのか未だによくわかっていません．競プロで用いられるアルゴリズムは先人が非常に高効率化したものであり，その構造をしっかり学ぶことはより高度なアルゴリズムを設計するために必要だと考えています．やろうやろうとずっと思っていますが他のことを優先してしまっている現状です・・・(むしろそれらのアルゴリズムの中身がブラックボックスでも青コーダーになれてしまうともいえます)
ちゃんとupsolve・復習をする
サボりがちです．コンテスト中に解けなかった問題を放置していたらずっと解けないままなのは理解していますが，めんどくさくて放置しがちです．しっかり復習をしましょう・・・
yukicoderの問題を解く
しばしば「yukicoderで同じようなテクニックを見た！」という言説をtwitterで目にするので，yukicoderにも手を出してみようと考えています．
難しい問題を時間かけて解く
大量の気力が必要となるのでなかなかやれていませんが，考察力を身につけるために必須だと思っています．黄diffを4問しか解いたことないのはさすがにマズいので・・・(しかもコンテスト外でちゃんと解いたのは1問だけ・・・)
とにかく問題をがんばって解く
物知り博士「問題を解かないと問題を解けるようにはならないんじゃ」
良好なメンタルを保つ
人生のために大事です．メンタルが終わると思考力も終わるらしいので気をつけましょう．研究も佳境に入ってきますが，良好なメンタルを保てるようにがんばります．精神が疲労したときはひとりカラオケに行くことにしています．
その他
「これやるといいよ！」というアドバイスを募集しています．
よくありそうな質問
解けない問題はどのように対処していますか？
コンテスト中に解けなかった問題のうち，考えても解けなかった問題に関しては解説を読んでしまうことが多いです．
とっかかりがつかめないときはその問題についているタグを見ることが多いです(大体のコンテストサイトでは公式の機能で提供されています．AtCoderではされていませんが，有志によるAtCoder Tagsというサービスがあります)．それでも，一時間くらい考えてもわからないときは解説を読んでしまいます．
ただ，いずれにしても写経はせず，解説を読んでから数日放置して，それから改めて自力で解いてみることが多いです．案外ちゃんと理解できていなかったりして，解けないことがあります．その時はまた解説を(より丁寧に)読んで，また放置して・・・とすることが多いです．
環境について教えて下さい
環境構築が面倒なのでAWS上で動作するcloud9というエディタを用いています．これの利用自体は無料ですし，Amazon EC2も一年間は無料です(その後も月数ドル)．とっても簡単にc++環境を用意できるので初心者の導入に割とおすすめだと思っています．また，私は，自分のPCと研究室のPCの両方で競プロを行っていますが，どちらでもすぐに全く同じ環境で競プロをできるので楽です．
競技プログラミングは役に立ちますか？
以下に示すのはあくまで私個人の感想です(予防線)．
競技プログラミングは研究の役に立ちます．実験結果に離散フーリエ変換の処理を施したり，bfsで粒子解析のようなことをやってみたり，といったちょっとした処理を，心理的な抵抗なく行うことができるのは競技プログラミングをやってきたおかげでしょう．また，なにか行いたい処理があったときのために，計算量解析の概念を習得できたのはよかったと思っています．
ただし，(非情報系の実験系の研究を行うにあたっては)緑コーダーくらいの実力で充分だと思います．無論コーディングの速度やバグ取りの精度など，コーディングスキルが研究の高効率化に寄与する面はありますが，研究のことだけを考えたら，緑→青になるための精進を行う時間で論文を読んだり他の実験をしたりしたほうが有益だと思います．
競技プログラミングは就職の役に立ったような気がします．多くの機電系の例にもれず推薦が充実していたのでn=1ですし，非情報系企業相手でしたが，そこの面接で語った競技プログラミングの経験や，それによって身につけたことの話は面接官に好印象だったように思います．まあぶっちゃけ，それがクリティカルに合否に作用したかどうかはわかりません． 研究内容が実学の極みだし，それに絡めた志望動機を示したので，そっちのウエイトが圧倒的に大きかった気がします．
競技プログラミングがその他の役に立つかはわかりませんが，娯楽としてとても楽しいし，コミュニティが非常に魅力出来なので競プロに出会えてよかったと思います．
これから
わかりません．飽きるまで続けていこうと思います．
おまけ
青コーダーになるまでに自分が習得したアルゴリズムについて
あまりに雑多になってしまったので，本文に乗せるのをやめました．
ぶっちゃけE869120さんの記事を読みましょう(https://qiita.com/e869120/items/eb50fdaece12be418faa)で終わりなのですが，一応自分の感覚について記しておこうと思います．
蟻本に記載されているものを主として，各アルゴリズムについて，以下の4つに分類してみます．
①青になるにはほぼ必須だと思う/確実に使うことができる
②それを使った問題を解いたことがある/できれば覚えておいたほうがよい気がする
③知ってるがほとんど使ったことない
④知らない・使えない
①青になるには必須だと思う/自分は確実に使うことができる
- next_permutation
- メモ化再帰
- DP(一次元DP，ナップサック，区間DP，bitDP EDPCでいえばA～G)
- set, multiset, map
- union-find
- DFS/BFS
- ダイクストラ・ベルマンフォード・ワーシャルフロイド法
- トポロジカルソート
- 累積和，imos，しゃくとり法
- ユークリッドの互除法
- modint
- 繰り返し二乗法
- 二項係数を素数で割った余りの計算
- 二分探索
- 後退解析
②できれば覚えておいたほうがよい気がする/自分はそれを使った問題を解いたことがある
- BIT(fenwick-tree)
- セグメント木
- 最小全域木
- ①に記さなかったDP(木DPや確率DP,ゲームDPなど EDPCでいえばH～O)
- 遅延評価セグメント木
- 半分全列挙
- 最大流，最小費用流
- 二部グラフ判定
- 最大流を用いたマッチング
- 座標圧縮
③なんとなく知ってるがほとんど使った記憶がない
- Grundy数
- バケット法・平方分割
- ダブリング
- LCA
- 行列累乗
- 文字列アルゴリズム(Z-アルゴ，ローリングハッシュ，suffix array)
- 2-SAT
- エラトステネスの篩
- 強連結成分分解
- 乱択
④知らない・使えない
