「○通り求めよ」系問題で初手に全探索を行うことを止めた (AGC015 A - A+...+B Problem)
初めてAGCのA問題の茶色級*1を解くことができたので、解法を記載する。
問題
問題は「最小値A、最大値Bの長さNの数列が与えられる。この数列の総和は何通りあるか？」である。
制約はN, A, Bともに1〜10^9をとる。
「○通り求めよ」系の問題は一瞬身構えてしまう。
初心者にありがちな「何でも全探索で解く」をやりがちな問題の聞き方であり、またそんな解き方をすると即座にTLEを叩きつけられる問題でもある。
考え方
当然全探索を行うと計算量は天文学的数値を取るため、この考え方は捨てる。
この問題は初めに和を考えるよりも、数列の0番目とN-1番目を除く数字の並べ方を考えるほうが良い。
たとえばN = 4, A = 4, B = 6の場合、以下の図のような○に4, 5, 6のいずれかを入れることを考える。
この場合、それぞれの○に4〜6の3つの数値を入れる場合の数を計算すると、和がかぶるパターンが出る。
そのため、以下のように考える。
○○に入る数値は最小値「44」、最大値「66」である。和がかぶらないようにするためには以下の操作を行う。
操作: 右の○から順番に数値をインクリメントする
数値が最大値となるまで上記の操作を繰り返す。
この操作を行った回数が、今回求める値である。
この操作回数は「◯に入りうる数値の個数(B - A + 1)」「◯の数(N - 2)」を考えると、以下のような式で計算することができる。
(B - A + 1)(N - 2) - ((N - 2) - 1)
= (B - A + 1)(N - 2) - (N - 2) + 1
= (B - A)(N - 2) + 1
あとは、提示されている例にあるコーナーケースに気をつけながら実装する。
提出コード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ll N, A, B; cin >> N >> A >> B; if(A > B) { cout << 0 << endl; } else if(N == 1 && B - A != 0) { cout << 0 << endl; } else if(N == 1 && B - A == 0) { cout << 1 << endl; } else { cout << (B - A)(N - 2) + 1 << endl; } }
create-react-appが正しくテンプレートを作ってくれなかったときに試みること
何が起こったのか
以下のコマンドを叩いてReactテンプレートを作ろうとした。
$ create-react-app my-app
その結果、my-app配下は以下のようなディレクトリ構成となってしまった。
|-- node_module |-- package.json `-- yarn.lock
また、package.jsonの内容も不完全である。
こうなると手も足も出ない。軽率にyarn startしても以下のように突っぱねられる。
$ yarn start yarn run v1.22.0 error Command "start" not found. info Visit https://yarnpkg.com/en/docs/cli/run for documentation about this command.
生成された不完全なpackage.jsonにscriptsの記載が無いためだ。
本当は以下のようなディレクトリ構成となってほしい。
|-- README.md |-- node_modules |-- package.json |-- public | |-- favicon.ico | |-- index.html | |-- logo192.png | |-- logo512.png | |-- manifest.json | `-- robots.txt |-- src | |-- App.css | |-- App.js | |-- App.test.js | |-- index.css | |-- index.js | |-- logo.svg | |-- serviceWorker.js | `-- setupTests.js `-- yarn.lock
解決方法
1. create-react-app のパスを調べる
$ which create-react-app
2. 表示されたパスのバックアップを取る
$ cp /usr/local/bin/create-react-app /usr/local/bin/_create-react-app
3. 表示されたパスを削除する
$ rm -r /usr/local/bin/create-react-app
4. 以下コマンドを実行して再度テンプレートを作り直す
$ npx create-react-app my-app
原因
create-react-appの仕様変更が原因。create-react-appのグローバルインストールがサポートされなくなり、明示的にnpxを使用してプロジェクトを作成するよう仕様変更された。
create-react-app公式ドキュメントに注意書きがある。
create-react-app.dev
If you've previously installed create-react-app globally via npm install -g create-react-app, we recommend you uninstall the package using npm uninstall -g create-react-app to ensure that npx always uses the latest version.
(翻訳)
以前にnpm install -g create-react-appを使用してcreate-react-appをグローバルにインストールしたことがある場合、npxが常に最新バージョンを使用するように、npm uninstall -g create-react-appを使用してパッケージをアンインストールすることをお勧めします。
少なくとも昨年(2019年)12月からこの仕様となったようだ。
github.com
ある配列のvalueを別の配列の添字にして問題を解く (ABC061 B - Counting Roads)
初心者は紙に書いて考えないと手こずる系の問題。
問題概略
N個の都市とM本の道路がある。
i番目の都市は、他の都市と1本の道路で結ばれている。
このときi番目の都市が、他のいくつの都市と結ばれているか?
出力は、i行目にi番目の結果を出力せよ。
入力
N M
a_1 b_1
...
a_M b_M
方針
次の2通りの方針が考えられる。
- 2重ループを用いて、全探索を行う。計算量はO(NM)。
- 「i番目の都市が他の都市といくつ道路をつないでいるかを管理する配列」を用意して数え上げる。計算量はO(N + M)。
今回は2つ目の方法を用いて解く。
配列を用意する
今回用意する配列は、以下の情報を格納する。
「i番目の都市が他の都市といくつ道路をつないでいるかを管理する配列」・・・(A)
この(A)は以下のように考える。
aおよびbの0番目から「都市aから伸びている道路の数」と「都市bから伸びている道路の数」をカウントしていく。
たとえば0番目の入力が「1 5」であれば、配列(A)の1番目の都市と5番目の都市をそれぞれインクリメントする。
このカウント結果を上記の配列に格納する。
最後に、この配列を0番目から順に標準出力して完了。
実装する
2重配列でもよいが、今回は連想配列を用いた。
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) int main(){ int N, M; cin >> N >> M; vector<int> a(M), b(M); rep(i, M) cin >> a[i] >> b[i]; map<int, int> res; rep(i, N) res[i] = 0; rep(i, M) { res[a[i] - 1]++; res[b[i] - 1]++; } rep(i, N) { cout << res[i] << endl; } }
ABC121 C - Energy Drink Collectorをstd::pairを使って解く
C++のSTLにはstd::pairという関数が用意されている。
2つの値の組を表し、使い方も単純で
pair<値1の型, 値2の型> 変数名;
で宣言して
make_pair(値1, 値2);
を使って値を突っ込んでいくだけだ。
いろいろな場面で活用できるのだが、先日AtCoderの過去問を解いているとき、「配列Aをキーとして配列Bをソートする」という場面に遭遇した。
つまり、配列Aを降順(昇順)にソートしたとき、ソート結果に基づいて配列Bも並び替えたい、というものだ。
この「過去問」とは、以下の問題だ。
いくつか解放が考えられるが、今回は上記で示したpair関数を用いて解く。
atcoder.jp
問題を要約すると「ある個数Mのエナジードリンクを手に入れたとき、エナジードリンクの価格の合計の最低値を求めよ」となる。
回答は以下。
#include <bits/stdc++.h> using namespace std; int main(){ int N, M; cin >> N >> M; vector<long long> A(N), B(N); vector<pair<long long, long long>> p(N); for(int i = 0; i < N; ++i) { cin >> A[i] >> B[i]; p[i] = make_pair(A[i], B[i]); } sort(p.begin(), p.end()); long long cnt = 0; long long mon = 0; for(int i = 0; i < N; ++i) { if(cnt + p[i].second <= M) { mon += p[i].first * p[i].second; cnt += p[i].second; } else if(cnt + p[i].second > M) { while(cnt < M) { cnt++; mon += p[i].first; } } if(cnt == M) { break; } } cout << mon << endl; }
まず、この部分で標準入力を行っているが、同時にpair型配列に受け取った値A, Bを突っ込んでいる。
vector<long long> A(N), B(N); vector<pair<long long, long long>> p(N); for(int i = 0; i < N; ++i) { cin >> A[i] >> B[i]; p[i] = make_pair(A[i], B[i]); }
その受け取った値を持つpを、Aをキーにソートする。同じくSTLのsortを用いれば良い。
sort(p.begin(), p.end());
あとは0番目から順番に価格を計算し、変数に突っ込んでいけばよい。
300点問題の中では簡単な部類だが、慣れていないと手が止まる。
ofMeshを使って図形を描画する
openFrameworksには図形を描画するための便利な関数が複数存在する。
ofDrawRectangle(x, y, w, h); ofDrawCircle(x, y, w, h);
などがそれに当たる。
しかし、ジェネラティブなプログラムを作りたい場合、これら関数を使うより便利な方法がある。自ら点と線を書いて図形を描画することだ。
これを実現するクラスがofMeshだ。
備忘のため、ofMeshを使って図形を描画する方法を記す。
なお、oF公式ドキュメント「ofBook」の以下ドキュメントを参考にした。
openframeworks.cc
Mesh
Meshとは、頂点の集合のことだ。それら頂点は互いに1本の線で接続が可能だ。
頂点を線で接続した形状をプリミティブと呼んだりする。下記の3Dモデルはプリミティブの一例だ。
ofMesh
ofMeshは、openFrameworks上でMeshの管理を担当するクラスだ。
以下公式ドキュメントを読むと、openFrameworks上でMeshを扱う上で役立つクラスメソッドが多数用意されている。
openframeworks.cc
openFrameworksでMeshを扱う際、このofMeshを使用する。
ofMeshで点を打つ
早速ofMeshで図形の描画を始める。まずは頂点を打つことだ。
ofApp.hでofMeshを宣言する。
#pragma once #include "ofMain.h" class ofApp : public ofBaseApp{ public: void setup(); void update(); void draw(); void keyPressed(int key); void keyReleased(int key); void mouseMoved(int x, int y ); void mouseDragged(int x, int y, int button); void mousePressed(int x, int y, int button); void mouseReleased(int x, int y, int button); void mouseEntered(int x, int y); void mouseExited(int x, int y); void windowResized(int w, int h); void dragEvent(ofDragInfo dragInfo); void gotMessage(ofMessage msg); ofMesh mesh; // ofMeshの初期化 };
次にofApp.cppを見る。setup関数にofMeshの設定を記載する。
void ofApp::setup(){ mesh.setMode(OF_PRIMITIVE_POINTS); mesh.enableColors(); // 3点の座標を用意する ofVec2f top(100.0, 50.0); ofVec2f left(50.0, 150.0); ofVec2f right(150.0, 150.0); // (100.0, 50.0)の位置に赤い点を打つ mesh.addVertex(top); mesh.addColor(ofFloatColor(1.0, 0.0, 0.0)); // (50.0, 150.0)の位置に緑の点を打つ mesh.addVertex(left); mesh.addColor(ofFloatColor(0.0, 1.0, 0.0)); // (150.0, 150.0)の位置に青い点を打つ mesh.addVertex(right); mesh.addColor(ofFloatColor(1.0, 1.0, 0.0)); }
setModeにOF_PRIMITIVE_POINTSを設定した。これはプリミティブとして点を描画するためである。
なお、setModeで指定できる値には以下が存在する。
- OF_PRIMITIVE_POINTS
- OF_PRIMITIVE_LINES
- OF_PRIMITIVE_LINE_STRIP
- OF_PRIMITIVE_LINE_LOOP
あとは座標の任意の位置に点を打つ。今回は2次元座標を扱うため、頂点座標の指定にはofVec2fを用いている。
draw関数内でmesh.draw()をしてあげると、meshに格納された頂点情報を描画してくれる
void ofApp::draw(){ ofBackground(0); mesh.draw(); }
これを実行すると以下となる。
ofMeshで三角形を描く
点を打ったので、あとは点同士を線で結ぶ。すると、正三角形が出来上がる。
すでに頂点は存在するため、setModeを変更して線を引っ張る。setup関数内の記述を変更する。
void ofApp::setup(){ mesh.setMode(OF_PRIMITIVE_LINES); // OF_PRIMITIVE_LINESに変更 mesh.enableColors(); // 3点の座標を用意する ofVec2f top(100.0, 50.0); ofVec2f left(50.0, 150.0); ofVec2f right(150.0, 150.0); // (100.0, 50.0)の位置に赤い点を打つ mesh.addVertex(top); mesh.addColor(ofFloatColor(1.0, 0.0, 0.0)); // (50.0, 150.0)の位置に緑の点を打つ mesh.addVertex(left); mesh.addColor(ofFloatColor(0.0, 1.0, 0.0)); // (150.0, 150.0)の位置に青い点を打つ mesh.addVertex(right); mesh.addColor(ofFloatColor(1.0, 1.0, 0.0)); }
実行する。結果は以下。
1本しか引っ張ってくれない。不親切だ。しかしこれには理由がある。
OF_PRIMITIVE_LINESを指定すると、頂点のペアを作り、それら同士を直線で結ぶ挙動を取るからだ。たとえば頂点が[v1, v2, v3, v4]4つ存在するとき、[v1, v2]同士と[v3, v4]同士で直線を結ぶ。
つまり、今回は3点のうちはじめにaddVertexした2点 [top, left]間で直線を結んでしまった。
これを解消するには、他のモードを試す。
結論から言うと、三角形を描画したければ以下のようにする。
void ofApp::setup(){ mesh.setMode(OF_PRIMITIVE_LINE_LOOP); // OF_PRIMITIVE_LINE_LOOPに変更 mesh.enableColors(); // 3点の座標を用意する ofVec2f top(100.0, 50.0); ofVec2f left(50.0, 150.0); ofVec2f right(150.0, 150.0); // (100.0, 50.0)の位置に赤い点を打つ mesh.addVertex(top); mesh.addColor(ofFloatColor(1.0, 0.0, 0.0)); // (50.0, 150.0)の位置に緑の点を打つ mesh.addVertex(left); mesh.addColor(ofFloatColor(0.0, 1.0, 0.0)); // (150.0, 150.0)の位置に青い点を打つ mesh.addVertex(right); mesh.addColor(ofFloatColor(1.0, 1.0, 0.0)); }
OF_PRIMITIVE_LINE_LOOPを設定すると、Meshに格納した順に頂点同士を線で結ぶ。そして、最後の頂点vnを頂点v1に結ぶ。こうすることで閉じた図形が出来上がる。
Meshで図形を描く利点
頂点に対する処理や演算が非常に楽になる。
ofMeshは配列で頂点の位置を保存しているため、全頂点を一気に操作することが容易い。
対してofDrawRectangle(x, y, w, h)などの関数は、すべての関数の引数に変数を設定し、変数操作を行う必要がある。1つの三角形であればよいが、2億個となると話は別だ。プログラムを書くことも大変だし、点の挙動をコントロールすることも嫌になる。
assimpExampleのソースコードを読んで、ofxAssimpModelLoaderで3Dモデルを描画する
openFrameworksのsamplesに入っているassimpExampleのソースコードを読みます。
assimpExampleとは
これ
openFrameworksのライブラリofxAssimpModelLoaderを使用して、読み込んだ3Dモデルをインタラクティブに表示切り替えするsampleです。
このソースを読んで、ofxAssimpModelLoaderで3Dモデルを描画するエッセンスを習得します。
まずはヘッダファイル。
ofApp.h
#ifndef _TEST_APP #define _TEST_APP #include "ofMain.h" #include "ofxAssimpModelLoader.h" #include "ofVboMesh.h" class ofApp : public ofBaseApp{ public: void setup(); void update(); void draw(); void keyPressed(int key); void keyReleased(int key); void mouseMoved(int x, int y ); void mouseDragged(int x, int y, int button); void mousePressed(int x, int y, int button); void mouseReleased(int x, int y, int button); void mouseEntered(int x, int y); void mouseExited(int x, int y); void windowResized(int w, int h); void dragEvent(ofDragInfo dragInfo); void gotMessage(ofMessage msg); ofxAssimpModelLoader model; bool bHelpText; bool bAnimate; bool bAnimateMouse; float animationPosition; ofMesh mesh; ofLight light; }; #endif
ヘッダファイルをincludeします。
#include "ofxAssimpModelLoader.h"
この部分でクラスofxAssimpModelLoaderを初期化しています。
ofxAssimpModelLoader model;
また、ofLightを使って照明オブジェクトを初期化しています。
ofLight light;
ofApp.cpp
次はcppファイル。setupとupdateを確認。
#include "ofApp.h" void ofApp::setup(){ ofSetLogLevel(OF_LOG_VERBOSE); ofBackground(50, 0); ofDisableArbTex(); // we need GL_TEXTURE_2D for our models coords. bAnimate = false; bAnimateMouse = false; animationPosition = 0; model.loadModel("astroBoy_walk.dae", false); model.setPosition(ofGetWidth() * 0.5, (float)ofGetHeight() * 0.75 , 0); model.setLoopStateForAllAnimations(OF_LOOP_NORMAL); model.playAllAnimations(); if(!bAnimate) { model.setPausedForAllAnimations(true); } bHelpText = true; } void ofApp::update(){ model.update(); if(bAnimateMouse) { model.setPositionForAllAnimations(animationPosition); } mesh = model.getCurrentAnimatedMesh(0); }
3Dモデルを描画するだけなら、いろいろなものを読み飛ばして良さそう。
とりあえずmodelの設定関連が必要なので、以下が必須のコード。
void ofApp::setup(){ ofBackground(50, 0); ofDisableArbTex(); // we need GL_TEXTURE_2D for our models coords. model.loadModel("astroBoy_walk.dae", false); model.setPosition(ofGetWidth() * 0.5, (float)ofGetHeight() * 0.75 , 0); model.setLoopStateForAllAnimations(OF_LOOP_NORMAL); model.playAllAnimations(); } void ofApp::update(){ mode.update(); }
ofxAssimpModelLoaderのクラスメソッドは、公式ドキュメントに記載がほぼなく使い方がわからない。
唯一このページが参考になる。
openframeworks.cc
最後はdraw内のソースコード。
void ofApp::draw(){ ofSetColor(255); ofEnableBlendMode(OF_BLENDMODE_ALPHA); ofEnableDepthTest(); #ifndef TARGET_PROGRAMMABLE_GL glShadeModel(GL_SMOOTH); //some model / light stuff #endif light.enable(); ofEnableSeparateSpecularLight(); ofPushMatrix(); ofTranslate(model.getPosition().x+100, model.getPosition().y, 0); ofRotateDeg(-mouseX, 0, 1, 0); ofTranslate(-model.getPosition().x, -model.getPosition().y, 0); model.drawFaces(); ofPopMatrix(); #ifndef TARGET_PROGRAMMABLE_GL glEnable(GL_NORMALIZE); #endif ofPushMatrix(); ofTranslate(model.getPosition().x-300, model.getPosition().y, 0); ofRotateDeg(-mouseX, 0, 1, 0); ofTranslate(-model.getPosition().x, -model.getPosition().y, 0); ofxAssimpMeshHelper & meshHelper = model.getMeshHelper(0); ofMultMatrix(model.getModelMatrix()); ofMultMatrix(meshHelper.matrix); ofMaterial & material = meshHelper.material; if(meshHelper.hasTexture()){ meshHelper.getTextureRef().bind(); } material.begin(); mesh.drawWireframe(); material.end(); if(meshHelper.hasTexture()){ meshHelper.getTextureRef().unbind(); } ofPopMatrix(); ofDisableDepthTest(); light.disable(); ofDisableLighting(); ofDisableSeparateSpecularLight(); if(bHelpText){ ofSetColor(255, 255, 255 ); stringstream ss; ss << "FPS: " << ofToString(ofGetFrameRate(),0) <<endl<<endl; ss <<"(keys 1-5): load models"<<endl; ss << "num of animations in this model: " + ofToString(model.getAnimationCount()); ss <<endl <<"(Spacebar): toggle animation"<<endl; ss <<"(LEFT MOUSE BUTTON DRAG in y-axis): control animation."<<endl; ss <<"(h): toggle help."<<endl; ofDrawBitmapString(ss.str().c_str(), 20, 20); } }
いろいろな記載があるけど、モデルの描画を行う記述は以下。
void ofApp::draw(){ ofSetColor(255); light.enable(); ofEnableSeparateSpecularLight(); model.drawFaces(); }
ofEnableSeparateSpecularLightは、モデルに光沢がつくような処理を行う記述。
openframeworks.jp
鏡面ハイライトと呼ぶ。詳細は以下。
area.autodesk.jp
自分で書いてみる
というわけで以下のofApp.cppを作成。
#include "ofApp.h" //-------------------------------------------------------------- void ofApp::setup(){ ofBackground(50, 0); ofDisableArbTex(); model.loadModel("astroBoy_walk.dae"); model.setPosition(ofGetWidth() * 0.5, (float)ofGetWidth() * 0.75, 0); model.setLoopStateForAllAnimations(OF_LOOP_NORMAL); model.playAllAnimations(); } //-------------------------------------------------------------- void ofApp::update(){ model.update(); } //-------------------------------------------------------------- void ofApp::draw(){ ofSetColor(255); ofEnableBlendMode(OF_BLENDMODE_ALPHA); ofEnableDepthTest(); light.enable(); ofEnableSeparateSpecularLight(); model.drawFaces(); // loadModelで読み込んだモデルを表示 }
実行結果は以下の通り。
陰影もあって良い感じ。3Dモデルの描画に成功した。
ちなみに、light.enable(); を外すとこんな感じ。
フィルム1本真剣勝負 - 代々木公園編
代々木公園とその周辺。
今回使ったフィルムはこれ。
![Kodak 35mm Ektar 100 Color Negative (Print) Film 36 Exp. lot of 5 Rolls by Kodak [並行輸入品]](https://images-fe.ssl-images-amazon.com/images/I/51I8fktrdSL._SL160_.jpg)
Kodak 35mm Ektar 100 Color Negative (Print) Film 36 Exp. lot of 5 Rolls by Kodak [並行輸入品]
posted with amazlet at 18.03.04
売り上げランキング: 1,809,743
ISO100初挑戦。
ISO100はやっぱり暗いとブレる。そんな当たり前のことに改めて気付かされた。
汗ばむくらい春を感じた。
お花見客がいっぱい。
最後は自宅周辺で終わり。
