AtCoder
atcoder.jp 昨日のD問題，このレベルは本番で出ても難しい． 解答だけ見ると真新しい知識はないんだがビット系の問題はどこから取っ掛かりをつければ良いか勘がつかめていない． 回答時の方針 本番中に提出したのが以下のコード． Submission #15177835 - AI…
整数にもう少し馴染みたいという気持ちからまとめてみます， 茶とか緑レベルくらいまで通用しそうなところまでです． それにしてもdiff800の壁が高すぎる... 今acceptが140だけど200くらいで緑コーダーになりたいが遠そうな感じ． ナイーブ エラトステネスの…
小ネタです． 競技プログラミングでよくやるテク． 容量nの容器に容量dの容器で満たすことを考えたときに何回試行が必要かみたいな問題で使えるテク． 愚直にやると(long long)/(long long)と(double)(long long)/(double)(long long)の比較をするみたいな作…
atcoder.jp エッジケースを通すコードを書く技術がまだまだ足りない． ネストが深くなったり変数定義が増えるときは大体考察が足りていなくて，そういうときはアクセプトしない． ネストを浅くしたり変数定義を減らせばアクセプトするのは事実だと思うが，そ…
atcoder.jp リハビリっていうほど元々すごいわけでもないけど レポート提出が落ち着いたのでリハビリがてら解きました diff 795 Total Accepted 122 回答時の方針 最近関数型言語に触れていたこともあり再帰脳で全探索しにいってしまった,当然間に合わず. Su…
atcoder.jp ギョームでも取り扱いそうな問題. diff 855 回答時の方針 Submission #12993816 - AtCoder Regular Contest 042 まずは全探索. 愚直にやると書き込みがあったスレッドのインデックスを0にしてそれ以外のインデックスを+1する,これをm回繰り返せば…
atcoder.jp diff 836 回答時の方針 Submission #12909261 - Sumitomo Mitsui Trust Bank Programming Contest 2019 N個の数字の中から3個選んで3桁の数字を作ろうかと思ったがとなり筋が悪そうだと思い別の方法を検討した.暫くして3桁としたときにN個の数字…
atcoder.jp 回答時の方針 Submission #12828298 - AtCoder Beginner Contest 125 最初に全探索を考えたの符号を反転する/しない操作をの範囲で行うと計算量はで間に合わない.次に局所的にの反転操作を考えたときにのときに反転が必要だと思った,これをi=0か…
atcoder.jp 毎回至らなさしか感じていないが圧倒的にこなしてる数が足りていないので粛々と向き合い続けるしかない. 道具としては一度くらいは触ったことがあるものでもセンスが良いほうでもないので応用が効かず解法を覚えていくしかないように思う.とはい…
C - Digits in Multiplication 久々に頭悪すぎて涙出そうになった... 初手の方針 Nを素因数分解してA,Bの桁数の差が最小になるように貪欲に取っていけばいけるかなと思った. 制約もなので素因数分解の計算量はで十分間に合う. Submission #12467047 - AtCode…
今400の茶コーダー. 緑コーダーがレート800-1200. AtCoder Rating Simulator 5回連続で1200パフォでやっと緑. 1200パフォにはABC161を参考にするとDifficulty1100のD問題を開始1時間くらいまでに解く必要がある. ということで早解は得意じゃないのでA-Cまで…
atcoder.jp 高校のときから整数問題苦手だったんだけど10年以上経って改めて苦しめられている... ちなみに4月中に茶色くらいはいけるだろうって言ってたのはなんとか滑り込みで今回達成しました. 初手の方針 そもそも整数問題っていうことに気づかなかった. …
atcoder.jp ABC147-C,ABC159-Eについで3度目のbit全探索が題材 初手の方針 N,Mが最大で10なのでスイッチのon/offパターンは全列挙しても,それぞれの電球が繋がるスイッチを1つずつ走査してもで余裕で間に合いそうということで全探索することにした。 [WIP] …
競技プログラミングでよく見るの余りを出力せよについて, 初めの頃(今も初めの頃ではある...)は32bit,64bitに収まらないから大きめの自然数で割るくらいにしか考えていなかったが組み合わせを求める問題でより深い理解が必要になったのでまとめる. 導入 以下…
atcoder.jp kenkoooo.comのdifficulty同じ数値でも最近の問題と昔の問題で難易度に差があるように感じるんだけど、こんなもんなんですかね 初手の方針 まだ知識がないので少ない中で知っている知識に帰着させようとしてUnionFindで実装しようとした。 が、繋…
atcoder.jp ルートの網羅をどう実装してよいか定まらずめちゃくちゃ手こずった 初手の方針 マス目の . -> # への変化をカウントしようとした。 例えば S[i-1][j] -> S[i][j] で . -> # と変化する場合カウントは count[i][j] = count[i-1][j]+1 といった感じ…
atcoder.jp D問題というか緑レベルの問題にも慣れてきた感はあるんだけど、なかなか解ききるまでは至らずもう少し時間がかかりそう。 初手の方針 0から9までの数字で差の絶対値が1以下になるものをそれぞれvectorで定義する。 あとはK回に達するまで列挙して…
atcoder.jp 初手の方針 総当りで間に合いそうだなと思ったものの実装が全然手つかず。 発想も実装もまだまだ精進が足りないなと感じた。 正答 Submission #11377582 - AtCoder Beginner Contest 159 縦方向をbit全探索しつつ固定して考え、横方向について貪…
atcoder.jp まだ道具としてのcppを使いこなせていないと感じた。 初手の方針 Submission #10661717 - AtCoder Beginner Contest 158 string ac,adにそれぞれ反転したものと反転していないもの両方を常に保持 、stringの連結は+演算子で行う。 業務でプログラ…
atcoder.jp 初手の方針 隣接リストを作ってdfsでカウントするような方針。 グループに属する人数を求めると計算量は(n^ 2)かな？ 今回はnが10^ 5なので間に合わず後述するUnion-Findというデータ構造で工夫する必要がある。 Submission #10513724 - AtCoder …
atcoder.jp 初手の方針 蟻本のDFS/BFSで迷路探索問題は見ていてアルゴリズムはわかっていたが実装力が足りなくて手が出せなかった。 幅優先探索について 幅優先探索の実装において抑えておくポイントみたいなものを記しておく。 以下のような迷路を例にとっ…
atcoder.jp 初手の方針 ぱっと見lower_bound使いそうだなと思ってvectorに詰める方向で諸々思考錯誤した。 最終的に順列Pのi番目の要素p[i]としたときi番目までの集合Piの最小pc[i]がp[i]と一致すればカウントするという方向でコードを書いてLTE。ソート1回…
atcoder.jp かなり明確に方針が立ってそのとおりにコードを書いてAC出せて手応えを感じた問題なので記事にしておく。 初手の方針（＋思考の流れ） とりあえず{1,2,3}のパターンを列挙した。 {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} 同様に{1,2,3,4}のパター…
atcoder.jp cpp力の無さで解けず、 解法わかってるのにコードに起こせないのは凹む。 初手の方針 inputを偶奇で分けてそれぞれ頻度の高いものを比較して差分を出力すればいけそうかなと思った。 が、それをどう書いていいかがわからなかった。 vector<ll> v; REP</ll>…
atcoder.jp 初手の方針 ぱっと見で累積和で解こうとなった、結果的にこの方針は正しかった。 ARC098の問題もそうだが、1次元のある区間の値を求めるような問題は累積和にパターンマッチできるようになってきたように思う。 C - Attention Submission #932035…
atcoder.jp 学生対象だが10歳くらいオーバーしてるおっさんですまん。 初手の方針 今回はスムーズに方針立てられた、 以下2つの転倒数の和の合計を取る。 A中に含まれる転倒数の合計 AkiとAkj,Akj+1...Akの転倒数の合計 入力例3で説明する。 10 998244353 10…
atcoder.jp Brute-force Attack 総当り攻撃が題材の問題。 初手の方針 a,b,cの組み合わせの文字列を全て列挙するということで先日bit全探索を覚えたこともあって真っ先にそれを使えないかなと考えた。 a,bの2種類の文字列であれば0=a,1=bとして全列挙可能だ…
atcoder.jp 相変わらずここでレコメンドされたやつを解いてるわけだが、 教育的に良い問題だと思ったので理解のために記事にすることにした。 https://kenkoooo.com/atcoder#/user/sd08013 1個飛ばしの整数の階乗的なものの末尾の0の個数を求めるというシン…
atcoder.jp ABC147は参加できなかったんだが今年のABCのC問題では一番難しいと一部で言われていた問題。 題材はbit全探索というアルゴリズムでbit全探索で集合の全パターン列挙するというのも慣れていなかったので当然難しかったんだが、正直者の発言が集合…
atcoder.jp 相変わらずD問題が鬼門で時間内に解けず。難易度的には茶くらい？ 今回はシステムに問題があってunratedになるらしい、参戦して初めての経験である。 時間内に提出したのが以下のコード。 提出した段階での方針は K個前に同じ手を出していなけれ…
