Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

パタヘネ第6版　第1章演習問題解答

院試 パタヘネ コンピュータアーキテクチャ

6th editionについての解答。

解答がおかしいとかがありましたらSen(@nonpro3)のTwitterアカウントにDMやリプライ飛ばしてください。

大体ここにある。 ただし、これは最新の6th editionではないので、下に対応表と乗ってない問題の回答を載せる。

6th edition old
1.1 1.1
1.2 1.2
1.3 1.3
1.4 1.4
1.5 1.5
1.6 なし
1.7 1.6
1.8 1.7
1.9 1.8
1.10 1.9
1.11 1.10
1.12 1.11
1.13 1.12
1.14 なし
1.15 1.13
1.16 1.14

以下の者はすべて6th editionのもので新規追加された問題の回答。

1.6

平均改善率を$ a $とすると、$ \log _ 2 a $が9年にあたるので、答えは$ \frac{\log _ 2 2}{\log _ 2 a} \times 9 $

改善率は$ 100 - \sqrt[9](100 - 9年での改善) $で求めている。

指標 9年での改善 改善率 性能倍増に必要な年数
技術 56.25% 6.2% 7.569年
最高クロック周波数 1.471倍 4.38% 16.16年
整数IPC/コア 2倍 8.01% 9年
コア数 4倍 16.65% 4.5年
最大BRAMバンド幅 2.497倍 10.7% 6.817年
SP浮動小数点 5.860倍 21.70% 3.528年
L3キャッシュ 3倍 12.98% 5.678年

1.9

ごめんなさい。わからないです。多分院試に出ないのでスキップさせていただきます……

1.11

$$ ウエーハあたりのダイの数 \approx \frac{ウエーハの面積}{ダイの面積} $$

$$ 歩留まり = \frac{1}{(1 + (\frac{単位面積の欠陥数 \times ダイの面積}{2})) ^ 2} $$

この2つの式を使う。後者は経験則。円周率は3.14とした。

1.11.1

直径15cm->$ \frac{1}{1.02207 ^ 2} = 95.73 $%

直径20cm->$ \frac{1}{1.04867 ^ 2} = 90.93 $%

1.11.2

良品のダイあたりのコストは、$ \frac{ウェーハあたりのコスト}{ダイの数×歩留まり率} $。

直径15cm->$ \frac{12}{84 \times 0.9573} \simeq 0.14922 $

直径20cm->$ \frac{15}{100 \times 0.9093} \simeq 0.16496 $

1.11.3

ダイの面積は、ウェーハあたりのダイを増やすので小さくなり、90.9%の縮小となる。

ダイの歩留まりは、計算式から、$ \frac{1}{1 + (1 \times 1)} ^ 2 = 0.25 $

と比べて、$ \frac{1}{1 + (1.15 \times 0.909)} = 0.2390 $

よって、下がる。

1.11.4

先ほどの式から逆算する。

改善前: $ 0.92 = \frac{1}{(1 + \frac{200 \times x}{2}) ^ 2}, x = 4.257 \times 10 ^ {-4} $

改善後: $ 0.95 = \frac{1}{(1 + \frac{200 \times x}{2}) ^ 2}, x = 2.598 \times 10 ^ {-4} $

1.14

浮動小数点 ロードストア 分岐 その他
70s 80s 40s 60s

1.14.1

全体では$ 250-70 \times 0.2 = 250 - 14 = 234　\frac{234}{250} = 0.936 $ 6.4%

1.14.2

問題文が意味不明なのでスキップ(整数命令という言葉は問題文には出てきてないし、かかった時間の割合も当然不明)

1.14.3

分岐命令は40sだが、全体の250sの20%は50s。どうあがいても無理。

1.16

台数 実際の時間(s) 何倍速いか OHがない場合何倍速いか
2 54 1.85倍 2倍
4 29 3.45倍 4倍
8 16.5 6.06倍 8倍
16 10.25 9.76倍 16倍
32 7.125 14.04倍 32倍
64 5.5625 17.98倍 64倍
128 4.78125 20.91倍 128倍

ListViewにButtonとか入れてるけどOnItemClickListenerが動かない

Android Kotlin ListView

Androidアプリの開発で、ListViewにCheckBoxやButtonを入れて、OnItemClickListenerを設定したが働かないという問題にであいました。 結構な既出問題でしたが、日本語情報ではなかなか十全な記事がなかったです。そして、自分のFocus、TouchModeの理解などもかねてまとめることにしました。

続きを読む

ABC194 - E - Mex Min

ABC 要反省 良問 発想転換

https://atcoder.jp/contests/abc194/tasks/abc194_e

問題概要

$ mex(a, b, c\cdots) $は$ a, b, c\cdots $のうちに含まれていない、最小の0以上の整数とする。

数列$ {A _ i} $と$ M $が与えられる。すべての$ A _ i $の連続した$ M $個の部分について、それぞれmexを考える。この時、$ |A| - M + 1 $個のmexの最小値を求めよ。

制約：$ 1 \leq |A| < M < 1.5 \times 10 ^ {6}, 0 \leq A _ i \leq |A| $

考え方

  1. 連続M個のmexを調べたいので、1つだけ見て、そこから首尾だけ変更して効率よく計算でいないか？
  2. しかし、これはなかなかに厳しい。mexを馬鹿正直に計算するとどうしても$ O(|A _ i| \log M) $ぐらい最悪かかってしまう。巧妙にvectorで数の続いてる区間をもって、削除と挿入による差分更新も可能ではあるが、複数個に対応させようとすると断然厳しい実装量となる。
  3. 常套テク発想を逆転させる。 $ 0 \leq A _ I \leq |A| $を利用すると、たかだか答えの候補は$ A $通りしかないと抑えられる。そして、答えとして満たすかは小さい順番に試せばよさそう。
  4. 具体的にはこうする。$ x $が最終的なmexの最小値だとすると、すべての$ M $個連続する区間のmexは当然$ x $以上。mexが$ x $以上である条件は実は簡単に求められるので、あとは少し効率化すればAC。

考察

mex演算

Grundy数などでも使われる0以上の整数の集合に対するmex演算は、以下のようなstd::setを用いて計算できる。

std::set<int> S;//Sにmexを計算したい要素が入ってる。
int ans = 0;
while(S.count(ans) != 0){
    //Sにansが含まれていたら、ans + 1がSにまたあるかを確かめる。　なくなったら終わり。
    ans++;
}
//ansがmexとなる。

これは、Sの中の要素の最大を$ X $とすると、$ O(X \log |S|) $の計算量が最悪かかる。(Grundy数の場合は、$ X $は一般的に大きくなることが少なく、なったとしても均してみた時は大丈夫)　今回の場合、愚直にシミュレーションは不可能だ。

差分更新

では、長さ$ M $の連続列であることを利用して、常套テクの最初と最後だけを変更しての差分更新を考えてみる。しかし、先ほどのmexのアルゴリズムのままではこれは効率的には行えない。ほとんど変わってなくても、効率的に再利用が難しい。

一つの方針としては、std::setに入れるのではなく、std::vector<pair<int, int>>として、 $$ [連続の始まり, 連続の終わり] $$ の形で持つことである。例えば、$ |S| = {1, 2, 4, 5, 6, 9, 34} $なら、{{1, 2}, {4, 6}, {9}, {34}}として持ち、ここから要素を1つ削除 and 挿入は 二分探索で該当する場所を探し当てて、行うことである。

しかし、この方法では同じ要素が複数ある場合の適用に難儀してしまう。一応丁寧にやれば可能ではあると思うが、実装量は恐ろしく多い。

ここでこの方針を置いておき、別方針で探るべきだ。

答えを仮定して

別方針として考えられるのは、答えはたかだか$ |A| $通りということだ。仮に答えが$ x $だとして、それが条件を満たすようにチェックできれば、$ x $を小さい順に試しておき初めて条件を満たしたものが答えでよい。(今回の求める連続列のmexの最小値はこの単調性がある)これは$ O(|A|) $のループしか回らない。(しかし、これで行くならばループの中は限りなく$ O(1) $出なければ間に合うことは難しいだろう)

仮に答えが$ x $であるとして、それが真であるには、次の条件を満たす必要がある。

  • どの長さ$ M $の連続列でも、mexが$ x $以上。

mexが$ x - 1 $より大きいとわかっているとき、$ x $がmexの最小値の候補としてあり得るかは、すべての$ A $の中の$ x $を見て、(先頭と後尾と)お互いと、$ M $個以上だけ間を空けていたら$ x $はmexの最小値となる。(そこの$ M $個以上の連続列では確実に$ x $は含まれていないが、$ x - 1 $以下は含まれているので、そこからとればmexの最小値は明らかに$ x $)

これは、すべての$ A[] $の値ごとに、要素としてどこにあるかをメモしておけば、$ x $が小さい順に確認するときに効率的に見ることができる。 全体で計算量はたかだか$ O(|A|) $となる。

ACソースコード

C++

最後に

青天、堕つ。いざ、昇らんや。

けんちょんさんの中国剰余定理の補足

解説 中国剰余定理 けんちょん

先日のABCで中国剰余定理による連立合同式が出たことでまた冷えたのでこれをきっかけに中国剰余定理を勉強しました。

続きを読む

ABC189 - F - Sugoroku2

ABC 数学 線形代数 期待値 DP 良問 解けた

https://atcoder.jp/contests/abc189/tasks/abc189_f

概要

マス目が0からNまであるすごろくが存在していて、あなたは1からMまですべての数が等確率で出るルーレットを持っている。あなたは最初にマス0にいて、マス目Nを目指して、以下のように進む。

  • マス目$ i $にいるとき、ルーレットで$ j $が出た時にはマス目$ i + j $へ移動する。移動先の$ i + j $が$ N $を超えた場合は、ゴールしたと見なす。

そして、このすごろくにはK個の初めに戻るマス$ {A[i]} $があり、そこにたどり着いてしまうとマス0に戻されてしまう。

この時、ゴールするまでのルーレットの数の期待値はいくつでしょう？

制約：$ 1 \leq N, M \leq 10 ^ 5, 0 \leq K \leq 10, 0 < A[1] < \dots < A[N] < N $

続きを読む

ABC191 - F - GCD or MIN

ABC gcd/lcm 良問 要練習

https://atcoder.jp/contests/abc191/tasks/abc191_f

概要

黒板にN個の数字${A[i]}$が書かれている。以下の操作をN-1回行って、最後に残った数は何通りあるでしょう？

  • 2つの数字$a, b$を選び、それらを黒板から消す。代わりに、$\min(a, b)$もしくは、$\gcd(a, b)$のいずれか一方を黒板に書き込む。

制約：$1 \leq N \leq 2000, 1 \leq A[i] \leq 109$

考え方

  1. 少し考えると、残る数字は$\min({A[i]})$より小さくないといけない。(そうでなければ絶対に最後まで残せない)
  2. また、残る数字は明らかに$A[i]$の要素のうちのいくつかの$\gcd$である。(gcdかminなので)
  3. よって、$\gcd(A[i], A[j], \cdots) \leq \min(A[i])$となる$\gcd$をすべて列挙したい。
  4. 2つペアでgcd取ればすべて行けるんじゃない？->嘘です。
  5. $dp[i] := iが作れるか？$のDPをするのは時間計算量が足りない。
  6. 発想の転換をし、$x$の倍数となるもののgcdはいくつか？(これが$x$と等しければ$x$をgcdとして残せるので)を数えると、これは時間内に数えられそう->AC。

考察

まず、$\min(A[i])$より大きい値を残すのは不可能である。なぜならば、常にmin方向(gcdも数字としては小さくなる)に数が選ばれるからである。そして、操作は

  1. いくつかの要素を選んでそのgcdを取る。この時、その値たちのgcdは$\min(A[i])$以下である。
  2. 残ったすべての操作についてminを取る。

の操作で言い換えられるとわかる(残る数字ならば必ずこの手順で黒板に残せる)。

では問題は、$A[i]$からいくつかの値を選んで、作れるgcdを列挙する方法である。

試し方1(間違い)

$dp[x] := xがgcdとなれるか？$のbool値DPを行う。遷移式は、(dp[x]がtrueなら)

$$ dp[\gcd(x, A[i])] = true $$

この愚直な遷移式では、すべての$A[i]$の約数の種類を$X$として、$O(NX \log X)$ほどの計算量で押さえられる。

しかし、ここで$X$はとても大きくなりうるのだ。とても雑な$A[i]$の構成法でこれが大きくなると示せる。

A[0] = 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12
A[1] = 13 * 14 * 15 * 16 * 17 * 18
A[2] = 19 * 20 * 21 * 22 * 23 * 24
...

このように構成すると、$N$個目の要素$4197$まで掛けることとなり、これらの間でも更にかけていくことができるので $X$は明らかに膨大になり、時間内には間に合わないとわかるだろう。

試し方2(間違い)

先ほどはすべてを試そうとしたがゆえに、時間計算量が間に合わなくなった。では、すべてのありうる答えの候補は、2つペアのgcdから求められる、と考えて$O(N2)$で試せばいいのではないか？

しかしこれはgcd系の問題でよく出る間違った命題である。 反例として、以下のようなケースがある。

$$ a = 2 \times 3 = 6, b = 3 \times 5 = 15, c = 5 \times 2 = 10 \ \gcd(a, b) = 3, \gcd(b, c) = 5, \gcd(c, a) = 2, \gcd(a, b, c) = 1 $$

このような反例で、2つペアのgcdがすべてのgcdをカバーできるわけではないとわかる。 集合内の部分集合の要素によるgcdの列挙は、○○個のペアだけで～とはならないのだ。

正しいアプローチ

試し方1では、すべての約数の候補を持っていて、かつ毎回の更新でそれらをすべて見ることから計算量が爆発した。 ここで、DPの対象の入れ替え？みたいなことをしてみる。

$ dp[x] := xを約数に持つAの要素すべての\gcd $

このようにすることで、$dp[x]$の計算に関わる$A[i]$の数を大きく減らすことができる。 もともとのDP遷移の場合、共通因数をそもそも持たない多くの遷移先はgcd == 1となっていた。この無駄を省くために、$x$を因数に持つ$A[i]$のみが$dp[x]$の遷移に関わるというアルゴリズム設計をするとうまくいく。

このアプローチの計算量はどうなるのだろうか。$109$以下の1つの数で最も約数の個数が多いのは$1344=d$個であるとわかっているので、$N$個の要素についてそれぞれ約数を全部見ても、たかだか$O(Nd)$で押さえられる。そして、mapを使用することによって、最終的に$O(Nd \log \max(A[i]))$と最悪計算量を抑えられる。(約数列挙部分は$o(N \sqrt{\max(A[i])})$)

$d$の具体的な値は知らずとも、約数であるので大体$O(\sqrt{N})$だなあと見当をつけることができれば、これが間に合うとわかる。

ACソースコード

C++

最後に

40分かけたのに解けなかったのは本当に反省。GCDは2つペアで見ちゃいけない(警告)