ロボットアームみたな問題群（追加予定）
問題
頂点OABを使った三角形を作ることができれば、頂点Cは内部に関してはどこにでも存在しうる。三角形を作ることができなければ最長辺の長さからその他二辺の長さを引いた長さだけの不可侵領域がOを中心にできる。
外側は最大でOA、AB、BCが一直線に並んだ場合実現される。その内側の面積から上で求めた不可侵領域の面積を引けば良い。
上の問題のN版。
キーエンスプログラミングコンテストにて。過去コンテスト中に解けず発狂した問題。
少し考えれば分かる。
AtCoder Beginner Contestの問題。難しめ。
名前知らずの有名問題？
大きさの数列
がある。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。
わかったら追記する。
追記用
