日本語によるプログラミングコンテスト
どーもとんきちです。 今回はC言語の参考書一冊終えての感想はなしてこーと思います。 いやー、やっと終わった！！！！褒めて！！！ 学生時代に勉強していたとはいえやはり一冊終わらせるのは根気がいりますね。 まだ基礎の部分だけですがスキルは身についたんじゃないかなと思います。 勉強に使った本はこちらですね。 新・明解C言語 入門編 (明解シリーズ)作者:柴田 望洋発売日: 2014/08/09メディア: 単行本 学んだ内容を全てブログに書くのを断念したおかげで、割とすいすいっと取り組めました！結果としてはよかったかな〜。 せっかくなので特に難しかったポイントをご紹介しようと思います。 やはり「ポイン…
2018年に書いた同タイトルの記事の2020年版です．競プロを始めるにあたって知っておくと良いことのまとめです． 競技プログラミングって何？ 端的に言うと，プログラムを書いて数学パズルを解くeスポーツです．競技プログラミングの大会(コンテスト)では，難しい問題を速く解けると高い順位が得られます． どんな問題が出るかを知りたい方はAtCoder Beginners Selectionを確認してみましょう． 主なプログラミングコンテスト オンラインを中心に様々なコンテストが開催されています．メジャーなプログラミングコンテストを紹介します． AtCoder 日本最大級のプログラミングコンテストサイト…
AtCoder Beginner Contestの過去問から、その提出コードの解答例です。 AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。 atcoder.jp プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。 「競技プログラミング」を略して、「競プロ」などと呼ばれています。#C - Attack Survival atcoder.jp僕が作成、提出したコードは、以下のとおりです。 /* AtCoder Problems in C++ #C - Attack Survival https://…
朝にAtCoder解く習慣ができてきた 人生のリソースを何に使うのが良いのか、悩むことが多い日々 やったこと ・競技プログラミング ABC057B Checkpoints：ループ回して解くだけ ABC024C 民族大移動：何気なく解いたけど、これが貪欲法かぁ ・安全なWebアプリケーションの作り方 4.14:構造化データの読み込みにまつわる問題 evalインジェクション攻撃：外部から送り込んだスクリプトを実行。evalを用いることがそもそも危険 バイト列にしたデータをもとに戻すデシリアライズ処理にも危険性があるため、JSON形式によりデータを受け渡すことを検討したほうが良い XML外部実体参照…
numpyで簡潔に書けたり劇的に高速化できたりする問題一覧 競プロでPythonを使っているが、numpyをあまり使っていないという人はやってみるとnumpyの効果を実感できると思います。 D - Knapsack 1 典型的なナップサックDP。Pythonで愚直にfor文を回すやり方では間に合わないが、numpyを使ってfor文を減らすと劇的に高速化できる例。また、numpy.maximumで２つの配列の要素を比較していき、大きい方の要素を選んだ配列を作ることができる。 Submission #14017275 - Educational DP Contest D - Lamp こちらもKn…
// 問題リンク 初めて解説記事を書くので至らぬ点もあると思いますが、よろしくお願いします。では、行きましょう。 まず、とを逆にしても結果は変わらないので、以降はとなるようにされているとします。 ステップ1 反復回数の最大値 反復回数が回となるようなペアを列挙して(ただし、ペアのつめの要素がつめの要素より小さいとします)した時に一番先頭に来るペアが、反復回数が回となるペアの中でつめの要素が最小(した時点でこれは満たされる)かつつめの要素が最小だとします。 この時、反復回数が回となるようなペアの中で一番小さいペアをとすると、反復回数が回となるようなペアの中で一番小さいペアはです。 このような性質…
問題 E - Balanced Path コード Submission #14018954 - AtCoder Beginner Contest 147 解法 左上のマスから右下のマスまで移動した際に、通ったマスに書かれている2つの数の差の絶対値を足すか引くかした値の絶対値をとすると、の最小値を求めたい。 これは、マスまでにの値をにすることができるかというbool値をとして管理すれば求めることができる。 遷移としては、がtrueの場合、次のマス（ または ）は、次のマスに書かれている2つの数の差の絶対値をとすると、、、のときtrueとなる。 計算量は、 感想 安定の解説ACではあるが、競プロへ…
はいatcoder.jp 任意のAの値を選択して変更することが可能。従って、Aの配列を予め昇順ソートしておき、小さい値から書き換えを行い、書き換えができなくなった時点で操作を終了すればよい。書き換えは貪欲的に、すなわちAの最小値を残っているCの値の最大値で書き換えてゆく。このことから、Cの値についての降順ソートを行うと楽(別に昇順で、逆から線形探索でもよい)。まとめると、ソート完了後のAの配列の先頭からi番目まで書き換えた場合、i+1番目が最小値であるので、その値が(ソート済の)Cのi+1番目(Bの値を考慮して)の値より大きいか否かというところである。 プログラムコードは以下の通り #incl…
備忘録
