トコロテンの日記

自分の活動内容や普段考えていることをアウトプットするためのブログです。ITに関わる話がメインであり、開発、競技プログラミング、気に入った技術などの話が多くなります。

英語の壁

勉強 英語

こんにちは。トコロテンです。
今回は、精進の話や得た知見の話ではなく、自分の悩みのようなものを書きたいと思います。
私は幼い頃(小学4年生くらい)からずっと情報の分野の魅力に惹かれて、大学生になる今まで情報に付き合ってきました。
情報という分野の歴史はまだまだ浅いですが、驚くほど奥が深く、それなのに身近で、大変面白い分野だと思います。
ただ、情報の世界にいると次々に新しい技術が生まれて変化について行くのが大変です。常に学び続けなければなりません。
最新の情報はインターネットで即座に広まり、基本的には誰でも見ることができるのですが、ここで問題があります。
情報の一次ソースが、多くの場合、英語であるということです。
私は、高校生の頃にしっかり英語を学ばなかったこともあって英語を満足に読み書きすることができません。
自分があまり知らない分野の英語が読めないのはもちろんのこと、自分が最も得意とする情報の分野で使われている英語でさえ読めないのは致命的な問題です。
大学に入って1年生の春に初めて受けたTOEICの点数も405点と壊滅的なものでした(これによって科目選択における人権を失いました)
これまでは日本語の情報だけで十分に事足りていましたが、自分のやりたいことが増え、さらに専門性が高くなるにつれて、日本語で得られる情報だけでは圧倒的に不足していると感じるようになりました。
Qiitaのなんちゃって技術記事を読んでる暇があったら公式ドキュメントに目を通した方が100倍有意義であるのは周知のことだと思いますが、公式ドキュメントもやはり多くの場合が英語で書かれており、今の私はGoogle翻訳に頼ってなんとなくで読むことしかできません。
インターネット上には私が必要とする情報が確かに存在していて、私でも自由に閲覧することができます。
しかし、いざそれを見てみても、自分の目の前にある情報が何を意味してるのかわかりません。悔しくて仕方がありません。
このままでは、これがキャップとなって頭打ちになるということがよくわかります。
もちろん、中学、高校、大学としっかり英語の授業は受けてきましたが、それだけでは全然足りないことはわかっていました。
また、英語がとても重要であるということも幼い頃から情報の世界に入り浸っている私は百も承知でした。
しかし、いつかしっかり勉強するだろうと思いながらもう大学2年生に上がってしまいました。
実際に使えなければ意味がないのに「英語がしっかり使えるようになった」という結果ではなく、「授業でしっかり勉強した」という過程だけに満足してしまい、やっただけ、実際には全然わからないということに目を瞑っていました。
こんな状態でも、恥ずかしながら「一流のエンジニアになりたい」という思いを幼い頃から常に持ちながら生活してきました。
Twitterを見ていると同世代のすごいエンジニアの方々がどんどん成長して、自分との差が開いて行くことに焦りを感じます。
もちろん、技術力で人と競うことが目的ではないのでこの焦りは、特定の人物に「◯◯に勝ちたい！負けたくない」という競争欲からくる焦りではありません。
他の方が自分に必要なものをしっかりと見定め、獲得して自分を高めている中、私は自分に本当に必要な物に目を瞑っていたということからくる焦りです。
精進することだけが全てではないことは分かっているし、技術力だけが私を測る指標でないこともわかります。
しかし、私が好きで好きでずっとやってきた情報という分野は、私が自分を測る際に一番大事な要素です。
一回、真剣に英語に取り組んで、まだ私の知らない情報の世界に足を踏み入れてみたいと思います。

AtCoder Beginner Contest 115 D - Christmas

競技プログラミング AtCoder ABC

問題

atcoder.jp

考察と解法

メリークリスマス！………ではないですね。 なぜクリスマスにハンバーガーなのかはわかりませんがとりあえず問題と真剣に向き合うことにします。

まずはじめに、ハンバーガーの生成規則について確認しておきます。
ハンバーガーは'P'と'B'からなる文字列で表現されます。 また、ハンバーガーにはレベルがあり、レベルLハンバーガーを表す文字列h(L)は以下のように再帰的に定義されています。 +演算子は文字列の結合を表しています。

{} $$ h(L) = \left\{ \begin{array}{} "P" & (L =0) \\ "B" + h(L - 1) + "P" + h(L - 1) + "B" & (L \ge 1) \end{array} \right. $$

問題は、この定義から生成されるレベルN(1 \le N \le 50)バーガーの文字列の先頭からX文字目(1-indexed)までに含まれる'P'の個数を数えるといったものです。 まずは、全探索する場合を考えます。 これは、レベルNバーガーの文字列を実際に生成して、その文字列の先頭から順にX文字目まで各文字を調べて'P'の個数をカウントすればいいです。 そこで気になるのは、レベルNバーガーの文字列の長さです。なぜなら、全探索を行う場合、文字列を生成後に各文字を調べていくだけでも計算量が文字列の長さに比例するからです。 文字数が多すぎる場合、全探索は行えないことになります。したがって、全探索を行う前にレベルNバーガーの文字列の最大長について考えます。

レベルLバーガーの文字列長を表す関数|h(L)|はh(L)の定義より以下のようになります。

{} $$ |h(L)| = \left\{ \begin{array}{} 1 & (L =0) \\ |h(L - 1)| \times 2 + 3 & (L \ge 1) \end{array} \right. $$

このままではN=50(最大値)であるときの|h(50)|がわからないので漸化式から一般式を求めます。

$$ \begin{align} |h(L)| &= 2|h(L - 1)|+3 \\ &= 2(2|h(L - 2)|+3)+3 \\ &= 2^2|h(L - 2)| + 2^1 \cdot 3 + 2^0 \cdot 3 \\ &= 2^3|h(L - 3)| + 2^2 \cdot 3 + 2^1 \cdot 3 + 2^0 \cdot 3 \\ &= \vdots \\ &= 2^L|h(L - L)| + 3(2^0 + 2^1 + ... + 2^{L - 1}) \\ &= 2^L + 3(2^L - 1) \\ &= 2^L + 3 \cdot 2^L - 3 \\ &= 2^{L+2} - 3 \end{align} $$

|h(L)| = 2^{L+2} - 3が得られたので|h(50)|を求めてみると4503599627370493 \ge 10^{15}となることがわかり、全探索では一生計算が終わりません。 レベルNバーガーを生成してはいけません。あまりにも分厚すぎて手に負えません。悪あがきはやめて大人しく問題と真剣に向き合うことにします。

よく考えてみると、この問題で重要なのは'P'の個数だけであるため、レベルNバーガーの具体的な文字列は知る必要がありません。 レベルNバーガーの中には'P'と'B'、さらにレベルN-1バーガーが含まれていることに着目します(それはそう)。
ここでレベルNバーガーの先頭からX番目までの文字の中の'P'の個数を表す関数をf(N, X)とすると次のようになることがわかります。

{} $$ f(N, X) = \left\{ \begin{array}{} 1 & (N =0, X = 1) \cdots (1) \\ 0 & (N > 0, X = 1) \cdots (2) \\ f(N - 1, X - 1) & (N > 0, 1 < X < 2 + |h(N - 1)|) \cdots (3) \\ f(N - 1, |h(N - 1)|) + 1 & (N > 0, X = 2 + |h(N - 1)|) \cdots (4) \\ f(N - 1, |h(N - 1)|) + f(N - 1, X - 2 - |h(N - 1)|) + 1 & (N > 0, 2 + |h(N - 1)| < X < 3 + 2|h(N - 1)|) \cdots(5) \\ 2f(N - 1, |h(N - 1)|) + 1 & (N > 0, X = 3 + 2|h(N - 1)|) \cdots (6) \end{array} \right. $$

(1)の場合は自明であるため、それ以外について説明します。

  • (2)は、レベル1以上のバーガーの左端は必ず'B'になるため0個となります。
  • (3)は、XがレベルNバーガーに含まれる左側のレベルN-1バーガーの範囲内にあるときです。この時は、レベルN-1バーガーの中にしか'P'が存在しないため、レベルN - 1バーガーのX - 1番目までに含まれる'P'の個数を数えます。
  • (4)は、X番目の文字がレベルNバーガーを構成している中央の'P'(レベルN-1の'P'ではありません)を指している時であるため、左側のレベルN-1バーガーに含まれる'P'の個数+1個になります。
  • (5)は、XがレベルNバーガーに含まれる右側のレベルN-1バーガーの範囲内にあるときです。この時は、左側と右側のレベルN-1バーガーの中にある'P'と(4)の場合の中央の'P'が存在するため、左側のレベルN-1バーガーに含まれる全ての'P' + 右側のレベルN-1バーガーのX - 2 - |h(N - 1)|番目までに含まれる'P'+1個になります。
  • (6)は、XがレベルNバーガーの最後尾を指している場合です。この場合は左右のレベルN-1バーガーが対称であることを利用してレベルN-1バーガーの中に含まれる'P'の2倍の個数に(4)の場合の中央の'P'の+1個になります。

上のような再帰関数を定義して呼び出すことでレベルNバーガーを生成することなくこの問題を解くことができます。

計算量

上記の再帰関数では、N=0となった時に再帰を終了します。 また、(1)以外の場合は必ずNが1ずつ減少していくため、少なくともN回の再帰呼び出しでf(N, X)は終了します。 したがって、時間計算量はO(N)です。

実装上の注意点

最も分厚いレベル50バーガーは32bit整数の範囲には収まらないため、64bit整数の幅を持たせなければなりません。#define int long longの会に入会することでオーバーフローを気にすることなく安心してこの問題を解くことができます。

ソースコード

#include <iostream>
 
// #define int long longの会に入会
#define int long long
 
using namespace std;
 
int calcBurgerSize(int level)
{
    return level ? 2 * calcBurgerSize(level - 1) + 3 : 1;
}
 
int countPatties(int level, int x)
{
    if(level == 0)
    {
        return 1;
    }
 
    int smallSize = calcBurgerSize(level - 1);
 
    if(x == 1)
    {
        return 0;
    }
    else if(x < 2 + smallSize)
    {
        return countPatties(level - 1, x - 1);
    }
    else if(x == 2 + smallSize)
    {
        return countPatties(level - 1, smallSize) + 1;
    }
    else if(x < 3 + smallSize * 2)
    {
        return countPatties(level - 1, smallSize) + countPatties(level - 1, x - smallSize - 2) + 1;
    }
    else
    {
        return countPatties(level - 1, smallSize) * 2 + 1;
    }
}
 
signed main()
{
    int n, x;
 
    cin >> n >> x;
 
    cout << countPatties(n, x) << endl;
}

感想

クリスマスではないにも関わらずChristmasを解いてしまったことに罪悪感を感じてます。場合分けおじさんを体に宿すことでこの問題をACすることができます。

AtCoder Beginner Contest 102 C - Linear Approximation

競技プログラミング AtCoder ABC

問題

atcoder.jp

考察と解法

今回は結構考察パートが長めです。

問題としては以下の関数f(A, b)の値を最小化するbを求め、それを代入したf(A, b)の値を求めるといったものです。 A = (A_1, A_2, ..., A_N)は入力として与えられるのでbの値だけを考えれば良いです。

f(A, b) = abs(A_1 - (b + 1)) + abs(A_2 - (b + 2)) + ... + abs(A_N - (b + N))

まず、(-1, -2, ..., -N)が定数になるため、これを事実上の定数である(A_1, A_2, ..., A_N)と合わせて、式変形を行います。

f(A, b) = abs(A_1 - (b + 1)) + abs(A_2 - (b + 2)) + ... + abs(A_N - (b + N)) f(A, b) = abs(A_1 - 1 - b) + abs(A_2 - 2 - b) + ... + abs(A_N - N - b)

ここでA' = (A_1', A_2', ..., A_N') = (A_1 - 1, A_2 - 2, ..., A_N - N)とすると

f(A, b) = abs(A_1' - b) + abs(A_2' - b) + ... + abs(A_N' - b) = \sum_{i=1}^N abs(A_i' - b)

となります。これは、全てのA_i'とbとの距離の総和を意味しています。bは自明に(min(A_i') \le b \le max(A_i'))になりますが、A_i'の取る値が1から10^9であるため、いつも通り全探索では時間内に計算が終わりません。おとなしく問題と向き合いましょう。
また、ここで考えるのを簡単にするために、A'の各要素を昇順(小さい順)に並べ替えたものをBとします。 これはもちろん

f(A, b) = \sum_{i=1}^N abs(B_i - b)

が成り立つため、全てのB_iとbの距離の総和について考えることにします。

ここで、あるb_iをjだけ増加させた場合、f(B, b_i + j)は以下のようになります。

B_i \le b_i \le B_{i+1}(1 \le i \le N - 1)

({B_i - b_i} \le j \le {B_{i+1} - b_i})

f(B, b_i + j) = f(B, b_i) + ij - (N - i)j
f(B, b_i + j) = f(B, b_i) + (i - (N - i))j

したがって、bをjだけ増加させた場合の関数の増加量は

f(B, b_i + j) - f(B, b_i) = (i - (N - i))j (増加式)

となります。f(B, b_i)を最小化するためには、上式を最小化すればよいです。
右辺に着目すると

(i - (N - i))j = (2i - N)j

上の式が最小となるのは以下の2パターンです。

  1. (2i - N) \ge 0かつ(j = B_i - b_i)
  2. (2i - N) \le 0かつ(j = B_{i+1} - b_i)

言い換えると、jの値を

  1. (i \ge N - i)のとき(j = B_i - b_i)
  2. (i \le N - i)のとき(j = B_{i+1} - b_i)

とすることで関数の増加量を最小化できます。また、最小化した場合、(増加式)が0以下の値を取るため、f(B, b_i) \ge f(B, b_i + j)が成り立ち、f(B, b_i)の最小値はf(B, b_i + j)となります。
そして、f(B, b_i + j)の最小値、つまりf(B, b_i)の最小値は

  1. (i \ge N - i)のときf(B, b + j) = f(B, B_i)
  2. (i \le N - i)のときf(B, b + j) = f(B, B_{i+1})

となります。
また、f(B, b)の最小値は自明に全てのi(1 \le i \le N - 1)に対するf(B, b_i)の最小値であることから、

min(f(B, b)) = min(f(B, b_1), f(B, b_2), ..., f(B, b_{N - 1}))

であり、b_iはiによってB_i, B_{i+1}の適切な方を選べばよいことがわかったため、

min(f(B, b)) = min(f(B, B_1), f(B, B_2), ..., f(B, B_N))

となります。あとは、各iについてf(B, B_i)を求める方法がわかればこの問題を解く事ができます。

ここで、f(B, B_i)の式を確認すると

f(B, B_i) = abs(B_1 - B_i) + abs(B_2 - B_i) + ... + abs(B_i - B_i) + ... + abs(B_N - B_i)

abs(B_i - B_i) = 0より

f(B, B_i) = \sum_{j=1}^{i-1} abs(B_j - B_i) + \sum_{j=i+1}^N abs(B_j - B_i)

Bが昇順に並んでいるという制約から

  1. (j \le i)ならabs(B_j - B_i) = B_i - B_j
  2. (j > i)ならabs(B_j - B_i) = -B_i + B_j

よって、

f(B, B_i) = \sum_{j=1}^{i-1} (B_i - B_j) + \sum_{j=i+1}^N (-B_i + B_j)

f(B, B_i) = B_i(i - 1) - \sum_{j=1}^{i-1} B_j + \sum_{j=i+1}^N B_j - B_i(N - i)

f(B, B_i) = B_i(2i - N - 1) - \sum_{j=1}^{i-1} B_j + \sum_{j=i+1}^N B_j (一般式)

となります。\sum_{j=1}^{i-1} B_jと\sum_{j=i+1}^N B_jは予め累積和を用いて計算しておく事で各iに対してO(1)で求める事ができます。

以上の(一般式)を全てのiに対して計算した結果の最小値がこの問題の解となります。

計算量

  1. 各要素をソートするのにO(NlogN)
  2. 累積和を計算するのにO(N)
  3. 全てのiに対して(一般式)を計算するのにO(N)

1, 2, 3の操作は互いに独立しているため、全体での時間計算量はO(NlogN)になります。

実装の注意点

この問題では、(一般式)が取りうる最大値を取った時に大体2 \times 10^{14}となるため、32ビットで表現できる数値の範囲を超えてしまいます。 したがって、殆どの環境で32ビットとなるint型ではオーバーフローが発生します。C++ではlong long型が64ビットの幅を持っているため、これを利用しましょう。

ソースコード

#include <iostream>
#include <algorithm>
 
#define int long long
 
using namespace std;
 
signed main()
{
    int n;
    int a[200000];
    int sum[200001] = { 0 };
 
    cin >> n;
 
    for(int i = 0; i < n; ++i)
    {
        cin >> a[i];
        // 予めAをA'に変換しておく
        a[i] -= i + 1;
    }
 
    // A'からBへの変換
    sort(a, a + n);
 
    // 累積和を計算[)
    for(int i = 1; i <= n; ++i)
    {
        sum[i] = sum[i - 1] + a[i - 1];
    }

    // f(B, b)の最小値
    int d = 1LL << 60LL;

    for(int i = 0; i < n; ++i)
    {
        int b = a[i];
        int leftD = (i * b) - (sum[i]);
        int rightD = (sum[n] - sum[i + 1]) - (n - 1 - i) * b;
        d = min(d, leftD + rightD);
    }
 
    cout << d << endl;
}

感想

300点の問題にしては少し難しいと感じました。bの値の候補をいかに絞り込む事ができるかがこの問題の鍵でした。

AtCoder エクサウィザーズ 2019 C - Snuke the Wizard

競技プログラミング AtCoder ABC

問題

atcoder.jp

考察と解法

まず、全探索を行う場合を考えます。 1回の呪文ごとにゴーレムの移動をシミュレートするのに最大N体のゴーレムを移動させる必要があり、全部で呪文をQ回唱えるため、最悪時間計算量はO(QN)となります。 もちろんQN=4 \times 10^{10}なので一生計算が終わりません。 マスをノード、ゴーレムの移動をエッジに見立てたグラフを考えたりもしましたが、あまり良い方法は思いつかなかったので悪あがきはやめて大人しく問題と向き合うことにします。

呪文について考えると、以下の性質がわかります。

  1. 呪文ごとに動く方向は異なるが、1回の呪文でゴーレムは1マス分しか移動しない。
  2. ある状態で同じマスに滞在しているゴーレムは必ずそれ以降は同じ動きになる。

上の2つの性質から、呪文をどのように唱えてもゴーレムが他のゴーレムを飛び越えられないことがないことがわかります。 つまり、ゴーレムの並び順は呪文をいくら唱えても初期状態から変化しません。 また、考えるのを簡単にするために、マスを(1, 2, ..., N)を(0, 1, 2, ..., N, N + 1)に拡張します。 こうすることで、ゴーレムの消滅はiマス目のゴーレムの0かN+1番目のマスへの移動で表現できます。
以上のことから、Q回の呪文を唱える間に

  1. iマス目のゴーレムが0番目のマスに移動するならjマス目(0 < j < i)のゴーレムも0番目のマスに移動
  2. iマス目のゴーレムがN+1番目のマスに移動するならjマス目(i < j < N + 1)のゴーレムもN+1番目のマスに移動

することがわかります。 これをさらに抽象化して、以下の2つの関数を定義します。

  1. f(x) : 初期位置xマス目のゴーレムが呪文をQ回唱える間に0番目のマスに移動するなら1そうでないなら0
  2. g(x) : 初期位置xマス目のゴーレムが呪文をQ回唱える間にN+1番目のマスに移動するなら1そうでないなら0

するとf(x)は単調減少、g(x)は単調増加であることがわかります。 したがって、これらの関数はxの値で二分探索を行えます。 そこで、二分探索を用いてf(x)=1を満たす最大のxとg(x)=1を満たす最小のxを求め、それぞれをa, bとします。 これは初期位置が (1, 2, ..., a)と(b, b + 1, ..., N)のゴーレムが消滅することを意味しているため、最終的な解はa + (N + 1 - b)となります。

実装の工夫

実は上で説明したようにf(x)とg(x)にわけて実装するのは少し面倒くさいです。 理由はf(x)が単調減少、g(x)が単調増加と、2つの関数がそれぞれ異なる性質を持つからです。 これは2パターンの二分探索を実装する必要があります。 そこで、少し楽をするために初期のマスの状態を逆順(ABC → CBA)にしたものと全てのd_iを逆方向にしたもの('L' → 'R')を用意します。 すると、g(x)で求めようとしていた情報をf(x)で同じように求めることができます。 新たに用意したマスと呪文を利用して求めたaは元のマスと呪文を利用して求めた(N + 1 - b)と等しくなります。

計算量

a, bを求めるためにx(0 < x < N + 1)について二分探索を行うため、O(\log{N})
f(x), g(x)を求めるのは、初期位置がxマス目のゴーレムの1体だけシミュレーションすればよいため、O(Q)

したがって、全体での時間計算量はO(Q\log{N})になります。

ソースコード

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// x番目のゴーレムをk番目のマスに移動させられるかシミュレートして確認する
bool checkLeft(int x, int k, string &s, vector<char> &t, vector<char> &d)
{
    for(int i = 0; i < t.size(); ++i)
    {
        if(t[i] == s[x])
        {
            x += (d[i] == 'L' ? -1 : 1);
        }
 
        if(s[x] == '_')
        {
            // マスの端に到達してもx == kが成り立つとは限らないことに注意する
            return x == k;
        }
    }
 
    return false;
}
 
int main()
{
    int n, q;
    string s;
 
    cin >> n >> q;
    cin >> s;
 
    // 消滅判定を簡単にするためにマスの両端に'_'をくっつけておく
    s = "_" + s + "_";
 
    vector<char > t(q);
    vector<vector<char> > d(2, vector<char>(q));
    for(int i = 0; i < q; ++i)
    {
        cin >> t[i] >> d[0][i];
        // マスの配置を反転させると操作も反転することに注意する
        d[1][i] = (d[0][i] == 'L' ? 'R' : 'L');
    }
 
    int golem = n;
    for(int i = 0; i < 2; ++i)
    {
        // 0マス目に到達する最も右のゴーレムの位置を二分探索する
        int lb = 0, m, ub = n + 1;
        while(ub - lb > 1)
        {
            m = (ub + lb) / 2;
            (checkLeft(m, 0, s, t, d[i]) ? lb : ub) = m;
        }

        // lbの位置にいるゴーレムより左にいるゴーレムは消滅する
        golem -= lb; 

        // 列を反転させてからもう一度同じ操作を行う
        reverse(s.begin(), s.end());
    }
 
    cout << golem << endl;
}

感想

初めて500点問題を自力で解くことができました。問題の中で単調増加性を発見した時には感動してため息が出てしまいました。

AtCoder Beginner Contest 112 D - Partition

競技プログラミング AtCoder ABC

問題

atcoder.jp

考察と解法

まずはじめに、すべてのa_iがすべてのa_iの最大公約数で割り切れることに気づきました(それはそう)。
a_1 + a_2 + ... + a_N = Mを満たす (a_1, a_2, ..., a_N)の最大公約数を xとするとa_i \mod x = 0であるから
自然数 (b_1, b_2, ..., b_N)を用いて

b_1 x + b_2 x + ... + b_N x = M
(b_1 + b_2 + ... + b_N)x = M (式1)

となり、xはMの約数であることがわかります。
したがって、Mの約数をすべて列挙し、(式1)のxに代入して満たすか確認すればよいです。 しかし、xが最大公約数でなくても、公約数であるなら(式1)を満たすことがわかります。
例えば、N = 3, M = 14の場合を考えると

Mの約数=(1, 2, 7, 14)

(2 + 4 + 8)1 = 14
(1 + 2 + 4)2 = 14

となりx = 1, 2の2つの場合があることがわかります。 (式1)を満たすxをすべて求めて最大のものが真のxとなるため、この場合はx=2が解になります。 また、(7, 14)はMの約数でありながらx=7, 14では(式1)を満たすことはできません。 この理由は、(式1)を以下のように変形するとわかります。

(b_1 + b_2 + ... + b_N) = \frac M x

xはMの約数なので右辺は必ず整数値になります。 (b_1, b_2, ..., b_N)が自然数であるという制約から

(b_1 + b_2 + ... + b_N) \ge N
\frac M x \ge N (式2)

となり、x=7, 14では(式2)を満たさないため、条件を満たす(b_1, b_2, ..., b_N)を構成することができません。 逆に(式2)を満たすなら、(b_1, b_2, ..., b_N) = (1, 1, ..., \frac M x - N + 1)とすることで(b_1, b_2, ..., b_N)を構成することができます。

以上のことをまとめると以下のアルゴリズムでこの問題を解くことができます。

アルゴリズム

  1. Mのすべての約数を列挙する
  2. Mの約数の中から(式2)を満たすxをすべて調べる
  3. 2で調べたxの中で最大のものを解とする

計算量

1の処理がO(\sqrt M)
2の処理が多く見積もってO(2\sqrt M)
3は2を行う中で最大値を更新すればよいため、O(1)

1, 2の処理は独立しているため、全体の計算量はO(\sqrt M)

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, m, gcd = 1;
    vector<int> divisor;
 
    cin >> n >> m;
 
    for(int i = 1; i * i <= m; ++i)
    {
        if(m % i == 0)
        {
            divisor.push_back(i);
            divisor.push_back(m / i);
        }
    }
 
    for(int i = 0; i < divisor.size(); ++i)
    {
        if(m / divisor[i] >= n)
        {
            gcd = max(gcd, divisor[i]);
        }
    }
 
    cout << gcd << endl;
}

感想

数学っぽい問題が本当に苦手なので解けて嬉しいです。

AtCoder Beginner Contest 001 C - 風力測定

競技プログラミング AtCoder ABC

問題

atcoder.jp

考察と解法

この問題は以下の2つを達成することで解決できます。

  • 風向の角度から方位を表す文字列(N, NNE, ..., NNW)への変換
  • 風速から風力への変換

変換自体は特にアルゴリズムを要求されることがなく、問題文に示されたルールに従うだけであるから簡単です。 しかし、各変換を行う際にはそれぞれ面倒くさい点があります。それは以下の2つです。

  1. 方位Nに対応する風向の角度の範囲が0.00度以上11.25未満と348.75度以上360.00度未満の2つの範囲がある
  2. 風程から風速への変換、少数第2位の四捨五入で浮動小数点数の誤差が発生する場合がある

1については、方位に対する角度の範囲全てに11.25を足せばよいです。円を回すイメージです。
これによって、すべての方位に対する角度の範囲の始まりと終わりが360 / 16 = 20.5の倍数になります。
と同時に、Nに対応する角度の範囲が360.00度以上20.5未満に集約されます。
あとは角度を20.5で割った商から方位を決定できます。

2については、すべての計算を整数のみで行えばよいです。
まず、風速の範囲が少数第1位までしか存在しないため、全て10倍して整数のみにします。 風力に変換する際には、少数第2位を四捨五入したあとの風速を10倍したものが範囲に収まるか確認すればよいです。
風速の計算ですが、まず与えられた風程を予め100倍しておき、それを60(秒)で割ります。
100倍してから除算することで、失われる可能性のある少数第2位までの計算を正確に行なえます。
あとはお決まりの四捨五入テクニックで5を足した結果を10で割れば変換完了です。

変換後の風速 = (1分間の風程 * 10 / 6 + 5) / 10;

ソースコード

#include <iostream>
#include <algorithm>

using namespace std;

string degToDir(int deg)
{
    static const string dir[16] = {
        "N", "NNE", "NE", "ENE", "E", "ESE", "SE", "SSE",
        "S", "SSW", "SW", "WSW", "W", "WNW", "NW", "NNW"
    };

    static const int degPerDir = 2250;

    deg = (deg * 10 + 1125) % 36000;

    return dir[deg / degPerDir];
}

int disToPower(int dis)
{
    static const int levelBounds[13] = {
        0, 3, 16, 34, 55,
        80, 108, 139, 172, 208,
        245, 285, 327
    };

    dis = (dis * 10 / 6 + 5) / 10;

    return upper_bound(levelBounds, levelBounds + 13, dis) - levelBounds - 1;
}

int main()
{
    int deg, dis;

    string dir;
    int w;
    
    cin >> deg >> dis;

    dir = degToDir(deg);
    w = disToPower(dis);

    cout << (w == 0 ? "C" : dir) << " " << disToPower(dis) << endl;
}

感想

よく考えたら風速から風力への変換時の誤差は風速の範囲の単位を風程に変換すれば消えるため、その後比較するだけでよかったです。