競技プログラミング

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要ラベル付き頂点のパスグラフから頂点を削除していく. 頂点をつ削除するたび連結成分の個数の点数を得る. 通りの削除の仕方すべての点数の総和を求めよ.思考の流れ 連結成分の数というのは数えにくい. パスグラフは木の一種であるのでABC173 F - Intervals on Treeと同様に考えると, 「頂点削除後の残りの頂点の数の総和」から「頂点削除後の残りの辺の数の総和」を引けばよい.「頂点削除後の残りの頂点の数の総和」は削除の仕方によらず「頂点削除後の残りの辺の数の総和」はのとき各辺の寄与分を考えると, つの辺につきよって答え…

AtCoder キーエンスプログラミングコンテスト2021のA問題の解答例を記載していきます。 KEYENCE Programming Contest 2021 - AtCoder A - Two Sequences 2 A - Two Sequences 2 問題文 すぬけ君は長さ N の数列 a,b を持っています。 a,b の i 番目の数はそれぞれ , です。 すぬけ君は a,b を使って長さ N の数列 c を作ることにしました。 1≤n≤N を満たす n について、c の n 番目の数 は 1≤i≤j≤n を満たすような (i,j) について を計算したときの最大値です。より形式的…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点辺の有向グラフの頂点からちょうど本の辺を辿って行くことのできる頂点の個数を求めよ.思考の流れ yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を乗した行列の成分は「頂点から頂点まで本の辺を辿っていく経路(ウォーク)の数」となる. よって, 隣接行列を乗した行列の行目の以上の成分の数が答えとなるが単に乗するとオーバーフローするが以上であるものはとして計算しても今回の答えは変わらない.提出プログラムhttps://yukicoder.me/submissions/606002感想No.1339の方がキツ…

はじめに 書くつもりはなかったが，公式解説がないようなのでメモ程度に書いてみることにした． 問題 ARC013 B - 引越しできるかな？ 解法 各荷物の3辺において必ず １番長い辺 ２番目に長い辺 3番目に長い辺 が存在する（同じ長さがあれば，それらの順位付けは勝手に決めてよい）． 荷物について ： １番長い辺 ：２番目に長い辺 ：３番目に長い辺 として， [ tex: l_ {i} , m_ {i} , n_ {i} ]の最大値をそれぞれ求めて，それらを3辺の長さとする箱が必要である． （数式表示がうまくいきません，ごめんなさい） 実装 C = int(input()) l_max = 0…

AtCoderを始めたばかりのころ どのように標準入力を取得していいかわからず苦戦していました。本当はプログラムの内容を考えたいのに、標準入力でつまづいてしまうとおもしろくないですよね。そんないやな思いをする人が少なくなるよう、AtCoderで使っているPythonの標準入力の取得方法を記事にしていきます。 標準入力とは 競技プログラミングの問題の条件みたいなものになります。例えば、「1個100円のりんごをx個買いました。支払う金額はいくらですか？」みたいな問題では、xによって金額が決まります。 競技プログラミングではxが何パターンも用意されていて、その条件を読み込み すべてのパターンで解答が…

今日も "初中級者が解くべき過去問精選 100 問" を解いていきたいと思います！ 精選100問って何？ 過去の記事についてはこちら！！ 第１回：全列挙 第２回：工夫して通り数を減らす全列挙 第３回：ビット全探索 第４回：順列全探索 第５回：二分探索 第６回：深さ優先探索 幅優先探索 28. Breadth First Search 29. C - 幅優先探索 30. E - チーズ (Cheese) 31. E - イルミネーション (Illumination) 32. Amazing Mazes 33. D - Grid Repainting 最後に 精選100問って何？ 記事はこちら！ …

2021/1/10に開催されたAtCoder Beginner Contest 188に参加しました。 atcoder.jp 前日に行われたARC111は0完という残念な結果で、緑転落ギリギリのレーティングまで落とされてしまいました。今回は、このマイナスを少しでも取り戻そうという気持ちで臨むこととしました。 AtCoder Beginner Contest 188 - AtCoder https://t.co/d3qLakcRGL 参加します。昨日のARC111で0完を喰らった分をすこしでも取り戻すべく頑張ります。— devgenjin77 (@devgenjin77) 2021年1月10日 …

Atcoder Begginer Contest 169 でのキューを使った幅優先探索のメモ atcoder.jp import os, sys, re, math from collections import deque N,M = map(int, input().split(' ')) tag = [-1] * N path_r = {} for _ in range(M): A,B = map(lambda x: int(x) - 1, input().split(' ')) if A in path_r: path_r[A].append(B) else: path_r[A] = …

新年あけましておめでとうございます！！（おそっ）今日も "初中級者が解くべき過去問精選 100 問" を解いていきたいと思います！ 精選100問って何？ 過去の記事についてはこちら！！ 全探索シリーズ 第１回：全列挙 第２回：工夫して通り数を減らす全列挙 第３回：ビット全探索 第４回：順列全探索 第５回：二分探索 深さ優先探索 24. Depth First Search 25. How Many Islands? 26. D - Ki 27. D - 薄氷渡り 最後に 精選100問って何？ 記事はこちら！ qiita.com こんなに丁寧にまとめてくださっている e869120 さんには本当…

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); A問題 B問題 C問題 D問題 感想 Atcoder Biginner Contest 188に参加しました。 atcoder.jp A問題 atcoder.jp XとYのうち小さい数に3を足すと大きい数より大きくなるかどうか つまり、min(X, Y)+3>max(X, Y)となるかどうかを判別する。 XとYの差が3未満と言い換えることができるのでab…

AtCoderのABC188に出場してACをとれたC問題の解答例を書いていきます。 AtCoder Beginner Contest 188 - AtCoder ABC188 C - ABC Tournament C - ABC Tournament 問題文 選手 1 から選手 までの 人の選手がトーナメント形式のプログラミング対決をします。 選手 i のレートは Ai です。どの 2 人の選手のレートも異なり、2 人の選手が対戦すると常にレートが高い方が勝ちます。 トーナメント表は完全二分木の形をしています。 より正確には、このトーナメントは以下の要領で行われます。i=1,2,3,…,N に…

AtCoderのABC188に出場し今回もC問題まで解くことができました。 この記事ではAおよびB問題の解答例を書いていきます。 AtCoder Beginner Contest 188 - AtCoder ABC188 A - Three-Point Shot A - Three-Point Shot 問題文 バスケットボールの試合が行われており、現在の両チームの得点はX対Yです。ここでX≠Yであることが保証されます。 現在劣勢であるチームが、3ポイントシュートを一本成功させて優勢に立つことはできますか？ つまり、現在得点が低い側のチームが3点を得た場合、そのチームの得点が他方のチームの得点…

rate 会社員やりながら色を上げるのは大変だと思いました。しかし、レート確定の瞬間は全てが報われる爽快感がありました。 継続してよかったです。 以下ではこれから黄色を目指す人の助けになるかもしれないことをつらつらと書いていきます。ポエム多めです。

こんにちはPyQマーケティングチームです。 PyQの運営会社ビープラウドは、メンバーの8割以上がエンジニアです。 ビープラウドのメンバーにアンケートを行い、気になる「エンジニアのxx」を聞いてみました。 前回はエンジニアとして働く中での失敗談を聞いてみました。 仕事でミスをなくすことは不可能ですが、注意をすることでミスを減らすことはできます。その方法のひとつとして、日々の学習で技術を身に着けることがあげられます。知識やスキルを向上させることにより、余裕のあるミスの少ない行動につながりますよね。 今回は、エンジニアはどのように情報をキャッチアップし、学びを継続しているのかを知るため、普段の学習方…

はじめまして。Eight Career部のサーバサイドエンジニアをしている大石 奈津子です。 先日、オンラインイベントの Rails Girls Gathering Japan において、スポンサーとしてLTの発表をさせていだきました。 Rails Girls Japanの方々から情熱的なパワーをもらったので、是非イベントの紹介をさせていただきたいと思います。

(この記事は僕がAtCoderで緑色になった直後に書いた記事の再掲です。) この記事では、僕がAtCoderで緑になるためにどんな勉強をしたかをまとめたいと思います。 前半部分では、自己紹介やAtCoderを始めた動機について書いているので、興味がない人は適当に読み飛ばしてください。 自己紹介 工学部の大学2年生です。(達成した当時) 競プロをやっている人の多くは、もともとプログラミングができたり、中学・高校の頃からパソコンを使うことに慣れていたという人が多い印象です。 そんななかで、僕はプログラミングはほぼ未経験、自分のパソコンを持ったのも大学に入ってからという状態で競技プログラミングを始め…

どうも！ 先週の振り返りを書いていきます。 仕事 まだ2週間しかスクラム開発に参加してないですが、スクラム開発に対する感想としては1チームの人数が少ないのであれば、かなり開発がやりやすいです。 スプリントプランニングを通して、各関係者の間で何をどの順番にやるかが決定されるので、開発者としてはどのPBIを進めれば良いのか、時間があまりそうであれば、どのPBIを着手すれば良いかが分かるのが特に良いなと思います。 また、スプリントレビューでお客様にデモをすることで、どういう仕事をしたのか見てもらい、関係者からフィードバックを貰えるのが嬉しいです。 ただ淡々と仕事をすることもできますが、助かった・すご…

仕事の幅を広げるために数字が読めるようにならないとならんな。 数字が読めない意識低い系プログラマの独白。 とりあえず数字を読めるようになるのが先決であろうな。 まとめ あわせてよみたい 仕事の幅を広げるために数字が読めるようにならないとならんな。 数字が読めない意識低い系プログラマの独白。 僕はまぁ、プログラマの仕事を生業としているのだけど、考え方が生まれつき文系の方らしく、数字が壊滅的に読めない。かつて学生だった頃も、数学と英語が壊滅的で倫理や現代文が得意だったという文系人間なのである。哲学的なものに興味を持って大学は心理学科に入った。だが、その頃流行り始めた2chにどっぷりと浸かってしまっ…

ども。転職から3ヶ月目遂に自分でも久方ぶりのリリース立ち会いなどもありドタバダしていた12月。今の職場で感じることは今のJavaScripterのワンライナーは理解できないことが多いことに気がつきました。今の職場は電算システムさんなんですが非常にコードが綺麗。ワンライナー使っていてもコードの流れがわかるんです。どれだけやってもJavaScriptのワンライナーが理解できないはずです。正直言ってガリガリ書いていても分かるリーダブルコード。これこそが本来自分たちが書かないといけないコードなんです。リーダブルコードは若手どころかベテランも進化させれると思いましたね。競技プログラミングだとアピールする…

AtCoderを始めたばかりのころ どのように標準入力を取得していいかわからず苦戦していました。本当はプログラムの内容を考えたいのに、標準入力でつまづいてしまうとおもしろくないですよね。そんないやな思いをする人が少なくなるよう、AtCoderで使っているPythonの標準入力の取得方法を記事にしていきます。 標準入力とは 競技プログラミングの問題の条件みたいなものになります。例えば、「1個100円のりんごをx個買いました。支払う金額はいくらですか？」みたいな問題では、xによって金額が決まります。 競技プログラミングではxが何パターンも用意されていて、その条件を読み込み すべてのパターンで解答が…

こんにちは、 @akira です。本年もよろしくお願いいたします。 2021 年のテックブログ一本目は、競技プログラミングの紹介記事になります。 サンプルコードは Go で記載しています。 競技プログラミングとは 出題されたお題をデータ構造とアルゴリズム（+数学 etc...）を駆使して解く競技です。 実際のコンテストでは制限時間内に難易度の違う問題が複数出題されるので、それらをいかに早く解くかを競います。 例えばこんな問題が出題されます。 自然数 n （1 <= n <= 1000）が与えられたとき、1からnまでの和を求める calcSum() を実装せよ まず naive に brute …

週に一回ぐらいなにかプログラムのアウトプットしたい、と考えてる最近です。 そこで今回はプログラミングブームに乗っかって、初心者向けの記事でも。特にこのブログはほとんど英語関係な気がするのでなにか参考になれば幸いです。 今回のテーマは「プログラミング最初の第一歩」です。

はじめましてこんにちは、あるたいるです。 2021/1/10 の ABC188 でめでたく水色になることができたので、色変記事を書いてみることにしました！ 「競技プログラミング始めたばっかりなんだけど、何すればいいの？」という灰Coderさん🐘から「はやく水色になりた〜〜い！！」という緑Coderさん🌿まで、お役に立てれば幸いです（あるいは「水色なんてとうの昔に過ぎ去ったぜ…」というガチプロさんも、暖かい目で読んでくれると嬉しいです）。 入水！！ 0. 自己紹介 1. 入水への経緯 2. ここまで何をしたのか？ 3. 覚えたテクニック（アルゴリズム・データ構造） 4. あるたいるの「おさえてお…