AtCoder

AtCoder Beginner Contest211のC問題についてPythonの解答例を記事にしていきます。 AtCoder Beginner Contest 211 - AtCoder AtCoder Beginner Contest211 C - chokudai C - chokudai 問題文 文字列 S が与えられます。 このうち 8 文字を選び下線を引き、下線を引いた文字が左から順に c , h , o , k , u , d , a , i となるようにする方法は何通りありますか？ ただし答えは非常に大きくなる可能性があるので、(109+7) で割った余りを出力してください。…

AtCoder 競プロ典型 90問 027 Sign Up Requests 簡単 028 Cluttered Paper いもす法だと思ったけど2次元なのもあって解けなかった ABC 211 Dがわかりそうで実装全然できず 解けなきゃいけない問題だったっぽい…… 辺の重みが等しいときの最短経路問題はBFSでいいのか…… というかBFSの理解が浅い……

AtCoder Beginner Contest211のA とB問題についてPythonの解答例を記事にしていきます。 AtCoder Beginner Contest 211 - AtCoder AtCoder Beginner Contest211 A - Blood Pressure A - Blood Pressure 問題文 収縮期血圧 A と拡張期血圧 B が与えられます。 平均血圧 C を求めてください。 ただし、平均血圧は以下のように定義されるとします。C=A−B / 3+B 制約 ・50≤B≤A≤300 ・入力に含まれる値は全て整数である 解答例 a, b = map(int…

Eは勝敗の判定条件を間違っていたり、ループがあると解けないと解き方をしていたりしていました。カウントの更新時に勝敗を交信するという発想が無かったので解けなかったと思います。(1915->1922) scrapbox.io scrapbox.io scrapbox.io

ABC212から問題数が従来の6問から8問に増えます！！ はい、今日の第38回あーだこ－だーで発表された内容なので、ほぼ確実だといって良いでしょう 今回の発表では、変更はABCの問題だけです コンテスト時間やレーティング更新対象、その他のコンテストについては変更はありません それでは詳しい内容を見ていきましょう 変更の詳細 問題数:6問から8問に 難易度: ・新A問題(旧A問題):100点、灰 ・新B問題(旧B問題):200点、灰 ・新C問題(旧C問題):300点、灰～茶 ・新D問題(旧D問題):400点、緑 ・新E問題(旧D問題):500点、水 ・新F問題(旧E問題):500点、青 ・新G問…

AtCoder Beginner Contest210のD問題についてPythonの解答例を記事にしていきます。 AtCoder Beginner Contest 210 - AtCoder AtCoder Beginner Contest210 D - National Railway D - National Railway 問題文 高橋王国は H 行 W 列のグリッドで表されます。北から i 行目、西から j 列目のマスを (i,j) で表します。このたび、高橋王国の国民から交通の利便性のために鉄道の建設を求める声が多数寄せられ、国王の高橋君は鉄道を建設しなければならなくなりました。 鉄…

問題：F - Coprime Solitaire きちんとした解法や証明は公式解説で。ここでは主に計算量削減パートをメモ。多分、解説動画でsnukeさんが最初にACした方針。 ・解法の大まかな流れ ① すべてのカードの表と裏を頂点としたグラフを考える（つまり頂点数がカード枚数の２倍になる） ② 「頂点uを使ったら頂点vも使わなくてはならない」という関係を有向辺u→vで表す ③ 強連結成分分解(SCC)をして、同一成分内に同じカードの表と裏が含まれていなければ"Yes"、含まれていれば"No" ここで問題となるのが②。問題の条件より 頂点のうち、使えるのは1つ という状況が生まれる。頂点の反対の…

07/19(月) 午後3時くらいに目を覚ます。TLにチュウニズムのアップデート情報が流れてきた。8/5の更新で、CRYSTALのマップ全部とイロドリミドリのマップが1つ消えるらしい。CRYSTALはラスボスのマップが残っていて、イロドリミドリのマップは手つかずなので、都合1500マスくらい走る必要がありそうだ。非常にまずい。 先週のARC123Cについて、実は操作回数は最大でも5回らしい。かなりびっくり。僕は60回で見積もって、これだとちょうどlong longに詰め込めるから簡単で、うまい問題だな～と思っていたのだが……。 TLを眺めたりYouTubeアプリで動画を見たりした後、また寝た。次…

問題 atcoder.jp 考え方 よくある釣り銭を求める問題に近いもの。 500円の方が幸福度が高いので、まず500円何枚が充当可能か計算し、余った額を5円で割り算して幸福度の全体を求めることになる。 本問では「500円」と「5円」の組み合わせだけ判定すればOKなので、それ以外の硬貨（100円、50円、10円、1円）については全く考えなくて良い。 解答例 ABC160 B - Golden Coins

コンテストやバチャ等での失敗を懺悔します 一般的な話 部分問題(や,制約を弱めた版)ですら,これでしか解けない → それに近いアルゴリズムを使う 例題: atcoder.jp 最適化関連 gcdは,一つ決めれば候補はその約数のみ $ 10 ^ 9 $ 以下の高度合成数の個数は $1344$ 個 例題: atcoder.jp 最適化であっても,最終形の判定問題を最初に考えるとうまくいくことがおおい. 例題: atcoder.jp atcoder.jp 絶対値の最大化 は max$(x,-x)$ の最大化で言い換えるとうまくいくことが多い. atcoder.jp atcoder.jp 計算量関連 …

今スプリントの感想 すいません。ふりかえりが出来ていませんでした。 もうちょっとサクッとした感覚で進められるようにしよう 今年の目標確認 毎日本の感想をツイート LeetCodeのTシャツゲット 蟻本やりきり+AtCoderの補題 Rust(本2冊やりきり) コンピュータの理論と実践やりきり ゼロから始めるOS入門をRustでやりきる STMをRustで操作を増やす Akka本をやりきる 英語を一日一時間 カンファレンスに去年よりも参加 ふりかえり：ORID O: Objective、事実 毎日本の感想をツイートできなかった ちょっと中だるみ感 読んでサクッと感想を書くって感じでやっていこう …

2完3WA2TLE。 各問題 A - LR Constraints n * k のマトリックスを作って、条件にそって絞り込んでいって最後に集計すればよいです。 B - XOR Matching 2 候補となり得るのはたかだかn個です。a_1に対してbのxorを取ったものを候補として全探索し、ある候補がすべてのb_iにたいして現れていればxとなりえます。 C - LCM of GCDs 素因数分解すれば、案外組み合わせの候補数は少なくなりそうだということはわかりましたが、それをどう探索すればよいかがわからず。 まとめ 【速報】弊社の新卒氏にAtCoder初敗北かつおぶしは君に任せたｗ— Toy …

何の話かと言うと atcoder.jp上記の問題をネタに、ナップサック問題の計算量に関するちょっとした考察をしてみます。 「しらみつぶし」がナップサック問題の基本 問題をパッとみて、ナップサック問題に似ていますよね。まず、下記の記事で、ディクショナリーを使ったナップサック問題の解法を確認してください。enakai00.hatenablog.comこの記事では、 今回のケースでは、それぞれの荷物について、「入れる」「入れない」の二択の判断が入ることになります。実際にナップサックに入り切るかどうかは別にして、・1個目の荷物を入れない場合 ・1個目の荷物を入れる場合の結果を記録して、その結果に基づい…

問題 atcoder.jp 考え方 1 ≦ A ≦ 1000 程度なので、 for ループで Aを回しつつ、各要素が問題文の条件である得票数が総得票数の 1 / 4M 以上 であるか判定すれば良いと考えた。 解答例 ABC161 B - Popular Vote

自分について 黄色達成までにやったこと 1.コンテスト参加 2.精進 3.知識 4.その他 これから 競プロerのN_haraです。AtCoder Beginner Contest 211 において黄色コーダーとなりました。記念(あるいは備忘録)として以下、主にAtCoder青色達成から黄色到達までにやったことなどを振り返りたいと思います。 青色になるまでにやったことについてはこちらの記事に書いてあります。 n-hara.hatenablog.com 以下、黄色達成時のデータです。 自分について 北海道大学M1のN_haraといいます。自分のプロフィールをまとめると 学科は情報系(学部も) 研…

こんにちは、キム太郎です。 昨日、初めてABCに参加しました。 これで自分も「プログラム、カイテマス」て言える気がして嬉しいです （業務ではExcelいじってばかりなので）。 「400点越えられたらいいな」と思い、目標はC問題まで完答としました。 準備はAtCoder Beginners Selectionを解いておきました。 でもって結果は300点（A、B問題完答）でした。 B問題まではサクサク解いていったのですが、見事にC問題で躓きました。 力技でなんとかなるっしょ！とfor文をネストさせまくったのがダメでした。 というかそもそもC問題は、動的計画法を使って解く問題とのことでした。 「動的…

問題 atcoder.jp 考え方 例にある通り、3の倍数（Fizz）、5の倍数（Buzz）、3と5の公倍数（FizzBuzz）以外の数字を合計してあげればOK。 今回は for ループで回しても間に合う程度の計算量なので、 range(1, N+1) を生成し、 FizzBuzz を if 文で判定して解答を求めた。 解答例 ABC162 B - FizzBuzz Sum

AtCoder Beginner Contestの過去問から、その提出コードの解答例です。 AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。 atcoder.jp プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。 「競技プログラミング」を略して、「競プロ」などと呼ばれています。#B - Cycle Hit atcoder.jp僕が作成、提出したコードは、以下のとおりです。 /* AtCoder Problems in C++ #B - Cycle Hit https://atcoder.jp/c…