Code Thanks Festival 2018 G Sum of Cards
問題文
考えること
まず、k種類以上の和で最大化なので、
dp[i][j] = i番目までのカードを使ってj種類の整数を見せているときの合計の最大値
のようなDPを考えたい。しかし適当な順序でカードを見ていっても、そのとき使った整数の種類が増えるかどうかがわからないので、適切な順序で並びかえる必要がある。 そこでカードを(表面の整数)→(裏面の整数)のようにつなぐ有向辺と見てみる。 例えば
N = 4 A = (1, 2, 3, 4) B = (2, 3, 1, 4)
みたいな組み合わせであったらグラフは下のようになる。
この辺たちにDPでうまく遷移できるような適切な順序を考えたい。 カードに現れる整数は表と裏でそれぞれ1回ずつなので、グラフの頂点の入次数と出次数は必ずそれぞれ1つ。 よってある頂点xについて、(xに入ってくる辺)→(xから出ていく辺)のような順序でグラフを見ていけば、xを使うかどうかが判定でき、使う整数の種類についてDPができる。そうすると、知りたかったカード(辺)を見る順序は下のようにループをそれぞれ一周していく形になる。
しかし、ループの最初に見る辺の出ていく側の頂点(図の頂点１のような点)はループが一周するまで使われるかわからないので場合分けによって解決する必要がある。また、DPの遷移中に使う整数の種類が増えるかの判定のために、直前に見た辺でどちら側を使ったかの情報が必要であり、正しいDPテーブルはこの２要素を考慮したdp[i][j][k][l]の形。
このDPの遷移は 見ている辺がループの最初に見る辺なのか、途中なのか、最後なのかによって場合分けしてあげればよい。 具体的には実装を参考
実装
辺の情報にループの最初か最後か途中かの情報を加えて持つと実装が楽。順序付けはDFSすればよくあとは頑張って場合分けしてDPをループで回すだけ。 ただし、DPテーブルの初期値には注意が必要で、i = 0のとき(何もカードを選んでいないとき)、何も選んでないのに1つ以上の整数を使っている場合から遷移するとまずいので
のようにする必要がある。DP配列を使いまわせば空間計算量が下がるし、初期化の時間分速くなるけどめんどくさいのでやってないしやらなくても通る。
#include <bits/stdc++.h> using namespace std; typedef long long ll; void IOS() { ios::sync_with_stdio(false), cin.tie(0); } const ll INF = 1e16; const ll INM = 114514; const ll MOD = 1e9 + 7; template <typename T> void dump(T x) { cout << x << endl; } template <typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill((T *)array, (T *)(array + N), val); } ll dp[5001][5001][2][2]; int g[5002]; bool used[5002] = {}; struct edge { int from, to; //表→裏のような辺 bool first, last; //ループの最初(最後)に使う辺か？ }; vector<edge> e; int main() { IOS(); ll n, k; cin >> n >> k; vector<ll> a(n), b(n); for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { cin >> b[i]; } for (int i = 0; i < n; i++) { g[a[i]] = b[i]; } //DFSで辺に順序付け for (int i = 1; i <= n; i++) { if (!used[i]) { used[i] = true; e.emplace_back(edge{i, g[i], true, g[i] == i}); int d = g[i]; while (d != i) { e.emplace_back(edge{d, g[d], false, g[d] == i}); used[d] = true; d = g[d]; } } } Fill(dp, -INF); dp[0][0][0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (e[i].first) { ll prev = max({dp[i][j - 1][0][0], dp[i][j - 1][0][1], dp[i][j - 1][1][0], dp[i][j - 1][0][1]}); dp[i + 1][j][1][1] = prev + e[i].from; //最初に表を使う dp[i + 1][j][0][0] = prev + e[i].to; //最初に裏を使う dp[i + 1][j][1][0] = dp[i + 1][j][0][1] = -INF; //その他はありえない } else if (e[i].last) { //ループの最初に表を使ったときは最後に裏を使っても種類数は増えない dp[i + 1][j][1][1] = max(dp[i][j - 1][1][1], dp[i][j][1][0]) + e[i].from; dp[i + 1][j][0][1] = max(dp[i][j - 1][0][1], dp[i][j][0][0]) + e[i].from; dp[i + 1][j][1][0] = max(dp[i][j][1][0], dp[i][j][1][1]) + e[i].to; dp[i + 1][j][0][0] = max(dp[i][j - 1][0][0], dp[i][j - 1][0][1]) + e[i].to; } else { //直前に裏を使って表を使う時は使う種類数は増えない dp[i + 1][j][1][1] = max(dp[i][j][1][0], dp[i][j - 1][1][1]) + e[i].from; dp[i + 1][j][0][1] = max(dp[i][j][0][0], dp[i][j - 1][0][1]) + e[i].from; dp[i + 1][j][1][0] = max(dp[i][j - 1][1][0], dp[i][j - 1][1][1]) + e[i].to; dp[i + 1][j][0][0] = max(dp[i][j - 1][0][0], dp[i][j - 1][0][1]) + e[i].to; } } } ll ans = 0; for (int i = k; i <= n; i++) { for (int j = 0; j < 2; j++) { for (int l = 0; l < 2; l++) { ans = max(ans, dp[n][i][j][l]); } } } dump(ans); return 0; }
伸縮箱の提出
総評
500点にしては難しいと思う。グラフのDPは頂点に関してのDPが多いけど、これは辺に関してのDPって言えるかな。editorialの後半読んでも意味わからなかったです、わかるかた教えてください
色んなコンテストで青色になってみた話
約一年ぶりに記事更新します、伸縮箱です。AtCoderとTopCoder(SRM)とCodeforcesの三つのコンテストで青コーダ－になったので、それぞれのレベル感とか感じたこととかのまとめをしようかなと思います。3つのコンテストで色統一ができるのも中々ないですし、次はたぶん赤なので無理。
Codeforcesについて
Codeforces(以下CF)はAtCoder(以下AC)が緑だったときにはじめて参加しました。最初に参加したとき独特な英語の問題文「☆意味不明☆な文章」が読解できずに冷えていやになってやめてしまいました。そのあとしばらくしてからモチベが出てきてACが水の時に青になって、まためんどくさくなってやめました(最近また気が向いて参加した)。CF青はアルゴリズムの知識があんま必要なくて、ACが緑とか水でも実装マッチョの読解王になればすぐに青になれると思います。
TopCoder(SRM)について
TopCoderのSRM(以下SRM)はACが水だったときにはじめて参加しました。Div2 easy(AC150点くらい？)とDiv2 medium(AC300点くらい？)で二完しただけで運よく初回で青になれました。SRMはほかのコンテスト(AC, CF)と違って関数単体を実装する形式です。このせいで手元の環境でテストの仕方がわからなかったり、オフライン環境が古かったりしてつらかったので、一回しか参加してないです。もう参加しないかもしれない。
AtCoderについて
AtCoderは大学に入ったときからはじめて、かれこれ１年ちょいかかって青になりました。レベル感としては上記二つのコンテストに比べて遥かに青くなるのが難しいと感じました。ぼくは考察が苦手で脳死でゴリゴリ実装する方が好きだからというのもあると思います。ACは45回参加して、過去問もたくさん解いてやっと青になった感じです。やっぱりあるレートまでにたどりつくのに必要な練習量っていうのは経験や地頭のよさに大分左右されるので、人と比べることは無意味だと思います。(とはいえ頭のいい同期に無精進でレートで追いつかれたりしてつらかった)
Twitterについて
界隈の人たちはよくﾂｲｯﾀーをやっています。中には有益な情報をたくさんツイートしてたり、ライバルとなりえるようなレベルのひとがいて、モチベーションが上がったりするかもしれません。ただ界隈の人々は軒並み頭がよくて劣等感でメンタルをボコボコにされたりするので、自分みたいなメンタルが弱い人間はわざわざSNSでそういう人々と関わらなくてもいいと思います。自分も「競プロ垢」と称したアカウントを作成したはいいものの、結局同期とずっと「真夏の夜の淫夢」の話をしてるゴミアカウントになってます。
まとめ
終盤は自分の頭の悪さと劣等感の話になってしまいましたが、まあなんだかんだ楽しんで続けています。次はCF紫とかAC青上位(1級)とかめざしていこうと思っています。
Visual Studio CodeでC++の簡単な競プロ環境構築
今まで競プロの環境構築に何度も失敗して、ずっとVisual Studioを使ってきたのですが、なんとかVSCodeで最低限のGCCの環境が作れたので紹介しようかなと思います。(OSはWindows10を想定しています)
手順１ ～MinGWの導入～
ココのmingw-get-setup.exeとかいうのを落とします。実行して適当にイエスマンになってるとInstall Managerとかいうのが起動するので、mingw32-base-binとmingw32-gcc-g++-binにマークを付けて、ツールバーのInstallation→Apply Changesをクリックするとインストールが始まります。
インストールが終わったら、システムのプロパティから環境変数を開いて、システムの環境変数の欄のPathを編集し、"C:¥MinGW¥bin"を追加します。コマンドプロンプトでgcc -vと入力して、バージョンとかが出たら成功です。たぶんここまでは何度かやったことがある人もいると思います。
手順２ ～VSCodeの導入～
インストールしましょう。それはできるよね。
必要な拡張機能を導入します。C++で調べて一番上に出てくるであろうMSのやつを入れればいいです。私は英弱なのでJapanese Language pack for VScodeも導入します。
作業フォルダを作成してください。デスクトップとかに適当なフォルダを作ればいいです。ソースコードやこれから作るbatファイルやvscodeの設定を保存するjsonファイル等が入ります。ここではC:¥Users¥hoge¥Desktop¥cppとしておきます。
ファイル→フォルダを開く から先ほど作ったフォルダを開いて、中にmain.cppを作成してください。
コマンドパレット→C/Cpp:Edit Configurations...を開くと、作業フォルダの中に
.vscodeフォルダが作成され、 c_cpp_properties.jsonが現れるのでそいつを以下のように編集します。
{
"configurations": [
{
"name": "Win32",
"includePath": [
],
"defines": [
"_DEBUG",
"UNICODE",
"_UNICODE"
],
"windowsSdkVersion": "10.0.16299.0",
"cStandard": "c11",
}
],
"version": 4
}
下のようにmain.cppでbits/stdc++.hがincludeできることを確認したらOKです。(画像のsettings.jsonはなくても気にしなくていい)
これで波線が消えなかったらincludePathに
を追加すると動くこともあるそうです。(ぼくはいらなかったのでよくわからない)
batファイルを作成します。作業フォルダ内にbuild.batを作成して中身を以下のように変更します。(a.exeがセキュリティソフト()に抹殺されるらしいので対象外にするなどしてください)
g++ -std=gnu++1y -O2 main.cpp
call a.exe
-O2は最適化の度合いでAtCoderではデフォルトでO2で設定されています。(詳しくはググって)
Ctrl+Shift+B→ビルドタスクを構成→テンプレから...→Othersを選ぶと.vscodeフォルダ上にtask.jsonが現れます。
そこの一行だけ
"command": "./build.bat",
と書き換えます。あとはmain.cppに適当なコード書いてCtrl+shift+Bで下のように実行できればひとまず完成です。ターミナルから標準入力に右クリックでコピペで入力できるので便利。
Ctrl+Shift+Bを押すのはめんどくさいのでキーコンフィグをF6に変えようと思います。
コマンドパレットにkeyと入力して、「基本設定:キーボードショートカットファイルを開く」からkeybindings.jsonを開いて
[
{
"key": "f6",
"command": "workbench.action.tasks.build"
}
]
のように書き換えればOKです。これで完成です、お疲れ様でした。
