ABC036 大小関係を保持したままデータを圧縮する操作を座標圧縮（座圧）と呼ぶようです。けんちょん本６章の章末問題6.1にでてきましたが、まだ解説がないので自分で考えてみました。座圧でぐぐったらABC036がでてきて、これはまさに座圧でした。C - 座圧 素…

はじめに A問題 B問題 C問題 D問題 E問題 F問題 終わりに はじめに 2020年12月19日21:00-22:40 パナソニックプログラミングコンテスト(ABC186）に参戦しました。結果は34:50 ノーペナ４完で2197/6238位、パフォーマンス961でレーティングは前回798から+18の8…

はじめに 2020年12月13日21:00-22:40 ABC185に参戦しました。 62分12秒 4完ノーペナで2734位 /7478人中 パフォーマンス897でレーティングは+11の798となりました。前回ARCで茶落ちしており、今回は緑復帰を目指すもわずかに足りませんでしたが手応えのあった…

はじめに A問題 B問題 C問題 D問題 提出コード E問題 終わりに はじめに 2020年1月22日21:00-22:40に開催されたABC184に参戦しました。結果は102分53分3ペナABCD４完で1761位／7822人、パフォーマンス1202でレートは+55となり800に。３度目の入緑となりまし…

はじめに longrunさんが立ててくださった＜EDPC+αを再帰で解く＞というバチャに参加してみました。https://kenkoooo.com/atcoder/#/contest/show/2c951dcc-fd87-4369-ac6e-9ed5b91ce271 学んだこと そもそもDPの問題が再帰で解けるという感覚がなかったので…

2020年11月21日21:00-22:40 ARC108に参加しました。5分17秒1完ノーペナで2719位、パフォーマンスは620でレーティングは13下がって745になりました。A問題はわりとすぐに解法に気づき，すんなり実装できてよかったです。B問題，いろいろ工夫してみましたがど…

問題 D - Digits Parade？が混じったN桁の数（N 考察 i番目までの数で13で割った余りがjのものの数をdp[i][j]としてDPを回します。 ?の場合は０～９までを入れて回します。１桁目（i=0)のところを工夫しました。 提出コード #include <bits/stdc++.h> using namespace std; </bits/stdc++.h>…

問題 A - Count Triplets 感想 愚直解でTLEだしたあと、真ん中を動かしながら前後の数をカウントすればO(N＾２）で解けることに気づいた。自力で解けたのがわれながら進歩したなと思ってる。 提出予定コード #include <bits/stdc++.h> using namespace std; int main(){ int</bits/stdc++.h>…

問題 B - エターナルスタティックファイナル文字列Sをn個の文字列Tの組み合わせでつくる場合の場合の数を求める問題です。 考察 Sのi番目までの組み合わせの数をdp[i]とおいて，動的計画法で求めることを考えましたが，遷移式をうまく立てられませんでした。…

はじめに 2020年11月15日21:00-22:40 ABC183に参戦しました。48分10秒で４完ノーペナでパフォーマンスは986でレートは29あがって758になりました。最近５回レートの単調減少が続いていたので久しぶりにあたたまってよかったです。 ただノーペナで解けたとこ…

永久にバグがとれません。 後日改めて検討します。PAST 1-GG - Division #include <bits/stdc++.h> using namespace std; int N; int M=3; int P[10][10]; int ans=0; int maxans=0; void dfs(vector<int>A){ if(A.size()==N+1){ ans=0; for(int i=0;i</int></bits/stdc++.h>

もう何度も書いたからソラで書けるはずと思いつつ，二次元配列のvectorの書き方に少し戸惑って見たりする。どうしてこんな面倒な書き方になるのだろう。世間ではよくchimin,chimaxという関数をつくってやっているけど，そのような関数を作る意味がよくわから…

https://atcoder.jp/users/chacoder/history/share/abc182 11月8日21:00-22:40のABC182に参戦しました。 ３完でパフォ662、レートは736から7下がって729でした。このところ単調減少が続いていて心が沈みますが、明日を信じて精進を重ねていきたいと思います…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jpグリッド内の島の数を求める問題です。 蟻本にあったLake Counting(POJ 2386）と同じですね。 考察 再帰DFSで書きました。 縦横を間違えがちなので注意して実装しました。 提出…

問題 C - 755N以下の７５３数を出力する問題です。けんちょん本４章章末問題です。 考察 再帰によるDFSで書いてきました。 生成した数，３，５，７を使ったかどうかどうかを示すフラグを引数にしました。TLEするのとWAするケースがあります。更に考えてみる…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=jaDFSの基本ということですが悩みながら実装しました。 再帰を使うとシンプルに実装できてよかったです。どこで時間が加算されるのかが難しかったです。 提出コード #includ…

CSESについて CSESはフィンランドの競プロサイトで問題セットとオンラインジャッジがあります。CSES この書籍で紹介されていました。 2017_Book_GuideToCompetitiveProgramming 問題 Your task is to count for k=1,2,…,n the number of ways two knights ca…

前回ABCのEにトライしました。各要素は難しくないのですが多数の配列の添え字を破綻なくまとめきるのには相当力が要ります。 #include <bits/stdc++.h> using namespace std; int main(){ int N,M; cin>>N>>M; vector<int> H(N); vector<int> W(M); for(int i=0;i<N;i++){ cin>>H[i]; } for(int i=0</n;i++){></int></int></bits/stdc++.h>…

ここのところスランプを感じてます。本業でとびきり重たい事件に忙殺されてることもあって，精進も上滑りだし，コンテストは冷えるしなのですが，ほそぼそ精進と勉強は続けています。精選がDFSやBFS，個数制限なしナップサックなどが頭が回らなくて厳しく詰…

はじめに 2020年11月1日21:00-22:40に開催されたABC181に出場しました。 5分42秒2完ノーペナでパフォーマンスは300，レートは41下がって736になりました。 A問題 偶奇の判定だけの簡単な問題です。 しっかりチェックして提出し1分29秒。 B問題 これも比較的…

精選のDFS,BFSのところは厳しいので後回しにしました。DPの34,35を解きました。けんちょん本は再帰のところに入ってユークリッドの互除法を書いてみました。 #include <bits/stdc++.h> using namespace std; int euc(int n,int m){ if(m>n){ swap(n,m); } if(m==0) return n</bits/stdc++.h>…

はじめに 2020年10月31日21:00-22:40に開催されたARC107では2完1ペナ80分02秒でパフォーマンスは757、レーティングは3下がって777になりました。少し冷えましたが目標の２完ができ，手応えがあった回でした。 A問題 式変形はすぐにできましたが割り算がでて…

DFSの基本ということですがまだ理解が追い付いていません。 もう少し勉強します。 問題 https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_11_B 考察 最初に訪問した時間とその頂点に戻ってきた時間を記録する，ということですが戻ってきた時間をどう記録し…

問題 C - 収集王 検討 10^6*10^6と非常に大きな領域だけどデータセットは10^3以下なので必要なところだけ計算することを考えましたが，まだTLEします。また，飴のあるマスは縦横に二重にカウントしているので，その部分を調整することを考えました。しかしWA…

問題 https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=6 ダーツを４本まで投げ上限Mを超えない得点の最大値を求めます。 得点はP[N]でN 考察 普通にループを回すのでは1000^4=１兆になりとても間に合いません。 二分探索のパワーを…

問題 D - 射撃王非常に難しくて詰まりました。この手の特殊な関数を立てて二分探索する問題をたまに見ますが，二分探索の応用範囲の広さを感じます。 解説AC 解説見てもなかなか理解できませんでしたが，他の人の提出コードを参照しながら概ね理解できました…

問題 数列Tに含まれる要素の中で数列Sに含まれる要素の個数を出力する問題です。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=ja 考察 基本通りの二分探索で実装しあっさりACしました。 #include <bits/stdc++.h> using namespace std; int bi</bits/stdc++.h>…

問題 チェス盤に互いに干渉しないように８つのクイーンを配置する問題です。有名な問題のようです。すでにいくつかクイーンが置かれている入力に対し，１通りだけ配置可能な組み合わせがあります。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id…

問題 考察 ACしたコード 問題 C - Count Order 考察 辞書順で出力するのにどうしようか悩みましたがnext_permutationがそもそも辞書順で次の順列を出力する関数なので心配無用でした。配列の比較がシンプルにできるのに改めて気づきました。 最初は要素を１…

問題と考察 WAしたコード 考察 ACしたコード 精選を順番に解いています。 bit全探索も大詰めに来ました。 問題と考察 色の違うビルが直線上に並んでいます。 うしろのビルは，前のビルよりも高くないと見えません。正面から見てK色以上の色が見えるようにす…