ARC138 - C : Rotate and Play Game
問題
解法
大きい方からN/2個がどんな並びでも取れそうと思い、その証明を得た。
やってること自体は本解説と同じな気がするが、こっちの方が断然わかりやすいはず。
次の図が全てである。
値を取る場合は y方向に1歩進み、取らない場合はx方向に1歩進む。 x = p に初めて到達した時に y の値が p より大きいと、「大きい方からN/2個取る」のに失敗する。
cyclic shift をするのは、このグラフでいうスタート地点を変更することに対応するので、
青点のように、y = x から最も離れた点 (すなわち、y - x が最も大きい点) から始めれば、
x = p に初めて到達した時の y の値は p 以下となる。
つまり、大きい方から N/2 個取ることに成功する。
int main(){ int n; cin >> n; V<ll> a(n); rep(i,n) cin >> a[i]; V<int> use(n); priority_queue<pair<int, int>, V<pair<int, int>>, greater<>> que; rep(i,n/2) que.emplace(a[i], i); for(int i = n/2; i < n; i++){ if(que.top().fi < a[i]){ que.pop(); que.emplace(a[i], i); } } ll sum = 0; while(sz(que)){ sum += que.top().fi; use[que.top().se] = 1; que.pop(); } int idx = -1, dif = 0, cur = 0; for(int i = 0; i < n; i++){ if(use[i]) cur++; else cur--; if(chmax(dif, cur)) idx = i; } cout << idx << " " << sum << endl; }
OCaml メモ
はじめに
関数論理型プログラミング実験というものがあり、OCamlを書くことになった。そこで、とりあえず色々メモしておいて、後で誰かの役に立てればええか〜と。大した内容は書かない(書きたくもない)ので、あんまり期待はしないでね。それでは、、、
文法編
・リストのコンス、連結について
コンス → A :: B
x :: [y;z] (= [x;y;z]) だったり [a;b] :: c;d (= [[a;b];[c;d]]) として使う。
同じ型のものを、より大きなリストに先頭に保存できる。
連結 → A @ B
[x] @ [y] (= x :: [y]) だったり a;b @ c;d ( = [a;b] :: c;d) として使う。
一重以上のリストで同じ型のものを、の数は増やさずに連結して保存。
(例) 二重配列 llst の各要素(リスト)の先頭にxを追加するやつ (画像すまん)
(注) llst = []の時なら動くが、とするとダメなのはお分かりだろうか
[]の時、y = , ys = (= 二重リストだけど空)であるからだ。
- モジュールについて
structure, signature, functorと3つ出てくる。
structure → C/C++でいうstructなどに結構似ているので問題ないと思う。
signature → そのモジュールが外部から見えてる型を表す。
signatureを使わないで 'a list' だけだと、ユーザ側が同じ型'a list' を持つ変数を宣言するなどして意図的にごっちゃにできるとよくない。
C/C++のstructでいうpublic, privateのイメージがあると理解しやすいかもしれない。
module M : signature = m
として宣言。実体は m と同等だけど、見えるものが異なる M が生成される。
OCamlのモジュール (ストラクチャ) とモジュール型 (シグネチャ) - Qiita
functor → 似たようなモジュールの定義を何度もするのを避ける目的。
module F = functor (T : TYPE) -> struct ... end
これはTYPEのシグネチャと同じ構造を持つものは、後でこのfunctor Fに代入することで、struct以後に書いた内容のものが実現できることを表している。
つまり、TYPEの部分を変えればmoduleの長い定義を1から書く必要がなくなる。
実際に代入するときは、module M = F (m) のようにmodule m を渡せば良い。
繰り返しになるが、この時の m は TYPEと同じ構造を持ってる必要がある。
signatureを返すようなfunctorもあるが、仕組みは同じ
OCaml 入門その4 モジュール・ファンクタ - Qiita
演算の優先順位について
6.7 式 をまずは見るべき。特に関数の優先順位は高いのと、左結合であることをしっかりと意識すると、変なバグや解釈をしなくて良い。特にfold_leftをfold_rightで書く課題などは、これ分かってないと詰むかも(私はList.fold_right で List.fold_left を書く - fetburner.coreを解読するのに、無限時間かけてしまいました...)。
コード編
再帰とかの挙動が分からない場合は、再帰の深さが小さいやつを手書きなどでもいいので展開してみるといい。
コードを書くとインタプリタ君がどんな型を想定しているかを返してくれるので、それを見るのもいいかもしれない。返り値はベースケースにしたやつの型になるので、わざわざみる必要もないかもしれないが...。どんな型の引数の想定になってるかとかの情報も見れるのは良さげ。
その他有名な事柄について(OCamlで書かれてないものも含む)
ラムダ計算、チャーチ数、再帰関数 :
Lecture 29: Fixpoints and Recursion
多相、単相など:
Imperative Programming - Real World OCaml
精進に対するお気持ち表明
お気持ち
僕はAtCoderが青でまだ全然強くないのですが、最近思ったこと(自戒でもあること)があるのでここに書いておきます。
皆さんは、精進をどうしているでしょうか。 アルゴリズムの勉強、早解きの練習、高難易度を通す練習、バチャなどなどそれぞれあると思います。 特に精進はこうするのがいいよねとか、そういった意見はありませんし、人の精進法についてケチをつける気もありません。
ただ、なんか競プロのコンテスト(に限らず色々なこと)で負けてる人の特徴ってこうなんじゃね？と考えついたので発表します。
人って問題が解けると気持ち良くなりますよね。 人ってコンテストでレートが上がると気持ち良くなりますよね。 でもコンテストで負けると気持ち良くはないですよね。
コンテストで気持ち良くなれないのに、普段の精進でも気持ち良くなれなかったらメンタルが厳しくなるので、普段の精進で自分の能力を伸ばそうとしない問題を解いたりして、気持ち良くなりますね。そんで、自分のできること自体は何も変わってないので、コンテストで再び負けて嫌な気分になります。嫌な気分になったコンテスト後は自分にとってのcomfort zoneに入ったまま問題を解いてメンタルを回復させます。
これを繰り返す人が「精進してるつもりであんまり伸びない人」なんじゃないかなと思ったわけです。 (今思うとこれ、入青するくらいまでの自分やん。その色の中では早解きが十分なレベルなのに、高めの難易度には手を出そうとしない自分やん。)
能力を伸ばそうとしないというのは、決して低難易度帯をやることを批判してるわけではないです。早解きを意識して、限界まで早く解こうとする練習自体は能力を伸ばす事にあたります。しかし、青の人が灰色の問題ばかりをやってるのは明らかにおかしいですね。という話です。
他にも、バチャをやって解けない問題のupsolveをしたいとします。このバチャでは6問中4問が結構楽に解けて、本番ならいいパフォが出そうだとなりました。ライバル達も5問目が解けていません。あなたはここで精進をやめますか...？ とか。たまたま自分の得意分野だったかもしれないけど、upsolveしなかったらただの自己満足です。マジで。普段の精進で気持ち良くなってるだけじゃん、となりますね。
精進って元々、厳しい覚悟のもと何かを成し遂げるための訓練みたいなニュアンスがあった気がします。 コンテストで気持ち良くなるには、普段嫌な気分になっておくしかないなあと。 嫌な気分というのも語弊があって、自分ができないことをできるようにしていくってことを言いたいです。 新しいことを身につける、学ぶごとに嫌な気分になるなら、それはあなたに知識欲/学習欲がないことを意味します。適性がないだけです。 だから、どの分野でも楽しんでできる人が強いんです。前に進むことに一切の躊躇いがないからです。学習コストをコストだと思わないからです。
以上、お見苦しいお気持ちでした。
理情のCPU実験シミュレータ係のはなし。
目次
はじめに
この記事は、東京大学理学部情報科学科の3Aにある名物実験「CPU実験」についてです。前から言われていたことですが、ネットにシミュレータ係に関するブログ記事があまりなく情報量が少ない状態だったので、正直何をすればいいかというイメージがつきにくい担当になっています(僕はイメージがつかないまま3Aを迎えました)。ちゃんと何をやるか把握してから自分の希望する担当を選べると良いのでこの記事を書きます。
ということで、早速中身に入りましょう。
シミュレータ係とは
まずCPU実験は大雑把にいうと
ことが目標になります。これだけを見るとシミュレータ係は特に何もしていない気分になります。
ではシミュレータ係の仕事とはなんなのでしょうか。
単刀直入にいうと、CPU の動きそのものをシミュレーションする事を指します。より具体的には、与えられたプログラム(レイトレ)がコンパイルされてアセンブリ/バイナリになるわけですが、これをシミュレータ係の作ったシミュレータで動かした時に、コア係やFPU係の書いたプログラムと同じ動き(fpu演算やメモリ上の値など)になるようにすることです。
なぜこんな事をするのかというと、自作コアや自作コンパイラのデバッグをするため という一言に尽きます。*1
命令列を受け取った時にどういう挙動を示すのが正しいのかを言ってくれる絶対的である神のような存在がないと、人間のようなちっぽけな存在は、迷える子羊ちゃんたちのようになります。
よって、シミュレータ係の使命は「神になること」です。
まだよく分からんという人でも安心してください、次の内容で詳述しています。
やること
先に列挙していきます。
ISAの決定(自信がなければ他の係と相談して決めるのも全然OK)
アセンブリ/バイナリのパーサー
パースされた命令を実行するインタプリタのようなものの作成
FPUのエミュレート
シミュレータの機能充実
統計情報の集計
ざっとこんな感じですが、実際には 5番は正直オプションみたいな感じで単位取得には完成したコアの出力と同じものを吐けばOKです。*2
まず ISAの決定ですが、今年は RISC-V をベースとする班が多かったです。 うちの班だけ PowerPC のISAを用いて†圧倒的成長† をしました。
これを早々に決める理由は、2番目でアセンブリ/バイナリのパーサーを書くことになるからです。命令のフォーマットが決まってないと、シミュレータ係は何もできません。
パーサーを書くというのは、コンパイラ係から渡されるアセンブリ/バイナリの列がどのような命令列かを認識する行為だと考えると良いと思います。
これが完成すると、仕様書に沿った命令を実行するようなプログラムをかくことで、インタプリタができます。1つだけ例を挙げますね。
add r4, r5, r6
これはどのISAにもあるような命令ですが、レジスタ4番にレジスタ5番の中身 + レジスタ6番の中身を代入するという命令です。 今現在、パースによってこのような命令だと分かっている状態です。 シミュレータはコアと同じような内部構造を持っているように構造体などを定義すれば良い*3(レジスタがあって、メモリがあって、...)ので、シミュレータ上でもこの演算を行って、レジスタ4番を更新すれば良いです。
そしてFPUのエミュレートです。FPU係は指定された誤差範囲を超えない範囲で高速化をしていくので、実際のIEEEで規定されている浮動小数点演算とは基本的に異なる値が出てきます。なので、これに関してはちゃんと模倣してテストしてあげないと、どこにバグがあるか分からなくなります。
はい、そうすると大体完成しますが、さっき言ったようにコア/コンパイラ係がこれを使ってデバッグ出来なければ、このシミュレータの存在価値は0です。 よって機能を拡充していきます。
例えば、1ステップずつ実行する/実行巻き戻し/ディスアセンブラの作成/GUIの作成 とかが挙げられます。まあ、ここは好き勝手にカスタマイズしてくれて結構です。他の係の要望を聞いて適宜実装して行きましょう。(GUIとか作るの結構だるいし...)
最後の統計情報は、よく分かりません！よしなにやりましょう。*4
まとめ
大体こんな感じです。
正直どの係になっても楽しい地獄が待っていると思うので、覚悟して臨みましょう。
言い忘れていましたが、使用するプログラミング言語は任意です。 トロいシミュレータは怒りを買うかもしれないので、C/C++やRustを使うと良いと思います。
では。
お釣りの嫌いな高橋君
- 問題
- 解法
dpをする.
i 番目のコインが有り余ってたら i + 1 番目のコインとして見なすことで、i 番目のコインを 0 ~ max(a[ i ] + 下からの傘増し, 9) しかないと思っても良い.
各ステップ i で下から傘増しされるコインの種類数はそんなに多くはないことから、mapを使って以下のようにdpテーブルを定義する.
dp[ i ][ j ][ k ] : 右から i 桁目まで処理した後、i 桁目の値が j で、i + 1 番目のコインが k 枚増えるような決め方の場合の数.
最後に全部ゼロ枚使う場合を引けばおしまい.
- 提出コード
Codeforces Educational Round 111 D - Excellent Arrays
- 問題
- 解法
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(); }
