ネコ探索アルゴリズムについて
こんにちは。今日は強化学習というかメタヒューリスティックな方法にであるネコ探索を用いたナップサック問題の近似値を求める方法について、論文を読み実装したので書いていきたいと思います。このようなコウモリ探索、オオカミ探索などメタヒューリスティックなアルゴリズムについて日本語の記事が殆どなかったため、記しておこうという理由です。具体的には以下の論文を読みました。 また本ブログでは実装例は載せますが、個人で行なったものであり必ずしも正しいかはわかりません。あくまで参考にして詳しくは論文を読んでいただけると幸いです。
Ricardo Soto , Broderick Crawford , Angelo Aste Toledo, Hanns de la Fuente-Mella , Carlos Castro , Fernando Paredes , and Rodrigo Olivares (2019) "Solving the Manufacturing Cell Design Problem through Binary Cat Swarm Optimization with Dynamic Mixture Ratios
概要
ネコ探索とは何かということを説明しますが、正直名前の由来はいまいちしっくりこないです。ただネコ科の習性を活かした探索方法ということがわかります。具体的に以下の2つのmodeに従って探索されていきます。
seeking_mode
tracing_mode
順に説明します。
seeking_mode
ネコ科の動物(ライオンなど)は基本的にほとんどの時間はじっとしております。しかしその時間は必ずしも休んでいるわけではなく、敵がどこにいるか、どの方角にいるかなど、見張っている時間も多いです。 また遺伝的アルゴリズム同様、子孫を増やしていきます。これを元にした探索手法です。正直初めて論文を読んだ時そして今もよくわからないです。がアルゴリズムはしっかりしているのでその部分をナップサック問題に合わせて簡潔に説明します。 まずナップサックにどの荷物を入れるかという1つの解が存在します。 その解は配列として用意し、0101001のようにi番目の荷物を入れる場合は1を入れない場合は0を立てる配列です。 これを数十個ほどコピーします。そしてそれらのコピーされた配列1つ1つに対して、ある確率のもとで1->0,0->1に反転していきます。すると異なった配列が複数できるわけです。当然これらは価値が異なってきますので、容量オーバーとなるもの以外で、価値を計算していきます。このなかで良い価値が生じたものを 次の世代の解として更新し、残していくという流れです。(この部分では必ずしも最も価値が高いものを選ぶわけではなくそれも確率的に決めるのですが説明するより論文を読んでいただけたほうがよいため割愛します)
tracing_mode
ここでは実際にネコ科の動物が獲物を狙いに行くことを模倣したmodeです。 正直意味はわからないですが,ありがたいことに論文にフローチャートが掲載されているので、それどおり実装するだけです。ですので概要的な説明になりますが、速度ベクトルが2つあり、それぞれ0->1にする速度、1->0にする速度2つがあります。それをこれまでの最高スコアを出している配列をもとに決めていきます。そしてそのベクトルの大きさがランダム値以上の時はじめの初期配列を更新しそうでない時は更新しないという流れです。僕は最近知ったのですがPSO(粒子群最適化法)と呼ばれる手法に非常に近い形で配列を更新していくことになります PSOについては以下の記事が非常に参考になりました。
ざっくりいえば値を更新する際、 もともとの慣性速度とこれまでの最大のスコアを出している位置とのベクトル和により速度を更新し初期解を変更しようという流れです。また今回、更新された配列がナップサックの容量を超えた時はそもそも更新しないという方法を取りましたが、論文では別の問題ではありますが、よりよいアルゴリズムが記されていたのでこれをナップサック問題に適応できる形に直して適応させるべきと考えましたがよくわかりませんでしたのでわかる方がいましたら教えてくれると幸いです。
まとめ
以上の方法を元に実装したところ、ある程度の大きさまでは厳密解と一致しました。 またその探索の流れを見てみると少しずつ解に近づいていく様子が観察できたため、実装に大きなバグはないのかなと思います。ただnを大きくするとやや厳密解とずれるため、そのへんはパラメータ調整でうまく行くのかそれともバグがあるのかはわからないです。(AtCoder上のナップサック問題に適応してみると半分くらいACでした)今回英語の比較的新しい論文を読んで実装した経験はほぼ初だったのでブログにまとめました。何度も述べますが、実装に誤りがあるかもわからないので、論文を読んで各人が実装していただければと思います。
実装
標準入力は以下のような形です。
N Max_Capacity W_i,...,W_N (重さ) C_i,...,C_N (価値)
C++による実装
#include <bits/stdc++.h> #include<time.h> #include <unistd.h> using namespace std; //vectorの中身を表示する関数 template <class T> void show(vector<T> v) { for (int i = 0; i < v.size(); i++) { cerr << v[i] << " "; } cerr << "\n"; } //容量オーバーしていないかチェックする関数 bool check(vector<int> &x, vector<int> &weight, int capacity, int n) { int weight_sum = 0; for (int i = 0; i < n; i++) { if (x[i]) { weight_sum += weight[i]; } } if (weight_sum > capacity) { return false; } else return true; } //ナップサックに入った価値を計算する関数 int calc_sum_profit(vector<int> &x, vector<int> &profit,int n) { int profit_sum = 0; for (int i = 0; i < n; i++) { if (x[i]) { profit_sum += profit[i]; } } return profit_sum; } //価値最大を計算する関数 int calc_max(int C,int n,vector<int> &weight, vector<int>&profit,vector<int>&x_best ,vector<vector<int>>& cat,int capacity,int max_profit){ for (int i = 0; i < C; i++) { if (check(cat[i], weight, capacity, n)) { int sum1 = calc_sum_profit(cat[i], profit, n); if (sum1 > max_profit) { max_profit = sum1; for (int j = 0; j < n; j++) { x_best[j] = cat[i][j]; } } } } return max_profit; } //グローバル変数にしておく double MR = 0.75, SMP = 15, CDC = 0.2, PMO = 0.76; //seeking _mode void seeking_mode(vector<int> & x, vector<int> &profit,vector<int>& weight,int capacity,int n){ vector<vector<int>> copy_cat(SMP, vector<int>(n, 0)); //SMP個分コピーする for (int i = 0; i < SMP; i++) { for (int j = 0; j < n; j++) { copy_cat[i][j] = x[j]; } } for (int i = 0; i < SMP; i++) { for (int j = 0; j < n; j++) { if((double)rand()/RAND_MAX < CDC){ if ((double)rand() / RAND_MAX < PMO){ copy_cat[i][j] = rand() % 2; } } } } vector<int> ok_cat; vector<int> fs(SMP); int fs_max = 0, fs_min = 1e9; int flag=0; for (int i = 0; i < SMP; i++) { if(check(copy_cat[i],weight,capacity,n)){ int tmp = calc_sum_profit(copy_cat[i], profit, n); fs_max = max(fs_max, tmp); fs_min = min(fs_min, tmp); fs[i] = tmp; flag = 1; } } //もしすべて容量オーバーしていたら何もしない if(!flag) return; //確率の // 重み付け確率を求めたい vector<pair<double,int>> prob; for (int i = 0; i < SMP; i++) { if (check(copy_cat[i], weight, capacity, n)) prob.push_back({ (double)((fs[i] - fs_min) / (double)(fs_max - fs_min+0.001)),i}); } sort(prob.begin(), prob.end()); vector<double> rui(prob.size() + 1); rui[0] = -1; rui[1] = prob[0].first; for (int i = 1; i < prob.size(); i++) { rui[i+1] = rui[i] + prob[i].first; } //大きい数字 int num = rand() % (int)(rui[rui.size() - 1]+1); //確率的にどれを選ぶかを決める int tmp_index = --lower_bound(rui.begin(), rui.end(), num) - rui.begin(); int index = prob[tmp_index].second; int candidate_Score = fs[index]; if(candidate_Score > calc_sum_profit(x,profit,n)){ for (int i = 0; i < n; i++) { x[i] = copy_cat[index][i]; } } } //tracing_mode void tracing_mode(vector<int> & x, vector<int> & x_best,int n) { //論文通りに実装 double d1 = 0,d0 = 0; double V1 = 0,V0 = 0,V_prime = 0; vector<double> t(n, 0); double c1 = 1, r1 = 0.5, w = 1; for (int i = 0; i < n; i++) { if(x_best[i]){ d1 = r1 * c1; d0 = -r1 * c1; } else{ d1 = -r1 * c1; d0 = r1 * c1; } V1 = w * V1 + d1; V0 = w * V0 + d0; if(x[i]){ V_prime = V0; } else{ V_prime = V1; } t[i] = (double) (1.0 / (1.0 +(double) exp(-V_prime))); if((double) rand()/RAND_MAX >= t[i]){ x[i] = x_best[i]; } } } //初期化関数 void init(vector<vector<int>> & cat,int C,int n ){ for (int i = 0; i < C; i++) { for (int j = 0; j < n; j++) { cat[i][j] = rand() % 2; } } } signed main(){ srand((unsigned int)time(NULL)); int n; int capacity; cin >> n; cin >> capacity; vector<int> weight(n); vector<int> profit(n); for (int i = 0; i < n; i++) { cin >> weight[i]; } for (int i = 0; i < n; i++) { cin >> profit[i]; } int C = 20; int Iterations = 50; vector<vector<int>> cat(C, vector<int>(n, 0)); vector<bool> seek_or_trace(C,0); vector<int> x_best(n); //初期化 init(cat, C, n); //暫定的な最大値の配列を取得 int max_profit = 0; for (int i = 0; i < C; i++) { if(check(cat[i],weight,capacity,n)){ int sum1 = calc_sum_profit(cat[i], profit, n); if (sum1 > max_profit) { max_profit = sum1; for (int j = 0; j < n; j++) { x_best[j] = cat[i][j]; } } } } //ここからスタート int counter = 0; time_t pretime = time(NULL); while (counter < Iterations) { ///max_profit = calc_max(C, n, weight, profit, x_best, cat, capacity, max_profit); for (int i = 0; i < C; i++) { vector<int>tmp=cat[i]; if((double) rand()/RAND_MAX < MR){ seeking_mode(cat[i],profit,weight,capacity,n); } else{ tracing_mode(cat[i], x_best, n); } //更新されたもとの配列が制約を満たしていなかったらもとに戻す if(!check(cat[i],weight,capacity,n)){ cat[i]=tmp; } } max_profit = calc_max(C, n, weight, profit, x_best, cat, capacity, max_profit); counter++; //ここのコメントアウトを外すと毎回の更新の際の配列の変化がわかります。 // show(x_best); // sleep(1); } show(x_best); cout << max_profit << endl; }
参考文献
Ricardo Soto , Broderick Crawford , Angelo Aste Toledo, Hanns de la Fuente-Mella , Carlos Castro , Fernando Paredes , and Rodrigo Olivares (2019) "Solving the Manufacturing Cell Design Problem through Binary Cat Swarm Optimization with Dynamic Mixture Ratios
AtCoder水色になるまで
こんにちは。今回AtCoder水色になるまでにやったことを手短に書きたいと思います。といってもアルゴリズムについてはまとめて覚えたとかではないので書かないです。
ABCのコンテストでDまで早解きorたまにEを通す。この２つです。企業コン2問早解きやAGCは失敗の可能性も高いためABCで上の成績を取るのが確実だと思います。
高度なアルゴリズムも高難易度も通せなくてもなれるため体感的に水色になるレベルはコンテストに継続して参加すれば全然高くないと思います。それよりもABCのCや易しいDをノータイムで実装できるようになれば良いと思います。水色になって働く意欲もあって開発分野に興味もあるので神人材じゃん()と思い、インターンやアルバイト等も含めて受かりやすくなるのかなと期待していましたが、現実はそう甘くないですね。(笑)それよりも実務や個人開発の経験を積まなければならないと思いますし、これからはそちらにも力を入れていきたいと思います。それはさておき水色になって名前の色が変わった時は嬉しかったですね。ひとまずの目標は水色安定と水diffを安定して解けるようになることです。また、青になるにはまだまだ壁があるのでゆっくり1年くらいかけて目指したいなと考えています。
Vino-serverからRemminaに接続する
こんにちは。今回は東京大学電気系の実験である大規模ソフトウェアを手探るという実験のなかで取り組んだ内容について書いていきたいと思います。
Remminaへの逆接続を行う(サーバ->クライアント)
私は同じ学科の友人とペアを組み上の課題について取り組みました。
まずRemminaって何というところから説明していきたいと思います。
Remminaというのはデスクトップ共有ソフトの一つで、簡単に言うと、見たいさきのPCのIPアドレスを指定して接続しに行くとそのPCの画面を自分側でも見ることができるというソフトです。これはVNC接続と呼ばれるそうです。もう少し具体的に説明します。
上の図１のような形になります。ここでVino-serverが登場します。文字通りVNC接続のサーバとしての働きを持ち、これは画面共有される側のPC内で動いているソフトでRemmina側に画面データを送る働きをしています。PCの設定で画面共有をONにしていると常に裏で動いていることが確認できます。まずこれが動いていることが前提です。この下で以下の様な流れになります。
(1) Remmina側で相手先のIPアドレスをGUI上で指定します。私たちはIPv4で指定しましたがコードを読む限りIPv6でも問題ないと思われます。
(2)Remmina側で接続というボタンを押すとプログラム上ではconnectが呼ばれます。すなわちVino-server側に接続しに行くことですね。ここからわかるようにRemminはクライアントとして働きます.。
(3)connectの通信が届くとVino-serverはacceptします。(当然PC使用者の許可が必要です) ソケットを作ってそこでTCP通信を行うという前期実験でも行なった流れとほぼ同じです。
(4)acceptまで問題なく処理されるとVino-serverは自らの画面データをRemmina側に常時送信していきます。
(5)Remmina側は１つのウィンドウ内で相手の画面を閲覧できます。
上のような流れが構造です。そして私達が取り組んだのは小見出しで述べたように connectをVino-server側からRemminaでaccpetする接続を作ろうということです。 動機としては、実際に学校でRemminaを使う場面を考えてみます。教員が学生のPC画面を見たいという場面が多々あると思います。このときにRemmina側から毎回毎回IPアドレスを指定して接続するようだと明らかに手間も時間もかかります。しかし逆向きですと大勢の学生が教員のIPアドレスだけを指定して接続するだけで教員は学生の画面を見ることができます。つまり効率化できます。これを実現するには上記で述べた逆向きの接続が必要になってくることになります。
つまり以下の図２のような構造を実現したいということになります。
では具体的に取り組んだことを細かく書いていきます。
具体的な取り組み
まずRemminaとVino-serverのソースを取ってくる必要がありますがgithubにありますのでググってgit cloneしてください。(どちらもC言語で書かれております)
環境 Ubuntu 18.04.3 LTS
メモリ 16GB
Remmina build方法
Remminaに関しては公式がbuild方法を出しているのでこれを脳死で実行しましょう()。
実行の仕方はremminaがあるフォルダに移動して
./remmina
これで大丈夫です。
-Vino-server build方法
$sudo apt install gnome-common
$sudo apt install libnotify-dev
$cd (フォルダの場所)/vino-master
$./autogen.sh
$make
$sudo make install
実行 ./vino-server (vino-serverというファイルのあるディレクトリで)
これで実行できます。Vino-serverは画面共有がONになっていると裏でもともとのが走っているので画面共有をOFFにしてから実行してください。(OFFにして実行しないとエラーメッセージが出るのでわかります)
実装までの流れ及び方針
ここでRemminaを触っていると気づくのですがListenermodeといういかにもな名前の選択肢があることがわかります。そのモードではGUIからポート番号を指定して接続を押します。 いかにも外部から何かしらの接続を待った状態 (accept待ち)が起きているのではないかと考えられます。ただこのモードはもともと正規版のRemminaにはない機能だったのでまだ正しく動くのかわからない状態でした。 ですのでとりあえずここを手探っていきたいと考えます。 がここから闇に入ります。まず動かし方が全くわかりません。どうやってListenermodeにつなげようとしてもいくら試してもできません。英語でググってもソースコードを読んでもいまいち接続の方法がわかりませんでした。 仕方ないのでVino-server側のmain関数のはじめにとりあえずTCPのクライアント機能を持たせてRemminaのListernermodeにつなげてみようとしました。するとつながることはデバッガを走らせながら実行することで確認できましたが、データの送信ができません。またncでつなげても全く同じでした。 つまり接続はできるけどその後の処理に正しく進んでくれないということがわかりました。
tcp通信に関しては以下のサイトを参考にしてコードを書くとよいかと思われます。
ここからVino-server側のプログラムをひたすら読んでいくことになります。どうやら通常用ではListenするためのソケットを作り それを使ってacceptするという構造が見えます。またaccepした後にrfbNewClient()という関数が呼ばれそこからIPアドレスの種類やパスワードに関する情報などを通信し最終的に画面データの送信が行われるという構造が見えてきました。ここで私はそれなら、ソケットを作るところでもともとあるListen用に加えてconnect用のソケットも作ってconnectできればrfbNewClient()という関数に飛べば良いのではないかと考えました。 この方針で実装し、コマンドライン引数からIPアドレスとポート番号を取れるようにして動かしたところ、やはり接続はできましたがそのあとの通信ができませんでした。つまりはじめと同じです。
発表前日まで途方に暮れていましたがチームメイトの方がほんとに頼りになってくれて、なんと動くように実装してくれました。どうしたかということですがこのrfbNewClient()という関数にはvino-serverの情報を持つ構造体(以下server構造体)の中の一部の変数が引数に与えられていました。最初の方針ではこのserver構造体が正しく実体を伴っておらず、つまり引数によくわからないものを入れていたというのが考えられました。 それならserver構造体が初期化されたあとにconnectしに行けば良いはずと考え、vino_server_new()みたいな名前のそれらしい関数にbreakpointをつけてデバッグするとname_acqired()という関数にたどり着きました。この関数が終わった時server構造体は初期化されることがわかりました。ここまできたらこの関数の最後にconnectそしてrfbNewClient()を呼べば行けるはず！ということでやってみると無事動きました！！ほんとに感謝です。 もう少し言うと単にname_acquired()の最後に置くだけではrfbNewClient()の引数のserver構造体がこのname_acquired()という関数のヘッダーファイルにないため一旦そのserver構造体が定義されているヘッダーファイルのあるファイルに飛んでそこで上の2つの関数を呼ぶという形になります。(実はここで半日程度止まりました笑) ということで我々のやりたかった逆向きの接続を完了できました。 相方いわく若干バグらしき状況があるみたいですが普通に使用する分では問題ないと思います。
具体的なコードですが、変更と言うより追加していった感じでして、細かいところをあげれば結構多いのでこのブログで載せるとかえって見づらくなると思われるのでconnect周りの必要最小限の処理だけ記載して詳しくは以下のリンクを参照してください。(tcp接続に関しては上で貼ったリンクのコードを基に今回使う機能だけを残して実装しております。) なんとか間に合わせた感じなのでかなり汚いコードになっていますが、vino-main.cとvino-server.cというファイルだけを見ていただくて、vino_connect_from_vino_server()という関数を作りname_acquired()関数の最後でconnect処理を行い、その後にrfbNewClient()を呼ぶ形が見て取れると思います。
まずコマンドライン引数からIPアドレスとポート番号を指定します。(グローバル変数にしてしまいごめんなさい)
#ifdef DEBUG char ip_add[256]; int port_num; #endif // DEBUG int main (int argc, char **argv) { if(argc==3){ strcpy(ip_add,argv[1]); port_num=atoi(argv[2]); } ... g_main_loop_run (vino.main_loop); ... return 0; }
次にconnectまわりの関数を作りました。
struct client_info { unsigned short sv_port; char *sv_ipaddr; }; typedef struct client_info cl_info_t; static int tcp_send(int sd, struct sockaddr_in *sv_addr, char *errmsg) { int rc = 0; rc = connect(sd, (struct sockaddr *)sv_addr, sizeof(*sv_addr)); if(rc != 0){ sprintf(errmsg, "(line:%d) %s", __LINE__, strerror(errno)); return(-1); } return(0); } int sd = 0; static int tcp_client(cl_info_t *info, char *errmsg) { struct sockaddr_in sv_addr = {0}; int rc = 0; sd = socket(PF_INET, SOCK_STREAM, IPPROTO_TCP); if(sd < 0){ sprintf(errmsg, "(line:%d) %s", __LINE__, strerror(errno)); return(-1); } memset(&sv_addr, 0, sizeof(sv_addr)); sv_addr.sin_family = AF_INET; sv_addr.sin_addr.s_addr = inet_addr(info->sv_ipaddr); sv_addr.sin_port = htons(info->sv_port); rc = tcp_send(sd, &sv_addr, errmsg); return( rc ); } static int initialize(int argc, char * ipaddres ,int port, cl_info_t *info, char *errmsg) { if(argc != 3){ sprintf(errmsg, "Usage: %s <ip-addr> <port>",ipaddres ); return(-1); } memset(info, 0, sizeof(cl_info_t)); info->sv_ipaddr = ipaddres; info->sv_port = port; return(0); } gboolean vino_connect_from_vino_server(int port_num,VinoServer *server){ if(port_num != 0){ int rc = 0; cl_info_t info = {0}; char errmsg[256]; rc = initialize(3, ip_add,port_num, &info, errmsg); if(rc != 0){ fprintf(stderr, "Error: %s\n", errmsg); return(-1); } rc = tcp_client(&info, errmsg); if(rc != 0){ fprintf(stderr, "Error: %s\n", errmsg); return(-1); } rfbNewClient(server->priv->rfb_screen,sd); } return TRUE; }
そして、name_acquired()という関数から上の関数を最後に呼び出します。
name_acquired (GDBusConnection *connection,
const gchar *name,
gpointer user_data)
{
VinoApplication *vino = user_data;
gboolean view_only;
gint i;
gboolean reject = FALSE;
...
/* Name is acquired. Start up the servers and register them with the
* listeners.
*/
if ((view_only = !vino_input_init (vino->display)))
g_warning (_("Your XServer does not support the XTest extension — "
"remote desktop access will be view-only\n"));
for (i = 0; i < vino->n_screens; i++)
{
VinoServer *server;
/* The server is initially "on-hold" while we set everything up. */
server = vino_server_new (gdk_display_get_screen (vino->display,
i),
view_only);
...
#ifdef DEBUG
vino_connect_from_vino_server(port_num,server);
#endif // DEBUG
}
}
苦労したところ
上でも少し述べておりますが、通信まわりを触った経験は少ししかなかったためいろいろな場所で苦労しました。これを読んでくれた方に参考になれば幸いです。
・デバッグがしづらい
これは通信周りですので1つのコードだけでデバッグするわけではありません。つまりクライアント、サーバ側ともにデバッガを立ち上げて実行しなければなりません。この時点で大変ですが、適切な位置にbreakpointを貼らないとすぐに接続されてしまい肝心の接続周りが見えません。このあたりに苦労しましたが、例えばconnectという関数やacceptという関数は必ず関わってきますのでまずこの名前からbreakpointを貼ることで かなり近づけることができます。そこからは1行ずつ進めていけば良いかと思われます。
・実装が変更と言うより追加になる
通常ですと、機能を変えるためには既存のコードの一部を変更、もしくは数行のコードを追加という作業がメインとなると思われます。これも変更箇所が多岐に及べば大変難しいですが、通信ですとソケットを作ってconnect...という仕様を作り新たなプロトコルで接続させるコード追加となります。そのためまずはどのような構造にするかという紙の上での議論から始まりました。そのうえで既存のコードではどのように実装されているかを調べ、その形に合わせ込めるように構造を考えなければなりません。私達も実験時間の3割ほどはそれに費やしたといいても過言ではないです。これに関してですが、サーバ、クライアントがconnect,acceptを行うわけですがその処理が行われた後をみると少しわかりやすくなると思われます。つまり接続された後は似ている処理をしているわけで、ここが新たな接続方針の終着点にしていけばよいからです。
課題
時間が限られていたということと動いたのが最終日の前日だったこともあって、やりたかったけどつめきれていないこともありました。
・Remmina側でVino-serverの画像データ送信を止める
これはRemminaへの多数接続状況では使っていない(あまり動かしていない)PCの画面の送信を止めることができればRemmina側のPCのメモリ削減につながると思われます。これも実装しようとしてみました。Vino-server側で画像を送ると思われる関数にbreakpointを貼りまくって何度もデバッガを走らせるとその関数部分にたどり着きました。rfbSendRectEncodingTight()という関数です。 emaccsデバッガでこの関数にbreakpointを貼って何度もcontinueをしていくと画像送信が少しずつされていることがわかりました。
これを標準入力でqが入るとこの関数が呼ばれずすなわち画像送信がストップし、rで また再開するみたいなプログラムは作れ、実際に動くことは確認できました。 しかし現状Vino-server側での操作できる状態であって、これではそんなに使い物にならないですよね。笑 また相方が言うには送信に使われている関数の中身を書き換えるやり方は良くないみたいなのでコードとしてもイマイチなので再考が必要と考えられます。
終わりに
本実験では大規模ソフトウェアを手探るという内容でしたが10日間の7日くらいはほんとに何もコードをかけませんでした。しかし例えばデバッグの仕方や、大規模なソフトウェアの構造がどういうものなのか またbuildの仕方までわからないことだらけだったのですがそれらを少しだけですができるようになったといえる実験でした。普段は競技プログラミングとかの短いコードを書くというのがメインでしたのでこのような 普段ひとりではとっつきにくいことをやることができ、かつ悩んだりすることも楽しかったりして最高の実験でした。
最後までたくさんのアドバイスをしていただいたり何時間もつきっきりで見ていただいた先生そしてTAさんにはほんとに感謝しかありません。ありがとうございます。
ABC140-D - Face Produces Unhappiness
今日はこの問題を取り上げます。非常に考察が楽しかったです。
リンク
エンジニアとして生きていくにはこの問題のように物事をどう簡単なものに帰着させて行くかという思考も実装力に加えて大事な気もするので、こういう能力も伸ばして行きたいと思います。
考察
LとRの区切りの個数と幸福な人の数の関係が相関を持っていることに気づけばあとは簡単。サンプルを見ると
LLLLLRRRRR
はLRの区切りが1ですね。ここでこの状態の幸福な人の数は(10-1)-1=8となります。
全員が同じ方向を向いている時答えはn-1なのでそこから区切りの数を引いたものが答えになりますね。つまり元の状態から区切りを最小化すれば答えは最大になるとわかります。ではK回の試行でどこまで区切りを減らせるか考えると、例えば
LRRRL
のとき区切りは2です。ここでRを反転すればLLLLLになり区切りは0になります。つまり1回の操作で区切りを2つ減らせます。区切りの数は0未満にならないことに注意すると以下のような簡潔なコードで解くことができます。
#include <bits/stdc++.h> using namespace std; int main(){ int n,k; string s; cin>>n>>k>>s; int cnt=0; //区切りをカウント for (int i = 0; i < n-1; i++) { if(s[i]!=s[i+1]) cnt++; } cout<<n-1-max(0,(cnt-2*k))<<endl; return 0; }
Educational Codeforces Round 64 A.Inscribed Figures
A.Inscribed Figures
こんにちは。今回Codeforcesの方にも参加してみたのでその中で解けたというかある意味話題になった問題について書きたいと思います。
詳しくはCodeforcesのリンクを見てください。 問題はこちら
A Inscribed Figures問題の概要をざっくり書くと、丸、四角、三角形を与えられた順に内側に内接させる形でどんどん埋めていき、合計で何点と接しているか求めよという問題です。例えば丸→三角形ですと3点で接します。同様に三角形→丸も3点で接します。ただし四角→三角形の場合下の底辺で共通部分できてしまいます。この場合はInfiniteと出力することになります。以上ざっくりとした問題の説明です。
コンテスト中に考えたこと
とは言っても特になくて(笑)ただ紙に具体的に図形を内包させて何点で接するかあるいはInfiniteなのか考えただけでした。コードにコメントアウトしているので解ると思います。 ぱっと実装して投げたところpretestは普通に通りホッとしてました。...がここでなんとpretestにミスが見つかりリジャッジされることに...codeforcesならではなんですかね。 知りませんが()。 そしてリジャッジの結果なんと落ちました。(1500人くらいは落ちてた気がする)どうしてなのかなーと考えているうちになんとunratedに...。codeforcesの洗礼を浴びてしまいました。 ただ気になるので深く考えたところ、四角→丸→三角の並びのときに上の頂点が一致してしまいます。すなわちこのパターンがあるときは1だけ引かなければいけません。いわゆるコーナーケース ですね。これを直して無事通りました。 問題としては易しいので英語の勉強がてらやってみてはいかがでしょうか。 以下コードです。
#include <iostream> using namespace std; int main() { int n; int a[110]; cin>>n; for(int i=0;i<n-1;i++) cin>>a[i]; //1が丸 2が三角 3が四角 // 四角→三角や三角→四角は底辺が重なるので"Infinite" for(int i=0;i<n-1;i++){ if((a[i]==3 && a[i+1]==2) || (a[i]==2 && a[i+1]==3) ){ cout<<"Infinite"<<endl; return 0; } } int cnt=0; // 丸と三角の場合+3 丸と四角の場合+4 for(int i=0;i<n-1;i++){ if((a[i]==1 && a[i+1]==2) || (a[i]==2 && a[i+1]==1) ) cnt+=3; else if((a[i]==1 && a[i+1]==3) || (a[i]==3 && a[i+1]==1) ) cnt+=4; } // 四角→丸→三角のとき上の接点が重なるので-1 for(int i=0;i<n-2;i++){ if(a[i]==3 && a[i+1]==1 && a[i+2]==2) cnt--; } cout<<"Finite"<<endl; cout<<cnt<<endl; return 0; }
diverta 2019 Programing Contest C-AB Substrings
diverta 2019 Programing Contest C-AB Substrings
今日はこの問題の僕の実装を書きたいと思います。
問題の概略は、与えられるいくつかの文字列すべてをうまくつなげてそのなかに"AB"という部分文字列が最大でいくつ作ることができるかという問題です。
コンテスト中の思考
まず大雑把に問題を把握し、考えたこととして、とりあえずそれぞれの文字列に"AB"がいくつあるか考えて、後は端の処理が必要かなという感じです。ここでそれぞれの文字列で最初がB最後がAならそれらをくっつければ"AB"ができるよねと思い、それは何個できるのか考えているとわりとすぐに最初がBの文字列の個数と最後がAの個数の小さい方分だけ"AB"ができるよねと思いました。具体的にはこんな感じです。
4
BFS
XYZA
こんな例ですと、
BCD XYZA BFS
みたいにつなげば良いですね。要は端同士をつなげるのだから小さい方分だけ"AB"ができるよね。という感じです。これをパッと実装し投げたところ普通に落ちました()。そこで色々コーナーケースのようなものを考えているとB~Aみたいな文字列が出てきた場合処理に戸惑うなと考えました。簡単な例を出すと、
3
BCA
BDA
BEA
みたいな感じです。これでは最初のように考えると答えはmin(3,3)=3となりますが正しくは
BCA BDA BEA
とつないでも答えは最大で2にしかなりません。つまりこのような場合を別に考えなければいけないと思いました。ここから無限に時間を使い色々考えた結果以下のように場合分けすると個人的にはスッキリしました。
- B~X,Y~Aみたいな文字列をそれぞれカウント
- B~Aみたいな文字列をカウント
この下で
1.B~Aがない時、先ほどの説明通りが答え
2.B〜Aしかない時、先ほどの説明通りの答え-1になる
3.B〜AもB~XもA~Yもある時(B~X,Y~Aはどちらも0を除く)
それぞれの文字列内にある"AB"の数+(B~Aの数+B~X,Y~Aの小さい方の数)
3の場合がわかりにくいかもしれません。具体例を考えます。
6
BDA
BEFA
BSX
YTA
YUA
これのつなげかたは
YTA BDA BEFA BGA BSX YUA で4が答えです。実際にcase.3に当てはまっていることを確かめてください。これを以下のように実装しました。適宜コメントアウトしています。
#include <iostream> #include<vector> using namespace std; #define EPS (1e-7) #define INF (1e9) #define PI (acos(-1)) int main() { int n; vector<string> s(n); cin >> n; for (int i = 0; i < n; i++) cin >> s[i]; int cnt = 0; //まずはそれぞれの文字列にABが何個あるか数える for (int i = 0; i < n; i++){ for (int j = 0; j < s[i].size()-1; j++) { if(s[i][j]=='A' && s[i][j+1]=='B') cnt++; } } //一番左にBが何個あって一番右にAが何個あるか調べる //このときB〜Aみたいな文字とB~X、Y〜Aみたいな文字列を区別する int left_B=0,right_A=0; int x=0; for(int i=0;i<n;i++){ int last = s[i].size() - 1; if (s[i][0] == 'B' && s[i][last] != 'A') left_B++; if (s[i][last] == 'A' && s[i][0] != 'B') right_A++; if (s[i][0] == 'B' && s[i][last] == 'A') x++; } //B~AがなかったらBの数かAの数の小さい方が答え(文字列をくっつけていくイメージ) if(x==0) cout<< cnt+min(left_B,right_A)<<endl; //もし文字列がB〜Aの形だけなら合計から１日引く必要がある(端同士は繋げられない) else if(left_B==0 && right_A==0 && x>=1) cout<<cnt+x-1<<endl; //それ以外ではB~A部分の数+B~XとY~Aの小さい方の和を考えれば良い else cout<<cnt+x+min(left_B,right_A)<<endl; return 0; }
ABC125 C-GCD on Blackboard
ABC125 C-GCD on Blackboard
どんな感じでブログを書けば良いかわからないのでとりあえず先日行われたABC125のC問題をどのように自分が考えたか書き連ねたいと思います。 なおこれはあくまで僕の思考過程を書くものであって、決して最適な方法ではないと思われますし、もしかしたら嘘解法の可能性もありますので、参考程度に流し読みしてくれたら嬉しいです。
当然ですが与えられたある数の約数が答えの候補になりますので、そこから絞ればいけるのでは考え、とりあえずソートし一番小さい数に注目しました。(このソートは不要でしたね) この１番小さい数と他の全ての数とのgcdをひとつずつとっていきその値が最も小さい数１つを消せばそれが答えになるはずです。具体的に、(4,6,7,12)のような数列を考えました。
gcd(4,6)=2, gcd(4,7)=1, gcd(4,12)=4
となり7を消せば最大値2が得られます。とりあえずこのように実装し投げたところいくつかWAとなったため、考察を深めました。一番小さい数自体が不要なケースもあることに気づき(3,8,10,12のような場合)、この一番小さい数を消す場合と他で消す場合で、gcdが大きくなる方を出力するように変えることでACできました。(なおコンテストが終わってから累積gcdなるものを知り、勉強になりました。)以下コードです。
#include <iostream> #include <algorithm> using namespace std; int gcd( int a,int b){ if (a%b==0){ return b; } else{ return gcd(b,a%b); } } int N; int a[100010]; int main() { cin>>N; for(int i=0;i<N;i++) cin>>a[i]; //1番小さい数と２番目に小さい数を見つけるためにソート sort(a,a+N); int min_gcd=a[0]; int remove_index=0; //a[0]とのgcdを取り一番小さくなったindexを書き換えたい for(int i=1;i<N;i++){ int s=gcd(a[0],a[i]); if(s<min_gcd) { min_gcd=s; remove_index=i; } } //1,まずはa[0]を書き換えた時 int ans1=a[1]; for(int i=1;i<N;i++){ ans1=gcd(ans1,a[i]); } //2,それ以外、つまりa[remove_index]を取り除いた時のgcd int ans2=a[0]; for(int i=0;i<N;i++){ if(i==remove_index) continue; ans2=gcd(ans2,a[i]); } //1,2の大き方が答え cout<<max(ans1,ans2)<<endl; return 0; }
