OverleafでVimやEmacsのキーバインドを使う

TL;DR;

プロジェクトの詳細画面に行き、左上に表示されるメニューをクリックするとサイドバーが表示されます。 サイドバーから Keybindings の項目を None → Vim or Emacs に変更します。

詳細

Overleaf上でVimキーバインドを使用したいと思ったのですが、公式のドキュメントを見ても、設定画面が見つからなかったので調査しました。

これは2023年1月3日段階での情報です。今後、追加の仕様の変更などあるかもしれません。

さて、ここからが具体的な手順になります。

まず、キーバインドを使用したいプロジェクトのページにいきます。

次に画面左上に表示されている下記画像のような Menu アイコンをクリックします。

Overleaf Menuボタン
Overleaf Menuボタン

するとサイドバーが表示されるので、画像の通り、Keybindingsを設定します。

Overleaf Menu サイドバー
Overleaf Menu サイドバー

これにて設定は完了です。

三井住友信託銀行プログラミングコンテスト D - LuckyPin

問題概要

\(N\)桁のラッキーナンバーから\(N-3\)桁を消して残りの\(3\)桁を暗証番号として設定する。

このとき、暗証番号は何種類考えられるか?ただし、ラッキーナンバーや暗証番号はいずれも\(0\)から始まって良いものとする。

制約

  • \(4\ \leq \ N\ \leq \ 30000\)
  • Sは半角数字からなる長さNの文字列

この問題のポイント

暗証番号になる数字は、高々 1000通りだけしかないことに気がつけるかどうか。

解説

作成される暗証番号は、000 ~ 999 までの1000通りしか存在しません。この範囲のある数字を\(n\)とすると、

  • 100の位・・・Sの左から探索する
  • 10の位・・・100の位で見つかった位置から探索する
  • 1の位・・・10の位で見つかった位置から探索する。

そして、各桁に対して見つからない場合は、次の数字にいくようにします。今回は、各桁の数字が見つかった場合を数え上げることで正解となります。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

int main() {
  int N; cin >> N;
  string S; cin >> S;
  int ans = 0;
  for(int i = 0; i < 1000; i++) {
    string s; s = "00" + to_string(i);
    s = s.substr(s.size() - 3);
    bool found = true;
    for(int j = 0; j < 3; j++) {
      int pos;
      if(j == 0) pos = S.find(s[j]);
      else pos = S.find(s[j], pos+1);
      if(pos == string::npos) {
        found = false;
        continue;
      }
    }
    if(found) ans++;
  }
  cout << ans << endl;
  return 0;
}

ABC145D - Knight

問題概要

2次元平面上の原点(0, 0)にチェスのナイトの駒が置かれている。

ナイトがマス\((i, j)\)にある時、\((i+1, j+2)\) か \((i+2, j+1)\)のどちらかにのみ動かすことができる。

目的地\((X, Y)\)まで移動させる総数を\(10^{9}+7\)で割ったあまりを求めよ。

問題のリンクはこちら

制約

  • \(\ 1\ \leq \ X\ \leq \ 10^{6}\)
  • \(\ 1\ \leq \ Y\ \leq \ 10^{6}\)

考察

DPによる考察

まず初めにDPで解けないかを考えた。具体的には、

$$ dp[i][j]: (i, j)までの移動させる方法の総和 $$

というDPを定義した時、遷移は、

\begin{eqnarray} dp[i][j]=\left\{ \begin{array}{ll} dp[i-1][j-2] & (y=2x) \\ dp[i-2][j-1] & (y=\frac{1}{2}) \\ dp[i-1][j-2]+dp[i-2][j-1] & (上記以外) \\ \end{array} \right. \end{eqnarray}

となる。しかしながら、今回の制約では \(O(N^{2})\)のプログラムは不適切である。

この問題のポイントとなる気付き

この問題を特に当たって、次のポイントに気がつくと考察を進めやすい。

  1. パスカルの三角形を形成すること(次の章を参照)
  2. 点は全て \(y = -x + 3*k, k:0以上の整数\)にのること
  3. X+Yの和は常に3の倍数になり、連続する3の倍数を形成している。
  4. パスカルの三角形は、\(y=\frac{1}{2}x\), \(y=2x\), \(y=-x+3k, k:0以上の整数\)で囲まれること。

パスカルの三角形と逆元による考察

個数のカウント方法

具体的に点をプロットしてナイトの動きを観察する。移動することのできる総和をプロットした点に書き加えていく。(例えば、 \((1, 2)\)は、\((0, 0)\)からのみ移動できるので\(1\)である。この操作を\(3\)段程度行うと、 パスカルの三角形 を形成していることに気がついた。

つまり、\((X, Y)\)が\(n\)段目の左から\(r\)番目にある時、 \(_{n-1} C_{r-1} \) で計算できる

ことが言えるようになる。

(X, Y)がパスカルの三角形のどこに位置するか

あとは、点\((X, Y)\)が\(n\)段目の左から\(r\)番目に該当するかを考える。

点 \((0, 0)\) を1段目とすると、

  • \((1, 2), (2, 1)\) → \(1+2/3+1 = 2\) 段目 *\((2, 4), (3, 3), (4, 2)\) → \(6/3+1 = 3\)段目

のように (X+Y)/3+1が段数に相当する。

\(n\)段目だと判明したら、次は、その\(n\)段目の中で一番\(y\)座標が大きい点を探す。これは、\(y = 2(n-1)\)により求まるので、あとは、今求めた\(y\)を用いて、\(r = y-Y+1\)で求められる。

これらを求めることができたので、あとは、逆元を用いて、コンビネーションの計算をすることで答えとなる。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int NMAX=1000010;

ll fac[NMAX], finv[NMAX], inv[NMAX];

void init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i = 2; i < NMAX; i++) {
    fac[i] = fac[i-1] * i % mod;
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}

ll C(int n,int k) {
  if(n < k) return 0;
  if(n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

int main() {
  init();
  int X, Y; cin >> X >> Y;
  if((X+Y) % 3 != 0) {
    cout << 0 << endl;
    return 0;
  }
  int n = (X+Y) / 3+1;
  int k = 2*(n-1) - Y + 1; // y = 2xより最も上にくる点からどれだけ離れているか。
  cout << C(n-1, k-1) << endl;
  return 0;
}

ABC144D Water Bottle 解説

問題概要

底面が\(1\)辺\(a\ cm\)の正方形で、高さが\(b\ cm\)であるような直方体の容器に体積\(x\ cm^{3}\)の水を入れたのち傾けていく時、水が溢れる限界の角度を求める。

制約

  • \(1\ \leq a,\ b \leq 100 \)
  • \(1 \leq x \leq a^{2}b\)

問題へのリンクはこちら

考察

この問題のポイントとなるのは、水量が変化しないと言うことです。

1. 直方体 → 長方形へと変換

立体を傾けていく水の動きをシミュレーションするのは難しいので、底面が正方形であることから、水の体積を\(a\)で割ることで\(a\ \times \ b\)の長方形とする。

2. 入っている水の量によって場合分け

2-1. 入っている水のかさが半分以上の時

傾けていくと次のような状態で限界点を迎えます。

f:id:accha-n:20191029092549j:plain
水量が多い時

限界点では、図の通り、台形になっていることから台形の面積の公式により、水量を求め、図中の\(y\)を逆算します。


\begin{align}
\frac{(y+b)*a}{2} &= \frac{x}{a} \\\
y &= \frac{2x}{a^{2}} - b
\end{align}

求める\(\theta\)は、 $$\theta = \tan^{-1} (\frac{b-y}{a})$$ となります。

2-2. 入っている水のかさが半分以下の時

f:id:accha-n:20191029092935j:plain
水量が少ない時

限界点では、先ほどとは異なり、三角形の形状になります。先ほどと同様に、水量が変化しないことから図中の\(y\)を逆算すると、


\begin{align}
\frac{b*y}{2} &= \frac{x}{a} \\\
y &= \frac{2x}{ab}
\end{align}

図より、求める\(\theta\)は、 $$\theta = \tan^{-1}(\frac{b}{y})$$ となります。

実際の実装は以下の通りです。(はじめに\(x\)を\(a\)で割ってしまっている点にご注意ください。)

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
  double a, b, x; cin >> a >> b >> x; x/=a;
  double y, rad, deg;
  if(x >= a*b/2.0) {
    // 水のかさが半分より大きい時
    y = 2.*x/a-b;
    rad = atan((b-y)/a);
  } else {
    // 水のかさが半分未満の時
    y = (2.*x) / b;
    rad = atan(b/y);
  }
  deg = rad * 180. / M_PI;
  cout << setprecision(12);
  cout << deg << endl;
  return 0;
}

CODEFORCES 1139 A. Even Substrings

問題概要

\(N\)桁の数字だけで構成された文字列\(s\)が与えられる。

\(s\)の部分文字列\(s[l...r]\)が偶数になるような\([l, r]\)の組み合わせの総数を求めよ。

制約

  • \(1\ \leq \ N\ \leq 65000\)
  • time limit per test 0.5sec

問題へのリンクはこちら

考察

\(N\)の最大値が\(65000\)なので、\(l,\ r\)を全探索して部分文字列を一つずつ検証する方法をとることはできない。

そのため、次のような1次元DPを考えた。

DPの定義

$$ dp[i]: i桁目までの偶数の個数の総和 $$

このように定義すると、\(0\)桁目には文字が存在しないので、\(dp[0] = 0\)となる。

DPの遷移

上で定義したDPの遷移を考える。この際、偶奇に場合わけして考える。

1. 奇数の場合

\(i+1\)桁目が奇数の場合は、\(i\)桁目までの総数のままである。

2. 偶数の場合

例として、1234と言う文字列が与えられた場合を考えてみる。この場合、2桁目に初めて偶数が現れる。2が現れた時、\([1, 2]\), \([2, 2]\)の2組が偶数になる。同様に、4桁目も考えると、\([1, 4]\), \([2, 4]\), \([3, 4]\), \([4, 4]\)の4組が偶数になる。

つまり、i桁目が偶数ならば、i組の偶数ができると言い変えることができる。

3. まとめ

上記の1. 2. を踏まえると、次のように遷移することが言える

$$ i桁目が奇数の時: dp[i+1] = dp[i]\ \ \ \ \ \ \\ i桁目が偶数の時: dp[i+1] = dp[i] + i $$

実装

実装は以下の通りになる。0-indexedに注意して実装することを忘れないようにしたい。

#include <iostream>
#include <string>
using namespace std;
const int MAXN = 65010;
int dp[MAXN];

int main() {
  int N; cin >> N;
  string s; cin >> s;
  for(int i = 0; i < N; ++i) {
    dp[i+1] = dp[i] + (int(s[i]) % 2 == 0 ? i+1 : 0);
  }
  cout << dp[N] << endl;
  return 0;
}

Technocup B (CODEFORCES)

問題概要

  • \(N\) 要素の配列 \( a_1, a_2, ... a_N \) を \(K\) 個に分割する。
  • \(K\) 個に分割されたそれぞれの要素の最小値のうち、最大になるものを求めよ。

制約

  • \( 1 \leq K \leq N \leq 10^{5}\)
  • \( -10^{9} \leq a_i \leq 10^{9} \)

問題はこちら

考えたこと

Kの値が 1, 2, 3以上 で取り扱いが異なる。

K == 1 の時

この時、配列 \(a\) の最小値が答えになる。

K == 2 の時

この時、次の場合のどちらかしかありえない

  • \([1, 1], [2, N]\) に分割される時
  • \([1, N-1], [N, N]\) に分割される時

そのため、配列の最初と最後の要素のうち、大きい方が答えとなる。

K >= 3 の時

この時、 配列の最大値の要素, その前の要素群, その後の要素群 に必ず分割することができるため、配列の最大値 が答えとなる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int inf = 1<<30;

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int N, K; cin >> N >> K;
  vector<int> a(N);
  int minn=inf, maxn = -inf;
  for(int i = 0; i < N; ++i) {
    cin >> a[i];
    minn = min(minn, a[i]);
    maxn = max(maxn, a[i]);
  }
  if(K==1) cout << minn << endl;
  else if(K == 2) cout << max(a[0], a[N-1]) << endl;
  else cout << maxn << endl;

  return 0;
}

CODEFORCES 318 A. Even Odds

問題概要

  • \(1\)以上\(N\)以下を満たす数字の中で、\(K\)番目に該当する数を求めよ。
  • ただし、\(N\)個の数字は以下の規則によって並べ替えられるものとする
    • \(1\)以上\(N\)以下を満たす奇数をはじめに並べる
    • その後ろに残った偶数を並べる
    • 数は昇順で並ぶものとする

問題のリンク

制約

\(1 \leq K \leq N \leq\) 1012

考察

\(N\)が奇数の時、並び替えた後の数列の前半の項は奇数のみで構成されることを考慮すると、\(N = N + 1\)としても\(N\)以下の数字の並び順には影響しない。

以下、\(N\)を偶数として考える。

\(N\)が偶数ならば、

  • \( K \leq N/2 \) の時、 \(2K-1\) が答え
  • それ以外の時、 \(2(K-N/2)\) が答え
#include <iostream>
using namespace std;
typedef long long ll;

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  ll N, K, ans; cin >> N >> K;
  if(N % 2 == 1) N += 1;
  if(K <= N/2) ans = 2*(K-1) + 1;
  else ans =  2 * (K-N/2);
  std::cout << ans << std::endl;
  return 0;
}