2018-12-11

プリティーライブ2018参加記

「ぜい！」

私の渾身の一撃が、彼女の剣を砕き腹を裂いた。これがこの戦いの終着だろう。私もこの傷では、もう帰還は叶わない。最期に話をするために彼女のそばに寄る。

「流石ね... ねぇ知ってる？私の国には転生のお伽話があるのよ。 ”正しく生きれば、魂は死なず幸せな国に生まれ変わる”って。私は正しく生きたかしら？もし生まれ変われるのなら、今度は別の形であなたと出会って、街に行ったり、屋台を見たりしたい。今度はこんな形じゃなく、ただの娘として.... 」

そこまで言うと彼女は、苦しそうに咳をした。

「ねぇ、笑って？最期にはあなたの笑顔が見たいの」

私は笑う。多分それはとてもぎこちないものだけれど、それが今の私にできるすべてだ。

彼女を看取ると、私も横になり空を眺めた。

暮れる空は赤く、下界の争いごとなど関係ないように広い。

もし彼女の言うお伽話が本当だというのなら、争いのない国に生まれたい。そして彼女と出会い、また恋をして、結ばれたい。

そんなの夢物語とは思う。ただ願わずにはいられない。私は目を閉じ、微かに赤い視界の中で、奇跡の存在をただ祈った。

アニメジャーナル2019年1月号。

巻頭インタビュー「プリティフレンズ主演お二人に聞いた魅力と意気込み」

--- 今回のお話はアイドルを志す二人の主人公が、時にはぶつかり、時には励まし合いながら、トップアイドルを目指していくお話と伺っております。お二人の演じるキャラクターの第一印象はいかがでしょうか？

「はい、私の演じるシュウカは本当に頑張り屋さんなんですけど、あんまり人に努力を見せるのが好きじゃなくて、何事にも完璧を目指しているんです。だから私も、完璧を求めるシュウカに負けないように、頑張ろうと思います！」

「私の演じるルルはどちらかというと柔和な感じで、はじめは厳しいシュウカに対して戸惑ってしまうんですね。でもシュウカの厳しさはファンのためなんだって知ると、自分も負けないようにがんばろうっていう。だから私もシュウカに負けないように、また厳しすぎるシュウカを支えられるに、がんばっていきます！」

--- ありがとうございます。お二人のご共演というと、「天黒のパラドクス」以来ですよね。あれはかなり暗い世界観のお話でしたが、ギャップに戸惑ったりはしませんか？(笑)

「そうですね(笑)。でもあのお話では、二人は想い合っていたのに戦い合ってしまう間柄ということで、結構モヤモヤしてしまうことも多かったんですね。」

「どうしてこうなっちゃうの〜！って(笑)」

「なので今回は、二人の思い通り(?)に仲を深められる作品ということで、鬱憤を晴らすわけではないですが、楽しみです！」

ああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ！！！

プリティーライブ2018に行ってきました！！！本当に夢のひと時で、声優さんたちが本当にキャラクターになりきってくださっているのを感じました。本編は終わっても、声優さんたちの中で確かにキャラクターが生きていることを感じました。本当に、プリパラが終わって悲しかった私には、感無量です😂😂😂

(プリチャンも大好きです。特にメルメルが好きです)

ライブで改めて認識したんですが、結構プリパラの声優をされていた方がプリチャンでも声優をされているんですね。ライブから帰って布団の中にいた私の中で「声優さんの中でキャラクターは生きている」「声優さんは別キャラの声優もしている」がつながって「もうそれって転生じゃん！」「世界を越える存在じゃん！」って一人大盛り上がりしていました。妄想の結果上の文書が生まれました。

捨てるのも偲びないので、簡素ながら参加記を添えてここに供養します。

関係者の皆様、本当にありがとうございました。

2018-10-04

KUPC 2018 参加記(ABCD解き)

コンテストページ：https://beta.atcoder.jp/contests/kupc2018 提出：https://beta.atcoder.jp/contests/kupc2018/submissions?f.User=skjmp

結果は229:49で800点(7WA) でした。

A

素直に要素について面積を求めて最大値を記憶すれば良さそうです。

提出コードは以下になりました。

#include <bits/stdc++.h>
#define REP(i, a, n) for (int i = (a); i < (int)(n); ++i)
#define REPC(i, a, n) for (int i = (a); i <= (int)(n); ++i)
#define ALL(t) t.begin(), t.end()
#define RALL(t) t.rbegin(), t.rend()
#define MATINIT(type, row, col, init)                                          \
  vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout << (cond ? "Yes" : "No") << endl;
#define YES(cond) cout << (cond ? "YES" : "NO") << endl;
using namespace std;
using LL = long long;
using ULL = unsigned long long;
template <class T> using VEC = std::vector<T>;
template <class T> using MAT = std::vector<std::vector<T>>;
void DUMP() { cerr << endl; }
template <class Head, class... Tail> void DUMP(Head &&head, Tail &&... tail) {
  cerr << head << ", ";
  DUMP(std::move(tail)...);
}
template <typename T> ostream &operator<<(ostream &os, vector<T> &vec) {
  os << "{";
  for (auto v : vec)
    os << v << ",";
  os << "}";
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  os << "[" << p.first << " " << p.second << "]";
  return os;
}

int main() {
  int n;
  cin >> n;
  VEC<int> s(n), a(n);
  REP(i, 0, n) cin >> s[i];
  REP(i, 0, n) cin >> a[i];
  LL ma = 0;
  REP(i, 0, n) { ma = max(ma, (LL)s[i] * a[i]); }
  cout << ma << endl;

  return 0;
}

掛け算をすることに気づいた当時の私は、最大値を格納する変数maをlong longで宣言していますが、制約を見るとたかだか100*100なのでintで十分でした。

B

自機の前3マスだけが移動可能な範囲で、同じマスを繰り返し通ることはない
盤面が最大でも10*10

なので、全探索で通りそうです。最初の自機の位置からはじめて、前3マスを再帰的に探索することで解くことにしました。ただ、経路復元をする必要があるところが厄介そうです。

DFSで探索を行い、1つ答えが求まった時点で探索を打ち切れば探索木の帰りがけ順が答えになりそうです。コードは下記になりました。

MAT<char> c;//弾幕ゲーム画面
int H, W;
list<char> ans; // 答えとして出力する経路を格納

bool dfs(int nh, int nw) {
  //自機の新しい位置として(nh, nw)を取り、
  //ゴール到達なら1、探索継続不可なら0を返します。
  //その判断がつかない場合、(nh, nw)の前3マスの探索を行います。

  //DUMP(nh, nw);
  if (nh == -1) {
    return 1;
  } else if (nw < 0 || W <= nw) {
    return 0;
  } else if (c[nh][nw] == 'x') {
    return 0;
  } else if (nh == 0 && c[nh][nw] != 'x') {
    return 1;
  } else {
    REP(i, 0, 3) {
      if (dfs(nh - 1, nw - 1 + i)) {
        // 答え用に経路を保存していく
        char t;
        if (i == 0)
          t = 'L';
        else if (i == 1)
          t = 'S';
        else
          t = 'R';
        ans.push_front(t);
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  ans = list<char>();
  cin >> H >> W;
  c = MATINIT(char, H, W, 0);
  REP(h, 0, H) REP(w, 0, W) cin >> c[h][w];
  //DUMP(c);
  bool possible;
  REP(w, 0, W) {// 's'の位置から探索を始める
    if (c[H - 1][w] == 's')
      possible = dfs(H - 1, w);
  }
  if (possible) {
    for (auto v : ans) {
      cout << v;
    }
  } else
    cout << "impossible";
  cout << endl;
  return 0;
}

C

入力がない問題ははじめてだったのでびっくりしました。 C++で答えとなる文字列を定義して提出していましたが、提出言語をTextにしたほうが楽だったようです。

よくわからなかったのでなんとなく次のような系列を出していました(1つ目はWAです)

......#..
.....#...
....#....
...#.....
..#......
.#.......
#.....###
......#..
......#..

......#..
.....#...
....#....
...#.....
..#......
.#####...
#.....###
......#..
......#..

これで33点を出し、ここではじめて順位表を見ました。この問題の満点が何点なのか知りたかったのです。200点でした(そういえば配点にも200点て書いてますね）。

さて、気を取り直して、満点解法を目指します。点数計算が$floor(200/max(1, N-10))$ ただしNは置いた#の数なので、11個まで置けます。

1個#を置くときに、それで遮れるラインが多いと嬉しそうです。また「このラインを塞ぐためにはこのマスのうちのどこかに置かなければならない」という風に置くマスの候補を限定も出来そうです。

とりあえず絶対置かなそうな場所を考えました

XX.....XX
XX.....XX
.........
.........
.........
.........
.........
XX.....XX
XX.....XX

そして、それぞれの端2列と、2行を塞ぐために、a~hので示した位置に1個ずつ、#を置く必要があることに気づきました。

XXcccccXX
XXdddddXX
ab.....ef
ab.....ef
ab.....ef
ab.....ef
ab.....ef
XXgggggXX
XXhhhhhXX

ここまでで8個の使いみちが決まって、残り3個で真ん中らへんのラインを塞ぐことになります。

XX..#..XX
XX..#..XX
.........
.........
##.....##
.........
.........
XX..#..XX
XX..#..XX

↑適当に置きました。置いたあとこんな置き方では足りないことに気づいたので、a~hにおく#の位置を工夫して、より多くのラインが塞げるようにします。

XX.#...XX
XX...#.XX
.........
#......#.
.........
.#......#
.........
XX.#...XX
XX...#.XX

↑左右（上下）の#を対になるように置くことで距離を6に抑える天才的な発想をしました。しかしこの状態で真ん中付近を通るラインを3個の#で塞げないか試しましたがダメでした。

XX#....XX
XX....#XX
#......#.
.........
.........
.........
.#......#
XX#....XX
XX....#XX

↑別パターンを試しました。この試行はうまくいってACしました. 答えは以下です。

..#......
......#..
#......#.
...#.....
....#....
.....#...
.#......#
..#......
......#..

感想ですが、配点と計算方法から「満点解法の場合における#の数」を出していれば、WAが減らせたと思います。また、天才的な発想をした直後に試した系列がダメだとわかってから、別パターンを試してACするまでの時間が長かったので、「ある仮定のもとに考察を進めている(これがダメだとわかったら別パターンの HOGEで考察をすすめるべき)」という状態に意識的であれたらいいなと思いました。

D

何もわからなかったのでとりあえず実験をしました。 f:id:hoyamag:20181004215440j:plain

3, 4, 5, 7でmodを取った時の値とその偶奇を書いています。そして、modを取った値の偶奇が元の数値の偶奇と違っていれば丸を書いています(シャーペンなので見えづらいですね)。

mod 3, mod 5の実験で、「modを取った値の偶奇と元の値の偶奇の不一致は周期的に出てくる」っぽいことがわかりましたが、それで解けるまで落ちてきませんでした。
mod 4の実験で、「偶数でmodをとっても、元の値と偶奇は変わらない」っぽいことがわかりました(今思えば根拠弱過ぎな気がします)。
mod 7の実験で、「14未満までの範囲だけを考えれば、7未満は元の値と偶奇が変わらず、7以上は偶奇が変わることがわかりました」。

mod 7の実験結果から、1回のクエリで解の候補となる区間を半分に出来そうなことがわかりました。ただ、

解の候補区間 $1 \le X \le 10⁹$ に対し発行できるクエリが$1 \le q \le 10⁹$なので、答えが1e9の場合特別な処理が必要そう(答えの数値の本来の偶奇が取れないので)($1 \le q \le 10⁹+1$だと嬉しかった)
- 答えが1e9の場合は、最初のクエリ(1e9)を与えた時に'even'が帰ってきて、それ以降のクエリでは毎回'odd'が返ってくることが実験でわかったのでそれで判定することにしました

ということで、解の候補区間を二分する奇数でクエリを発行していくニブタンを書きます。クエリの数30回は、ぎりぎりなので、余計なクエリを発行しないように気をつけましょう (そもそも事前にチェックしましょう)(6WAくらいしました)

コードです.

int main() {
  LL left = 1, right = 1e9;
  LL maxRange = right;
  cout << "? " << right << endl;
  string original;
  cin >> original;
  int cnt = 1;
  LL mid;
  string midEvenOdd;
  bool maxFlag = original == "even";// 答えが1e9だったときを判定する用
  while (abs(right - left) > 2) {
    ++cnt;
    mid = (left + right) / 2;
    mid += mid % 2 == 0 ? 1 : 0;
    DUMP(cnt, left, mid, right);
    cout << "? " << mid << endl;
    cin >> midEvenOdd;
    if (midEvenOdd == original) {
      right = mid;
    } else {
      left = mid;
    }
    maxFlag = (maxFlag && midEvenOdd == "odd");
  }
  mid = (left + right) / 2;
  DUMP(cnt, left, mid, right);
  if (maxFlag) {
    cout << "! " << maxRange << endl;
  } else {
    // midに奇数を取るよう補正した関係上、
    // この時点でまだ解の候補に{left, left+1}の2つがあります。
    // {left, left+1}の偶奇見て、最初のクエリでとった偶奇と等しい方を答えにします。
 
    REP(i, left, right) {
      string s = (i % 2 == 0 ? "even" : "odd");
      if (s == original)
        cout << "! " << i << endl;
    }
  }
  return 0;
}

感想ですが、

にぶたんするのはいいけどクエリの最大回数で探索が終わるかは書く前に考えたほうが良い

2018-06-17

ABC100参加記

問題: https://abc100.contest.atcoder.jp/assignments
sub: https://beta.atcoder.jp/contests/abc100/submissions?f.User=skjmp

A

隣り合ったケーキは同じ人が取れない

からサイズの半分が、一人が取れる限界な気がします。サイズを見ると16です。境界が怖いのでサンプルで確認すると、素直にサイズの半分が一人で取れる最大のようです。

とりあえずA, B両方共8以下ならOKだろうというような気持ちになりました。

int main() {
    int a, b;
    cin >> a >> b;
    if (a <= 8 && b <= 8)cout << "Yay!";
    else cout << ":(";
    return 0;
}

ただ、A(またはB)が0だった場合も同じ答えになるか怖かったので図を見て確認します。
大丈夫でした。投げます。通りました。

B

(今回通ってないです)
サンプルを見ると各Dで候補の数字は

D=0 -> 1,2,3,4,...,99
D=1 -> 100,200,300,...,9900
D=2 -> 10000,20000,30000,...,990000

に見えるので、条件を満たすN番目の数字は

D=0 -> N*1
D=1 -> N*100 
D=2 -> N*100*100

に見えます。コードを生やして

int main() {
    ll d, n;
    cin >> d >> n;
    ll k = pow(100, d);
    cout << k*n;
 
    return 0;
}

サンプルを確認して出します。WAでした。「pow関数がdoubleを返すからか？ループにしよう」なんて期待薄な修正をしてWAを重ねます。
この時点でBに取り組み始めてから15分経っていました。順位表を見ると人々はBを通しているので、問題文のミスというのはなさそうです。

これ以上粘ってA1完というのはつらい
自分のABCの印象としては「Cは高確率で解けて運が良ければDまで解ける」

なのでCに進みます。

C

数列に操作を繰り返して、何回操作できるでしょうか？問題がでました。操作は

a_iを2分の1
a_iを3倍

で、操作を継続できる条件は

a_iがすべて整数であること

です。「3倍だけすれば続くな。2分の1は数字が減るから嬉しくないな」なんて考えますが

操作はすべてのa_iに行わなければならない
操作のうち1つは、2分の1する操作でなければならない

だそうです。

「奇数には2分の1操作は行えない」ことがわかるので、奇数には3倍操作だけが割当たることがわかります。「奇数に3をかけて偶数に化けたりしないだろうか？」なんてことを考えますが、 (2n-1)(2n-1)=4n²-4n+1で偶数+1になるのでなさそうです。

次に偶数の取り扱いを考えます。
偶数が2分の1操作を繰り返されて1(or 他の奇数)になると、その数字はもう2分の1操作に使えなくなるので、1回の数列操作で2分の1操作される数は1個だけにしたいです。
他の偶数には3倍する操作を割り当てるとして、「偶数に3倍操作を行った場合に、2分の1できる回数に影響はあるか？」という疑問が湧きました。 2とか4とか6に3をかけて、特に変わらないことを確認します¹。

実装に移していきます。

「3倍操作によって、数列の操作回数に影響はない」
1回の数列操作で2分の1されるのは1要素のみ

ことがわかったので、数列の各要素について、2で割れる回数を計算し、その総和を取ると答えになりそうです。

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, 0, n)cin >> a[i];
    int cnt = 0;
    rep(i, 0, n) {
        if(a[i] % 2 == 1)continue;
        while (a[i] >= 2){
            a[i] /= 2;
            cnt++;
        }

    }
    cout << cnt << endl;
    return 0;
}

サンプルが合いません！ repループの末尾にcerr<<cnt<<endl;を入れて確認します。 84になってましたがよくわかりません。 VisualStudioのデバッグモードで終了時の配列aの中身を確認します。「奇数だったものはその数字のまま」「他の数字は1」なっています。「偶数全部が1まで割り切れるっておかしいでしょ」ということでバグに気づきました。直します。

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    rep(i, 0, n)cin >> a[i];
    int cnt = 0;
    rep(i, 0, n) {
        while (a[i] >= 2 && a[i] % 2 == 0) {
            a[i] /= 2;
            cnt++;
        }
//        cerr << cnt << endl;

    }
    cout << cnt << endl;
    return 0;
}

投げます。通りました。

D

いい感じに物品を選ぶ問題が出ました。

ケーキは3属性持っている
評価は各属性の評価値の和
属性の評価は総和の絶対値で行う

問題見てコードの入力部分書こうと思ったんですが、ケーキを3つのvectorで持つかtupleのvectorで持つか悩んだので書きませんでした。

属性の評価が総和の絶対値で行われるので、例えば属性xyzのうち属性xを良くしようと思ったら

xが正のものをできるだけ集める
xが負のものをできるだけ集める

の2パターンが存在することがわかります。

各属性ごとに貪欲に取ろうと考えました。xを最適にしたらy, zが最適にならないケースがありそうでこれは無理そうです。

「もし属性の取りうる値が正だけだったら楽なのになぁ(ケーキごとに3属性の和をとって、その和をソートして上から取ればよいので)」などと考えました。

いまいち方針が浮かばないのでdpを考えました(私にdp力はないです)。とりあえずdpテーブルを「dp[i][j]: i個のケーキからj個選んだ時の最適値」として考えます。
dpテーブルの遷移がうまく考えられません。 dp[i+1][j]を(取りうるケーキが増えた時を)考えた時、新しいケーキのもつ属性値が既存の最適値を良くするかどうかがわからないので(既存の最適値と符号があってるかわからない)。
dpテーブルの定義を変えます。 dp[i][j]: i個のケーキからj個選んだ時の、xの総和とyの総和とzの総和」。
これでも遷移がうまく考えられません。 xyzそれぞれ、正で集めるときと負で集めるときの情報がないと、最適な状態に遷移できない気がします。そこでdpテーブルに、xyzの正負のパターンを追加することを考えます。数えると8通りで、現実的な数です。

ここで「全部正だったら楽なのに」妄想を思い出します。各属性の正負のパターンを全列挙して、正負のパターンにより各属性値に-1をかけて評価すれば、「全部正だった」場合にうまくいくアルゴリズムが使えて、答えが出る気がしてきました。

「ケーキのどれかの属性でケーキをソートしたい」みたいなことはなさそうなので、ケーキは3つのvectorで持つことに決めて、コーディングしました。

#define ll long long
#define all(t) t.begin(), t.end()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));

int bit(int n, int th) {
    return (n >> th) & 1;
}
int main() {
    int n, m;
    cin >> n >> m;
    auto cake = mat(ll, 3, n, 0);
    auto tmpcake = mat(ll, 3, n, 0);
    rep(i, 0, n) {
        // 値取得ループ。初めはcin>>x[i]>>y[i]>>z[i];で取っていたが、
        // bit列で全探索する都合上数値で扱えたほうが良いのでvector<vector<>>で書き換えた
        rep(j, 0, 3)cin >> cake[j][i];
    }

    ll ma = 0;
    rep(com, 0, 8) {
        // このループでどの正負のパターンを探索するかはcomのビットパターンで判別する
        // 例えばcom=0b110なら、属性xでは正を集めて、属性y, zでは負を集めるようなイテレーション
        rep(i, 0, 3) {
            // 各属性について、comのパターンによって-1をかけるやつをやる。
            int sign = (bit(com, i) ? -1 : 1);
            rep(j, 0, n) {
                tmpcake[i][j] = sign*cake[i][j];
            }
        }

        // 補正が終わったので、単純にケーキの3属性の和が大きいものを上から取れば、
        // その正負のパターンでの最適な取り方になるようになった
        vector<ll>sum(n,0);
        rep(j, 0, n) {
            // ケーキごとに属性値の和を取る。
            rep(i, 0, 3) {
                sum[j] += tmpcake[i][j];// サンプルが合わなくて見たら += じゃなくて = になってた
            }
        }
        sort(all(sum));
        ll whole = 0;
        rep(k, 0, m)whole += sum[k]; // 上からM個取るループ
        ma = max(ma, abs(whole)); // サンプルが合わなくて見たらabsしてなかった

    }
    cout << ma << endl;;
    return 0;
}

投げます。通りました。やったね！

B(再チャレンジ)

N=100で変なことになるのはわかったんですが、お恥ずかしながら、「解なしでは？」「そんなわけないやろ」という思考のループに陥りました。頭の中で

「N*100^D」で列挙できる
N=100で(D+1)回割れてしまう

が両立して、処理が不可能になっていた感じがします。。
素直にN=100付近の数直線を書き、問題分に書かれた「100でちょうどD回割れる」の条件を満たす数に○でも打っていけばよかったと思います。

今にして思えば。2で割って整数になる数は素因数分解したとすると(2ⁿ)*hogeで表されて、2で割る操作はnを-1する操作に他ならないので、ちょっと無駄な実験でしたね。↩

2018-06-14

vagrant sshしたらまっさらなVMがそこにあった

環境 Ubuntu 16.04 LTS
vagrant 2.1.1
VirtualBox Graphical User Interface Version 5.1.34_Ubuntu r121010

homeディレクトリ以下にあったディレクトリが消えている

$ vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Importing base box 'bento/centos-7.2'...
==> default: Matching MAC address for NAT networking...
==> default: Checking if box 'bento/centos-7.2' is up to date...
==> default: Setting the name of the VM: rails_tutorial_default_1528677272770_17615
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
    default: Adapter 2: hostonly
==> default: Forwarding ports...
    default: 22 (guest) => 2222 (host) (adapter 1)
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2222
    default: SSH username: vagrant
    default: SSH auth method: private key
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: 
    default: Vagrant insecure key detected. Vagrant will automatically replace
    default: this with a newly generated keypair for better security.
    default: 
    default: Inserting generated public key within guest...
    default: Removing insecure key from the guest if it's present...
    default: Key inserted! Disconnecting and reconnecting using new SSH key...
==> default: Machine booted and ready!
==> default: Checking for guest additions in VM...
==> default: Configuring and enabling network interfaces...
    default: SSH address: 127.0.0.1:2222
    default: SSH username: vagrant
    default: SSH auth method: private key
==> default: Mounting shared folders...
    default: /vagrant => /home/hoyamag/Codes/rails_tutorial
$ vagrant ssh
[vagrant@localhost ~]$ ls
[vagrant@localhost ~]$ ls
[vagrant@localhost ~]$ ls -a
.  ..  .bash_logout  .bash_profile  .bashrc  .ssh  .vbox_version
[vagrant@localhost ~]$ logout

入れていたソフトも抜けている

[vagrant@localhost ~]$ rails -bash: rails: command not found

vagrant vm 消えたでぐぐる

どうやら既知の現象らしいです vagrant upすると、以前インストールしたRubyやRailsなどの中身がすべて消えてしまう。今まであったVMは消えたわけではなく、連携が切れただけのようです。その状態で'vagrant up'したため新規のVMが作成されたという。

ただ、ここで直し方として紹介されている Vagrantの仮想マシンとの紐付けの直し方 - ウチのメモがvagrant 1.2.7向けの話だからか、「.vagrantファイルを修正して直す」の部分が自分の環境と合致しませんした(.vagrantはディレクトリなので)。ということで'vagrant vm missing'でぐぐってそれっぽいページを見つけました( Re-associate vagrant with vm · Issue #1755 · hashicorp/vagrant · GitHub)。手順がわかったので直します。

結論

直りました。
実際の手順を知りたい方は「やった手順(ログ目的のため失敗手順含む)」を参照してください。
結論としてはVagrant lost all of my VMs · Issue #5144 · hashicorp/vagrant · GitHub を見るのが一番でした。
再発防止策としては、下記が有効そうな気がします(試してません)。

'vagrant up'する前に'VBoxManage list vms'してVMが紐付いているか確認する
boxファイルを作って復旧を容易にしておく(参考:自分仕様のboxファイルを作成する)
.vagrantフォルダをバックアップしておく(？)

やった手順(ログ目的のため失敗手順含む)

vagrantとVMの紐付けの回復

VirtualBoxのVMはディレクトリ'~/VirtualBox\ VMs/'にあるそうなので、そこにあるVMを確認します(コマンド'VBoxManage list vms'だと、1つしかVMが出てこなかったので)。

hoyamag@hoyThinkpad13:~/VirtualBox VMs$ ll
total 20
drwx------  5 hoyamag hoyamag 4096  6月 11 09:34 ./
drwxr-xr-x 45 hoyamag hoyamag 4096  6月 11 22:51 ../
drwx------  3 hoyamag hoyamag 4096  5月 17 07:23 rails_tutorial_default_1526509377188/
drwx------  3 hoyamag hoyamag 4096  6月  7 09:23 rails_tutorial_default_1526511117537/
drwx------  3 hoyamag hoyamag 4096  6月 11 09:34 rails_tutorial_default_1528677272770/

行方不明のVMの名前がわからず、最終更新日付が見たかったのでllを使いました。ということで行方不明のVMの居所がわかりました。次はvagrantとこのVMとの紐付けを回復します。

ファイル'$(your_vagrant_directory)/.vagrant/machines/default/virtualbox/id'に記載されているIDのVMが、そのディレクトリで'vagrant up'したときに起動される
VMのIDはXMLファイル'~/VirtualBox\ VMs/\$(your_missing_VM_name)/$(your_missing_VM_name).vbox'のMachineタグの属性uuidに書いてある。

(UUIDってなんだ？って思ったんですけど、Universally Unique Identifierで世界中で重複しないIDらしいです) ということなので、idファイルに書いてあるUUIDを、起動したいVMのUUIDで置き換えました。

'vagrant up' 'vagrant ssh' したら、また新たなVMが生成されたようで、目的のVMにアクセスすることは出来ませんでした。多分目的のVMが起動していないので、'vagrant up'実行時に”存在しない”判定になり、新規のVMが生成されているような気がします。試しにVirtualBoxをGUIで立ち上げると、リストに目的のVMがリストされていません。

なぜかVMとVirtualBoxとの紐付けが切れているようなので、VMをVirtualBoxにインポートする

'VirtualBox missing VM'でぐぐります。 virtualbox.org • View topic - missing virtual machines, but the XML files exist.... を見ると、”'VBoxManage registervm'で直せたよ。詳細はここを見てね”みたいなことが書いてあるのでそこを見ます。 Chapter�8.�VBoxManage/. 「XMLファイルに書かれたVM定義をVirtualBoxにインポートできます」みたいなことが書いてます。 syntaxが書いてないので
'VBoxManage --version > ~/a.txt'
'vim ~/a.txt'
してregistervmオプションの使い方を見ます。ファイルネームを指定すれば良さそうです。

'VBoxManage registervm <fullpath.vbox>'
を実行したらエラーメッセージもなく終わりました(fullpathは長かったので除いています)。
'VirtualBox'
してVirtualBoxのGUIを見ると目的のVMがリストされているので大丈夫そうです。

いつも'vagrant up'してたディレクトリで'vagrant up'します。

$ vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Checking if box 'bento/centos-7.2' is up to date...
==> default: Clearing any previously set forwarded ports...
==> default: Fixed port collision for 22 => 2222. Now on port 2201.
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
    default: Adapter 2: hostonly
==> default: Forwarding ports...
    default: 22 (guest) => 2201 (host) (adapter 1)
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2201
    default: SSH username: vagrant
    default: SSH auth method: private key
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
    default: Warning: Authentication failure. Retrying...
^C==> default: Waiting for cleanup before exiting...
Vagrant exited after cleanup due to external interrupt.
$ VirtualBox

Authentication(認証？)が通りません。

ssh接続の回復

しばらく失敗手順

なぜauthでエラーになったのか考えます。vagrantとVMの紐付け情報は、さっきの経緯から.vagrantフォルダ以下に保存されてそうです。.vagrantフォルダ以下を一覧します。

$ tree .vagrant
.vagrant
└── machines
    └── default
        └── virtualbox
            ├── action_set_name
            ├── creator_uid
            ├── id
            ├── index_uuid
            ├── private_key
            ├── synced_folders
            └── vagrant_cwd

3 directories, 7 files

Authenticationのエラーなので、private_keyを適切に置き換えれば動きそうな気がしますが、どう直すかわからないので'vagrant Authentication failure'でぐぐります。

Vagrant ssh authentication failure - Stack Overflow VagrantFileに~/.ssh/id_rsaを使うように設定した。いわく、「

ファイルVagrantfileに「ssh private keyを格納したファイルを指定する記述を追加」し
対応するpublic keyをVMに追加する

とAuthenticationが通るようになるだろう」とのこと。指示に従います。

'vim Vagrantfile' して、もともと

...
Vagrant.configure("2") do |config|
...

だったのを

...
Vagrant.configure("2") do |config|
  config.ssh.private_key_path = "~/.ssh/id_rsa"
  config.ssh.forward_agent = true
...

にしました。そして、'ssh-copy-id -p 2222 root@127.0.0.1'しました。

$ ssh-copy-id -p 2222 root@127.0.0.1
The authenticity of host '[127.0.0.1]:2222 ([127.0.0.1]:2222)' can't be established.
ECDSA key fingerprint is SHA256:DSmPARVhLTW2ft2gWxXloCDEdYbY.
Are you sure you want to continue connecting (yes/no)? yes
/usr/bin/ssh-copy-id: INFO: attempting to log in with the new key(s), to filter out any that are already installed
/usr/bin/ssh-copy-id: INFO: 1 key(s) remain to be installed -- if you are prompted now it is to install the new keys
root@127.0.0.1's password: 
Connection to 127.0.0.1 closed by remote host.

パスワードがわかりません。。。
'Virtual Box default password'
'CentOS default password' でぐぐりますがいい感じのが出てきません。。。

'vagrant vm missing' でググり直して2番めのページを見ます Vagrant lost all of my VMs · Issue #5144 · hashicorp/vagrant · GitHub のJan 9, 2015投稿のStep9に「じゃあ起動しなおしたVMにid/password vagrant/vagrantでログインしてみようか」みたいなことが書いてあります(同時にこの投稿詳しすぎて最初からここ見ればよかった疑惑も立ちます)。

id/passwordがわかったのでさっきの手順を再開します

$ ssh-copy-id -p 2222 root@127.0.0.1
/usr/bin/ssh-copy-id: INFO: attempting to log in with the new key(s), to filter out any that are already installed
/usr/bin/ssh-copy-id: INFO: 1 key(s) remain to be installed -- if you are prompted now it is to install the new keys
root@127.0.0.1's password: 

Number of key(s) added: 1

Now try logging into the machine, with:   "ssh -p '2222' 'root@127.0.0.1'"
and check to make sure that only the key(s) you wanted were added.

idはvagrantであることを思い出したので、再実行します。

$ ssh-copy-id -p 2222 vagrant@127.0.0.1
/usr/bin/ssh-copy-id: INFO: attempting to log in with the new key(s), to filter out any that are already installed
/usr/bin/ssh-copy-id: INFO: 1 key(s) remain to be installed -- if you are prompted now it is to install the new keys
vagrant@127.0.0.1's password: 

Number of key(s) added: 1

Now try logging into the machine, with:   "ssh -p '2222' 'vagrant@127.0.0.1'"
and check to make sure that only the key(s) you wanted were added.

vagrant reload(再起動？)します

$ vagrant reload
==> default: Attempting graceful shutdown of VM...
    default: Guest communication could not be established! This is usually because
    default: SSH is not running, the authentication information was changed,
    default: or some other networking issue. Vagrant will force halt, if
    default: capable.
==> default: Forcing shutdown of VM...
==> default: Checking if box 'bento/centos-7.2' is up to date...
==> default: Clearing any previously set forwarded ports...
==> default: Fixed port collision for 22 => 2222. Now on port 2201.
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
    default: Adapter 2: hostonly
==> default: Forwarding ports...
    default: 22 (guest) => 2201 (host) (adapter 1)
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2201
    default: SSH username: vagrant
    default: SSH auth method: private key
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Authentication failure. Retrying...
^C==> default: Waiting for cleanup before exiting...
    default: Warning: Connection refused. Retrying...
Vagrant exited after cleanup due to external interrupt.

だめでした。 'vagrant change ssh key'でググってみたんですが、出てきたページが config.ssh - Vagrantfile - Vagrant by HashiCorpで、もはや読む元気がありませんでした。

実際に有効だったssh接続回復手段

vagrant issue #5144の2番目のコメントに従います。 Vagrant lost all of my VMs · Issue #5144 · hashicorp/vagrant · GitHub

$ cp ~/.vagrant.d/insecure_private_key ./.vagrant/machines/default/virtualbox/private_key 
$ vagrant ssh-config
Host default
  HostName 127.0.0.1
  User vagrant
  Port 2201
  UserKnownHostsFile /dev/null
  StrictHostKeyChecking no
  PasswordAuthentication no
  IdentityFile /home/hoyamag/Codes/rails_tutorial/.vagrant/machines/default/virtualbox/private_key
  IdentitiesOnly yes
  LogLevel FATAL
$ VirtualBox

vagrantで管理してたVMに id/padd=vagrant/vagrantでログインして

wget https://raw.githubusercontent.com/mitchellh/vagrant/master/keys/vagrant.pub
cat vagrant.pub >> .ssh/authorized_keys

元いたターミナルに戻って

$ vagrant halt
==> default: Attempting graceful shutdown of VM...
    default: 
    default: Vagrant insecure key detected. Vagrant will automatically replace
    default: this with a newly generated keypair for better security.
    default: 
    default: Inserting generated public key within guest...
    default: Removing insecure key from the guest if it's present...
    default: Key inserted! Disconnecting and reconnecting using new SSH key...
$ vagrant up
Bringing machine 'default' up with 'virtualbox' provider...
==> default: Checking if box 'bento/centos-7.2' is up to date...
==> default: Clearing any previously set forwarded ports...
==> default: Fixed port collision for 22 => 2222. Now on port 2201.
==> default: Clearing any previously set network interfaces...
==> default: Preparing network interfaces based on configuration...
    default: Adapter 1: nat
    default: Adapter 2: hostonly
==> default: Forwarding ports...
    default: 22 (guest) => 2201 (host) (adapter 1)
==> default: Booting VM...
==> default: Waiting for machine to boot. This may take a few minutes...
    default: SSH address: 127.0.0.1:2201
    default: SSH username: vagrant
    default: SSH auth method: private key
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
    default: Warning: Remote connection disconnect. Retrying...
    default: Warning: Connection reset. Retrying...
==> default: Machine booted and ready!
==> default: Checking for guest additions in VM...
==> default: Configuring and enabling network interfaces...
    default: SSH address: 127.0.0.1:2201
    default: SSH username: vagrant
    default: SSH auth method: private key
==> default: Mounting shared folders...
    default: /vagrant => /home/hoyamag/Codes/rails_tutorial
==> default: Machine already provisioned. Run `vagrant provision` or use the `--provision`
==> default: flag to force provisioning. Provisioners marked to run always will still run.
$ vagrant ssh
Last login: Tue Jun 12 14:51:48 2018
ls[vagrant@localhost ~]$ ls
environment  vagrant.pub

終わりました。 ssh接続の復旧に手間取りましたが、.vagrant/.../idファイルのIDを直して、行方不明だったVMを起動したあたりから、「'varant ssh'を実行してpassword=vagrantで認証してログインする」はできてたと思います(ssh認証に失敗しながらもできてたので)。

2018-06-14

neovimにlldbを導入するとき':UpdateRemotePlugins'で詰まった話

環境構築系何もわからないんですが、詰まったら詰まったなりにメモを残しておかないとまた詰まるのでメモを残します。

環境 Ubuntu 16.04 LTS

手順は大体これに則りました neovim + clang + lldbでC++開発環境構築メモ(自動補完、文法チェック、デバッガフロントエンド)。ただ、試行錯誤の過程で

neovimのプラグインマネージャはvim-plugに
critiqjo/lldb.nvimはdbgx/lldb.nvimを使うように

なりました。 vim-plugでインストールしたパッケージは~/.local/share/nvim/plugged以下に入るらしい

詰まった位置1

lldb.nvimの導入で

:UpdateRemotePlugin

を実行したところ。コピーを撮り忘れたが、

... 
Failed to load python3 host.
...

のようなエラーメッセージが出た。

解決策

':CheckHealth'をneovim上で実行すると、neovimのステータスが表示されるらしいので実行する。
"python 3 provider (optional)"のところがNGになっており、python3-neovimがインストーされていないことがわかる。
'pip3 install neovim'する。
再度neovim上で':CheckHealth'して、'python 3 provider'がOKになのを確認する
':UpdateRemotePlugins'をneovim上で実行する(今度は通るはず)

詰まった位置2

詰まった位置1を解消した後、':PlugInstall'を行った。その後

:UpdateRemotePlugin

を行うと

...
ImportError: No module named lldb
...

のようなエラーメッセージが出た。

解決策

エラーメッセージでぐぐるとlinux - how to import lldb in a python script - Stack Overflowに着いたので、Answerの指示の通り、壊れたシンボリックリンクを直す。

2018-06-04

AGC025参加記

問題: https://beta.atcoder.jp/contests/agc025
sub: https://beta.atcoder.jp/contests/agc025/submissions?f.User=skjmp

A

制約 N<=1e5 を見ると O(n) が通りそう
A+B=N を満たすAとBを全探索するとき、Aを決めるとBが決まる(B=N-A)なので全探索にはO(n)回かかりそう

なので全探索を考えます。

for(int i=1;i<=n/2+1;i++){
    int A=i;
    int B=N-A
    //TODO 「整数の各位の桁の和」の最小値を更新する
}

「整数の各位の桁の和」を求める処理をketawa関数に書くとすると

int mi=INT32_MAX;
for(int i=1;i<=n/2+1;i++){
    int A=i;
    int B=N-A
    mi=min(mi, ketawa(A)+ketawa(B));
}

ketawa関数は整数を10で割った時のあまりがその整数の1の位の値になることを考えると

int ketawa(int n) {
    int cnt = 0;
    while (n > 0) {
        cnt += n % 10;
        n /= 10;

    }
    return cnt;
}

それで投げたら通りました。この時ketawa処理にO(logn)かかるため全体の計算量がO(nlogn)になっていたことには気づいていません。

B

mod演算が苦手なのでCを読みます

C

A(高橋)くんとB(青木)くんが最適に動いたときスコアがどうなるか的な問題が来ました。何もわからないのでサンプルをノートに書いてシミュレーションします。方眼ノートが便利でした。高橋くんの気持ちになってサンプルをシミュレーションすると、
* 自分が渡された区間内にいたら動かない
* 渡された区間が右にあったら区間の左端に移動する
* 渡された区間が左にあったら区間の右端に移動する

が最適ムーブな気がしてました。ほんとに最適かな？って思ったんですが、
* 同じ方向に連続して動く場合、今端を超えて動いても後で動いてもスコアは変わらないこと
* 違う方向に動く場合は、端を超えて動くとスコアが悪くなること
* 今動く必要がない場合、動く必要がある区間が渡されてから動いてもスコアが変わらなそうなこと

から高橋くんのムーブはそういうことにしました。

次に青木くんのムーブを考えると、

0
   --           //1番目に渡す区間(区間1)
      ---       //区間2
           --   //区間3

のような区間の渡し方は、1番目に渡す区間が2番目に渡す区間の中継地点になっているので、嬉しくない気がしてきます。

0
      ---       //1番目に渡す区間(区間1)
   --           //区間2
           --   //区間3

のような区間の渡し方は、高橋くんが渡された区間の近い方の端にタッチすることを考えると、高橋くんがジグザグに動いてくれてスコアが稼げそうです。

高橋くんがジグザグに区間を往復する場合、
* 区間の右端に触る->区間の左端に触る->区間の右端に触る...
* 区間の左端に触る->区間の右端に触る->区間の左端に触る...
の2通りがありえます。

今、高橋くんが右端左端右端...の順で区間に触ることを考えると、高橋くんが一番長い距離をジグザグに走る場合、高橋くんへの区間の与え方は
1. 区間の右端が、残っている区間の中で一番右にある区間を渡す
2. 区間の左端が、残っている区間の中で一番左にある区間を渡す
3. 区間の右端が、残っている区間の中で一番右にある区間を渡す
4. ...

になりそうです(お気持ち)。

そういうことで与えられた区間を左端でソートしたものと右端でソートしたものをそれぞれ持って、右左右...のパターンの場合のスコアと左右左...のパターンの場合のスコアをシミュレーションします。そして大きかった方を答えにします(軽く書いていますが実装に40分以上かかっています)。

シミュレーションの処理に、区間内に高橋くんがいた場合の処理を書き忘れていると、サンプルが通りません(ありがとうAtCoder!)。

シミュレーション前処理のソートがO(nlogn)
シミュレーションがO(n)
N<=1e5

なので計算量的にも問題なさそうです。

投げます。通りました。やった！俺はやったぞ！

D

なにもわかりません。