Soohの嘆き呟き

競プロ解説記事をかくぞ。

精進に対するお気持ち表明

お気持ち

僕はAtCoderが青でまだ全然強くないのですが、最近思ったこと(自戒でもあること)があるのでここに書いておきます。

皆さんは、精進をどうしているでしょうか。 アルゴリズムの勉強、早解きの練習、高難易度を通す練習、バチャなどなどそれぞれあると思います。 特に精進はこうするのがいいよねとか、そういった意見はありませんし、人の精進法についてケチをつける気もありません。

ただ、なんか競プロのコンテスト(に限らず色々なこと)で負けてる人の特徴ってこうなんじゃね?と考えついたので発表します。

人って問題が解けると気持ち良くなりますよね。 人ってコンテストでレートが上がると気持ち良くなりますよね。 でもコンテストで負けると気持ち良くはないですよね。

コンテストで気持ち良くなれないのに、普段の精進でも気持ち良くなれなかったらメンタルが厳しくなるので、普段の精進で自分の能力を伸ばそうとしない問題を解いたりして、気持ち良くなりますね。そんで、自分のできること自体は何も変わってないので、コンテストで再び負けて嫌な気分になります。嫌な気分になったコンテスト後は自分にとってのcomfort zoneに入ったまま問題を解いてメンタルを回復させます。

これを繰り返す人が「精進してるつもりであんまり伸びない人」なんじゃないかなと思ったわけです。 (今思うとこれ、入青するくらいまでの自分やん。その色の中では早解きが十分なレベルなのに、高めの難易度には手を出そうとしない自分やん。)

能力を伸ばそうとしないというのは、決して低難易度帯をやることを批判してるわけではないです。早解きを意識して、限界まで早く解こうとする練習自体は能力を伸ばす事にあたります。しかし、青の人が灰色の問題ばかりをやってるのは明らかにおかしいですね。という話です。

他にも、バチャをやって解けない問題のupsolveをしたいとします。このバチャでは6問中4問が結構楽に解けて、本番ならいいパフォが出そうだとなりました。ライバル達も5問目が解けていません。あなたはここで精進をやめますか...? とか。たまたま自分の得意分野だったかもしれないけど、upsolveしなかったらただの自己満足です。マジで。普段の精進で気持ち良くなってるだけじゃん、となりますね。

精進って元々、厳しい覚悟のもと何かを成し遂げるための訓練みたいなニュアンスがあった気がします。 コンテストで気持ち良くなるには、普段嫌な気分になっておくしかないなあと。 嫌な気分というのも語弊があって、自分ができないことをできるようにしていくってことを言いたいです。 新しいことを身につける、学ぶごとに嫌な気分になるなら、それはあなたに知識欲/学習欲がないことを意味します。適性がないだけです。 だから、どの分野でも楽しんでできる人が強いんです。前に進むことに一切の躊躇いがないからです。学習コストをコストだと思わないからです。

以上、お見苦しいお気持ちでした。

理情のCPU実験シミュレータ係のはなし。

目次

はじめに

この記事は、東京大学理学部情報科学科の3AにあるCPU実験をこれから経験する予定の後輩たちに捧げます。前から言われていたことですが、ネットにシミュレータ係に関するブログ記事がほとんどなく情報量が少ない状態だったので、正直何をすればいいかというイメージがつきにくい担当になっています。ちゃんと何をやるか把握してから自分の希望する担当を選べると良いのでこの記事を書きます。

ということで、早速中身に入りましょう。

シミュレータ係とは

まずCPU実験は大雑把にいうと

  • 与えられたプログラムを自作コンパイラ(コンパイラ係)によってコンパイルし、

  • コアや浮動小数点演算器やメモリに関するあれこれ(コア係、FPU/メモリ係)のプログラムによって、FPGAという基盤上で配線を行い、

  • これが CPU として動くようにする

ことが目標になります。これだけを見るとシミュレータ係は特に何もしていない気分になります。

ではシミュレータ係の仕事とはなんなのでしょうか。

単刀直入にいうと、CPU の動きそのものをシミュレーションする事を指します。より具体的には、与えられたプログラム(レイトレ)がコンパイルされてアセンブリ/バイナリになるわけですが、これをシミュレータ係の作ったシミュレータで動かした時に、コア係やFPU/メモリ係の作ったコアなどのプログラムと同じ動きをするように実装をしていくわけです。

なぜこんな事をするのかというと、自作コアや自作コンパイラデバッグをするため という一言に尽きます。*1

命令列を受け取った時にどういう挙動を示すのが正しいのかを言ってくれる絶対的である神のような存在がないと、人間のようなちっぽけな存在は、迷える子羊ちゃんたちのようになります。

よって、我らシミュレータ係の使命は「神になること」です。

まだよく分からんという人でも安心してください、次の内容で詳述しています。

やること

先に列挙していきます。

  1. ISAの決定(自信がなければ他の係と相談して決めるのも全然OK)

  2. アセンブリ/バイナリのパーサー

  3. パースされた命令を実行するインタプリタのようなものの作成

  4. FPUのエミュレート

  5. シミュレータの機能充実

  6. 統計情報の集計

ざっとこんな感じですが、実際には 5番は正直オプションみたいな感じで単位取得には完成したコアの出力と同じものを吐けばOKです。*2

まず ISAの決定ですが、今年は RISC-V をベースとする班が多かったです。 うちの班だけ PowerPC のISAを用いて†圧倒的成長† をしました。

これを早々に決める理由は、2番目でアセンブリ/バイナリのパーサーを書くことになるからです。命令のフォーマットが決まってないと、シミュレータ係は何もできません。

パーサーを書くというのは、コンパイラ係から渡されるアセンブリ/バイナリの列がどのような命令列かを認識する行為だと考えると良いと思います。

これが完成すると、仕様書に沿った命令を実行するようなプログラムをかくことで、インタプリタができます。1つだけ例を挙げますね。

add r4, r5, r6

これはどのISAにもあるような命令ですが、レジスタ4番にレジスタ5番の中身 + レジスタ6番の中身を代入するという命令です。 今現在、パースによってこのような命令だと分かっている状態です。 シミュレータはコアと同じような内部構造を持っている*3(レジスタがあって、メモリがあって、...)ので、シミュレータ上でもこの演算を行って、レジスタ4番を更新すれば良いです。

そしてFPUのエミュレートです。FPU係は指定された誤差範囲を超えない範囲で高速化をしていくので、実際のパソコンで行う浮動小数点演算とは基本的に異なる値が出てきます。なので、これに関してはちゃんと模倣してテストしてあげないと、どこにバグがあるか分からなくなります。

はい、そうすると大体完成しますが、さっき言ったようにコア/コンパイラ係がこれを使ってデバッグ出来なければ、このシミュレータの存在価値は0です。 よって機能を拡充していきます。 例えば、1ステップずつ実行する/実行巻き戻し/ディスアセンブラの作成/GUIの作成 とかが挙げられます。まあ、ここは好き勝手にカスタマイズしてくれて結構です。他の係の要望を聞いて適宜実装して行きましょう。(GUIとか作るの結構だるいし...)

最後の統計情報は、よく分かりません!よしなにやりましょう。*4

まとめ

大体こんな感じです。

正直どの係になっても楽しい地獄が待っていると思うので、覚悟して臨みましょう。

言い忘れていましたが、使用するプログラミング言語は任意です。 トロいシミュレータは怒りを買うので、C/C++やRustを使うと良いと思います。

では。

*1:他の係がバグを一切埋め込まない天才プログラマーだった場合には、シミュレータ係の出る幕はありません。

*2:ただし、21er からキャッシュの模倣および実行時間予測が加わりました。

*3:コアの完全模倣をすることをエミュレートすると言いますが、その必要はなくて、飽くまでコアの動きが再現できる程度でいいのです。

*4:実行時間予測をするなら命令数と実行時間の関係性をむにゃむにゃと...

ARC098 - Minimum Range Queries

  • 問題

atcoder.jp

  • 解法

最終的に選んだものは、小さい方から取っていくのが最適だと証明可能.

ということで、最小の値 X を固定したらそこから貪欲に取れば良い.

「X 未満の値は取れない ⇔ X未満の値を跨ぐような区間を選べない」

ゆえに X 未満の値がある場所で分割してしまえば、より小さなサイズの問題になる.

しかも小さなサイズの問題の中では、この分割された区間内の最小値がこの区間から選ばれる最小値と考えて良く、貪欲に取ればいいのでソートするだけで十分である.

  • 反省

区間を分割するアイデアが思い浮かばなかったとです...

 

お釣りの嫌いな高橋君

  • 問題

atcoder.jp

  • 解法

dpをする.

i 番目のコインが有り余ってたら i + 1 番目のコインとして見なすことで、i 番目のコインを 0 ~ max(a[ i ] + 下からの傘増し, 9) しかないと思っても良い.

各ステップ i で下から傘増しされるコインの種類数はそんなに多くはないことから、mapを使って以下のようにdpテーブルを定義する.

dp[ i ][ j ][ k ] : 右から i 桁目まで処理した後、i 桁目の値が j で、i + 1 番目のコインが k 枚増えるような決め方の場合の数.

最後に全部ゼロ枚使う場合を引けばおしまい.

 

  • 提出コード

atcoder.jp

Codeforces Educational Round 111 D - Excellent Arrays

  • 問題

codeforces.com

  • 解法

1-indexedで扱う. N は 配列のサイズである.

B_i = A_i - i と定義する.

A_i + A_j = i + j は B_i = -B_j と書き換えられる.

L <= A_i <= R だったので L - i <= B_i <= R - i である.

F(a)の最大値を達成するのはどんな時かを考えると,

B_i = x となる i が floor(N/2) 個あり、B_i = -x となる i が ceil(N/2) 個の時である.

これは帰納法により証明できるが省略する.

とはいえ、この問題では必ずF(a)がfloor(N/2) * ceil(N/2)になるかまだ分からない.

なぜなら、任意の x について B_i = x となるのが s_x 個で、B_i = -x となるのが t_x 個だったとして、s_x + t_x < N しかならない場合があるかもしれないからだ

正の整数を x として、x と -x のペアを作ることを考える.

以下の式変形では問題の制約による L <= 1, R >= N に気をつける.

B_i = x となる i の条件は L - i <= x <= R - i すなわち 1 <= i <= R - x

同様に B_i = -x となる i の条件は L - i <= -x <= R - i すなわち L + x <= i <= N

この2つの不等式から以下のことが言える.

R - x >= N かつ L + x <= 1 つまり 1 <= x <= min(R - N, 1 - L) の時は

「任意の i について、B_i = x にも B_i = -x にも出来る」が成立 - 1.

R - x <= 0 または L + x >= N + 1 つまり x > min(R, N + 1 - L) の時は、「任意の i について B_i = x に出来ない」または 「任意の i について B_i = -x に出来ない」が成立 - 2.

1 について

L < 1 かつ R > N の時は必ずこのような x が存在し、

この時の F(a) の最大値は floor(N/2) * ceil(N/2) であることが容易にわかる.

要は、B_i = x にする i の個数を K, -x にする i の個数を (N - K) とした時

K(N - K) を最大化したいので、K = N/2, (N+1)/2 が最適だからだ. (割り算は切り捨て)

よって、この範囲の各 x については B_i を x か -x にするかを選んで半々にすればよく、

どの i を選んで x にするかを決めればいいので二項係数で計算できる.

また、この場合の数は x に依らないのでまとめて計算できる.

2 について

x が 当該の範囲にある時は、(x, -x)というペアを作ることが出来ないのでこの範囲は無視しても良い事になる.

x <= min(R - N, 1 - L) の時と x > min(R, 1 - L + N)の時は 1, 2でカバーしたので、

min(R - N, 1 - L) < x <= min(R, 1 - L + N) を考えればよい.

1, 2のどちらでもないので、「任意の i について、B_i = x または B_i = -x の少なくとも一方にできる」

先程の考察から、

B_i = x に出来ない i は R - x < i <= N

B_i = -x に出来ない i は 1 <= i < L + x

B_i = x に出来ないような i については、B_i = -x にするしかない.

同様に B_i = -x に出来ないような i については B_i = x にする事になる.

残りの要素については、x か -x のどちらにも出来るので、うまく数合わせをしてF(a)の最大値を達成できるなら、それを答えに足し合わせれば良い.

L = 1 または R = N の場合は、1 において F(a) = floor(N/2) * ceil(N/2) になるとは言えなかったが、x がこの範囲にある場合は不等式を睨むと必ず達成できることも分かる.

この範囲はO(N)個しかないので、1つずつ考えても大丈夫である.

以上によって、この問題が解けた.

  • コード
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;

const int MAX = 200001;
long long fact[MAX], finv[MAX], inv[MAX];

void Comb_init(){
    fact[0] = fact[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fact[i] = fact[i-1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod; 
    }
}
long long comb(long long n, long long k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fact[n] * finv[k] % mod * finv[n - k] % mod;
}

void add(ll &a, ll b){
    a += b;
    if(a >= mod) a -= mod;
}

void solve(){
    int n, l, r; 
    cin >> n >> l >> r;
    ll k = min(r - n, 1 - l);
    // 1 <= x <= k の範囲では、全ての i でB[i]が x にも -x にもできる
    ll ans = 0;
    // x になる i を n/2 or (n/2 + 1) 個になるように選ぶ
    add(ans, k * comb(n, n/2) % mod);
    if(n % 2 == 1) add(ans, k * comb(n, n/2+1) % mod);
    for(int x = k + 1; x <= min(r, 1 - l + n); x++){
        int a = max(0, n - (r - x)); // B[i] = -x にしか出来ない
        int b = max(0, l + x - 1);   // B[i] = x にしか出来ない
        int rem = n - a - b; // b[i] = x にも -x にもできる
        add(ans, comb(rem, n/2 - a));
        if(n % 2 == 1) add(ans, comb(rem, n/2 + 1 - a));
    }
    cout << ans << endl;
}

int main(){
    Comb_init();
    int t; cin >> t;
    while(t--) solve();
}

典型90 015 Don't be too close

https://atcoder.jp/contests/typical90/tasks/typical90_o

 

数弱が悲鳴を上げてしまった...

場合の数をちゃんと勉強しましょうの問題です。

 

高校数学典型その1

ある数字 n を選んだら (n + 1) ~ (n + k - 1) までは使えないので、n ~ (n + k - 1) をまとめて考える

 

じゃあ、どの n を選んでいこうか、、、

まず 1 を選んだ場合 2 ~ K は使えなくて、、、

と考えていくと良くない。ぬまる。ぬまった。数弱でごめん。

 

高校数学典型その2

先に配置を決めてから、数字を順に割り当てる

 

今 1 ~ N まで数字があったとする。

p 個えらんで並べた時に何が起こるかというと

[K個の連続した数字が詰まった箱] が (p - 1) 個

右端の数字 が 1 個 

消費される。

使われなかった数字は N - (p - 1)K - 1 個になる。

 

ここで、(p - 1) + (1) + (N - (p - 1)K - 1) = N - (p - 1)(K - 1) の"モノ"を並べ替えることを考える。(配置を決めるパート)

適当に並び替えた"モノ"に対して、左から 1, 2, ..., N と数字を割り当てれば(箱には K 個の数字を割り当てる)、うまく分割できてることがわかるだろう。

 

つまり、N - (p - 1)(K - 1) から "モノ"を p 個指定する話に帰着された。

(右端となる数字は選んだうちの最後の"モノ"でないといけないことに注意)

これは二項係数により簡単に計算できる。

 

数弱大変...