名前知らずの有名問題？
大きさの数列
がある。1≤i<j≤Nを満たすi、jにおいてdij:=Aj−Aiとする。dijの最大値を求めよ。
制約：
AtCoder Beginner Contest 015 D - 高橋君の苦悩 誤答コード(Resolved)
また自分の目が腐っているかもしれない案件について。
この問題だ。
提出コードはこちら。そしてスクリーンショットも合わせて。
そしてサンプル2に対しての自分のプログラムの出力はこちら。
そして問題ページにある出力はこちら。
ふう、どうやらまた視力検査が必要なみたいだぜ。。コンタクトに変えようか。
冗談抜きで皆さんも試して見てほしい。以下のプログラムに上記の入力を私見てほしい。そして結果を教えてほしい。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
int main() {
int w;
cin >> w;
int n, k;
cin >> n >> k;
vector<P> input(n);
rep(i, n) cin >> input[i].first >> input[i].second;
vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(k+1, vector<int>(w+1)));
rep(i, n+1) {
rep(j, k+1) {
if(j > i) break;
rep(l, w+1) {
if(i == 0 || j == 0 || l == 0) {
dp[i][j][l] == 0;
}
else if(input[i].first > l) dp[i][j][l] = dp[i-1][j][l];
else {
dp[i][j][l] = max(dp[i-1][j][l], dp[i-1][j-1][l-input[i].first] + input[i].second);
}
}
}
}
cout << dp[n][k][w] << endl;
}では。
追記用
自分の目が腐っていた。
input[i]は違っていて、input[i-1]が正解
それに直したところWAがほとんどなくなった。（まだACしていない）。
いろいろテストケースを作っていたところ、次のテストケースで引っかかった。
3
3 2
3 100
5 500
7 200
expected: 100, output: 0
自分が実際定義していたの内容をすっかり忘れていた。
つまり自分が定義していたdp[i][j][l]は「の左から
個までを使うことができ、実際に
個を使いかつ全ての幅が
以下であるような時の重要度の合計の最大値」だった。
つまり出力するのがdp[n][k][w]だと「の左から
個を使うことができ、実際に
個を使ってかつ全ての幅が
以下であるような時の重要度の合計の最大値」になってしまう。
個使う必要はないので、その部分を修正する。結果AC。
What the heck is the event loop anyway? JSConf EUを観て。
本当にわかりやすいプレゼンだった。いきなりイベントループに入らず、「JavaScriptとは何なのか？」を説明し、それから「V8の中身」「コードが実行されるときのスタックの中身がどのように変遷しているのか」「スタックとwebapiとのやり取り」などをアニメーションを使って視覚的に分かるように説明していた。イベントループと題にうってあるが、ブラウザの中でJavaScriptがどのように動作するのかを大まかに知りたい人にはこの動画は非常に良い。2014のJSConfの動画だが2020年の今になっても見る価値のある動画であり、かつプレゼンテーションの見本でもある。とにかく素晴らしかった。他にもJSConfの動画で観ていない動画が多いので、また今度時間がある時に観たい。
下は自分が動画を観ながらとったメモ。
Transcriptはこちらから。
動画中で使われているヴィジュアライズのためのアプリケーション。自分でいろいろコードを書いてみるとよく分かる。
では。
多次元vectorを生成するのに便利なテンプレート。
けんちょんさんのコードを見ていて、多次元vectorを生成するのに便利なテンプレートを発見したので、載せておく。けんちょんさん(drken)に感謝。
template<class T>
vector<T> make_vec(size_t a){
return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
// example of 5-dimensional vecotr
auto sample = make_vec<int>(3, 3, 3, 3, 3);
AtCoder Beginner Contest 122 D - We Like AGC 誤答コード
問題と提出コードはこちら。
問題
提出コード
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using ll = long long;
#define chmin(i, j) i = min(i, j);
#define chmax(i, j) i = max(i, j);
#define rep(i, n) for(int i=0;i<n;i++)
ll N;
ll MOD = 1000000007;
vector<map<string, ll>> memo;
bool ok(string last4) {
rep(i, 4) {
string t = last4;
if(i >= 1) swap(t[i], t[i-1]);
auto it = t.find("AGC");
if(it != string::npos) return false;
}
return true;
}
ll dfs(int cur, string last3) {
if(memo[cur][last3]) return memo[cur][last3];
if(cur == N) return 1;
ll ret = 0;
for(auto& c : "ACGT") {
if(ok(last3 + c)) {
ret += dfs(cur+1, last3.substr(1, 2) + c);
ret %= MOD;
}
}
memo[cur][last3] = ret;
return ret;
}
int main() {
cin >> N;
memo.resize(N+1);
cout << dfs(0, "TTT") << endl;
}正直全くわからなkった。解答に忠実に実装したがWA。最初のサンプル入力における出力は122。期待される値は61。
わかったら追記する。
追記用
ブラッドウェブみたいなやつ作りたい。
（注）これはポエムです。お気をつけてお読みください。
デッドバイデイライトっていうゲーム知ってますか。
非対称の対戦ゲームでサバイバー4人とキラー1人が対戦するゲームです。サバイバーはキラーから逃げることが勝利条件、キラーはサバイバーをなるべく多く屠ることが勝利条件です。
一つの対戦の中で、サバイバー・キラーどちらもパーク(perk)という特殊な能力を4つだけ選んで使うことができます。使うパークは対戦の前に選択します。もう一つアドオンというのもありますが、それもパークと似たような機能を果たします。
そのパークやアドオンというのは、ゲームを始めたばかりだと3つほどしか選択肢がありません。新しいパークを獲得するためには、ゲームを何回もプレイする必要があります。具体的には一つの対戦ごとにプレイヤーのパフォーマンスに応じてブラッドポイントというポイントをプレイヤーは獲得します。獲得したポイントを使って新しいパークやアドオンを取得するというのが通常の流れです。まあポケモンで言うレベル上げ見たいなもんです。
その新しいパークやアドオンを取得する上で出てくるのがブラッドウェブ。蜘蛛の巣上に新しく取得できるパークやアドオンが広がっていて、その中から自分がゲットしたいパークをブラッドポイントを消費して選択して行きます。
具体的には下のリンクから見てください。
具体的にブラッドウェブがどんな機能を果たすのかはここでは問題にしません。僕がここで強調したいのがブラッドウェブのデザイン最高じゃね？？と言うことです。
何で好きなのかって言うと、僕個人がグラフがすごい好きだからです。グラフの形をしているものに目がありません。蜘蛛の巣はループがあるので木構造ではありません。単なる無向グラフです。
これを実装したいと言うのがこのポエムの趣旨です。
でなんか良い題材ないかなーと思っていたところ、AtCoder Problemsの問題をグラフの形にしたいなぁなんて思ったりしてます。
AtCoder Problemsの表示形式は今のところコンテストごとの表形式です。それも全然ありなのですが、グラフ形式で表示したい。問題同士の繋がりを見たい。
もっといってしまうとAtCoder ProblemsとAtCoder Tagsの融合したものを作りたいといった感じです。AtCoder Tagsにのっとって問題をクラスタリングして、そのクラスタリングした問題を難しさごとにレベル分けする。一つのレベルに大体10~20くらいの問題を載せて、ACした問題に関しては緑、WAした問題に関しては黄色にしたい（これはAtCoder Problemsと全く一緒）。
まあ単に動的にグラフが作りたいと言うことです。それをヴィジュアライズしたい。
と言うポエムでした。
以上。
