AtCoder Beginner Contest 186 (パナソニックプログラミングコンテスト) (ABC-186) E - Throne についての記事です． 問題へのリンク atcoder.jp ABC-186 E Throne 解法 全体で必要なステップ数は， Kの倍数であって (つまり，mod K で 0 である) mod N で -…

AtCoder の ACL Beginner Contest E - Replace Digits についての記事です． 問題へのリンク atcoder.jp 経緯・考えたこと コンテストのときには，この問題を解き始める時点でまだ80分以上残っていたのに，結局ACできませんでした．想定解は遅延伝搬セグメン…

2009 JOI 予選6 ビンゴ についての記事です． 問題へのリンク (AtCoder) atcoder.jp 上のリンクで問題は見られますが，要は，$n$, $m $, $s$ が与えられた時， 以下を満たす数列 $\{a_i\}_i $ の個数を求めよ，というものです． 制約は，$1 \leq n \leq 7$, …

Codeforces Global Round 10 G. Omkar and Pies についての記事です． 問題へのリンク codeforces.com 経緯 全然見当もつきませんでした．editorial を読んですごく勉強になったように思います． 解法 以下，ほぼ editorial のまま． まず，「1をできるだけ…

AtCoder Beginner Contest 175 (ABC 175) D - Moving Piece についての記事です． 問題へのリンク atcoder.jp 解法 $i \to P[i]$ にリンクがある有向グラフだと思って，連結成分 (といってもサイクルだが) ごとに考える． ループを回ってプラスのときに，端…

問題へのリンク atcoder.jp 状況 2020/08/15 のあさかつで出題されました． 他の問題で時間がかかって，この問題まで手が回りませんでした． この問題自体は，コンテスト時に解けていましたが，実行時間がだいぶかかりました (1.3秒)． 解説 を斜め読みした…

AtCoder Beginner Contest 011 D - 大ジャンプ に関する記事です． 問題へのリンク atcoder.jp 状況 2020/08/07 のあさかつで出題されました． 解けたつもりでしたが，時間内にはコードが書ききれませんでした． その後も考えたところ，結局，解けてはいなか…

解説ACしたその解説がよくわからなかったので，自分なりに書き直したものです．

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); 問題概要 問題ページはこちら． 与えられる整数 $N$ に対し， 以下を満たす 整数 $s_1,s_2,n_1,n_2,u_1,u_2,k_1,k_2,e_1,e_2$…

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); 問題概要 4整数 X, P, A, B が与えられる．P は素数．$1\leq X < P < 2^{31}$, $0 \leq A \leq B < 2^{31}$. $X^i \,\%\, P$ …

AtCoderでは C++ で boost が使えるので，多倍長計算をすることができます． ヘッダ部分 先頭付近に次のように書いておきます．(競技プログラミングなので，これで良いことにしてください．) #include <boost/multiprecision/cpp_int.hpp> // 整数を使う時 #include <boost/multiprecision/cpp_bin_float.hpp> // 実数を使う時 using nam</boost/multiprecision/cpp_bin_float.hpp></boost/multiprecision/cpp_int.hpp>…

競技プログラミングの文脈の話です．std::lower_bound() と std::upper_bound() の使い方がなかなか覚えづらく，使いづらい印象があります．自分で二分探索を行う関数を書いておいて貼り付けた方が楽ではないか，という趣旨の話を書きます． 以下，次のよう…

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); AtCoderサイトの問題ページはこちら． 問題概要 縦 $x$ 本横 $y$ 本の道路が碁盤状にある街で，左下の地点から右上の地点まで…