怠惰の累積和

技術/競プロ/怪文書/虚無

Google Code Jam Qualification Round 2021

できたとこまで.身の丈.受験明け初コンテスト.リハビリにはよかった感がある.

A:Reversort

問題概要

 数列{L_n}を下の擬似コードで示されるアルゴリズムでソートする:

for i := 1 to length(L) - 1
 j := position with the minimum value in L between i and length(L), inclusive
 Reverse(L[i..j])

 

 Reverseのときにコストがj-i+1だけかかる.かかるコストの総和をT個のテストケースそれぞれについて求めよ.

解法

 上の擬似コードをお好みの言語で書き直してあげてコストを計算するとできる.O(N^2).

 

B:Moons and Umbrellas

問題概要

 文字列Sは''C,'J','?'の3文字のみで構成されている.このうち'?'の文字すべてを独立に'C'か'J'のいずれかに置き換える.最終的に完成した文字列が'CJ'を含むとXpt,'JC'を含むとYptのコストがかかる.コストのminは?

解法

 'CC'も'JJ'もコスト0なのでHardのケースでなければ'?'が連続する区間を'C'か'J'のみで埋めることでコストがminになることが分かり,これは結局Sから'?'を抜いた文字列でコストがいくらになるかを考えればよいことになる.O(|S|).Hardは多分文字列DP.この1点が無くても通過できるのでまあ良し.

 

C:Reversort Engineering

問題概要

 A:Reversortの問題について,コストがCであるような1,2,...,Nを並び替えた順列を1つ出力する問題をT個のテストケースそれぞれについて解け.

解法

 Easyの方はnext_permutationで全探索すれば解けてO(N!・N^2).この時点で予選通過は確定したのでHardは出していないがCN-1\leq C\leq {}_NC_2-1を満たせば構成可能でそうでなければ"IMPOSSIBLE"っぽいことがわかり,Reversortを行う際には順列を前から順にみていくことを考えると順列を構成する際には1,2,...,Nを後ろから見ていって構成すればO(N^2)でできそう.Hardは通してないので知らんけど.

円周率を二物体の衝突で求めるやつ

なにこれ(ここに書いてある内容は適当なので読むなら下のPDFのところを読むのをお勧めします)*1

 有名なのかそうでないのかよくわかんないんですけど物体2つを衝突させると円周率が求まりそうみたいな主張が存在することを何か(何だっけ)で知りました.しかし知ったのが高3の夏休みくらいだった(はず)ので受験勉強そっちのけでその主張を理解するのに時間を費やすのもなあみたいな気分になったのでそのときはきちんと理解しようとはしませんでした.無事(?)受験が終了したので\LaTeXの勉強がてらPDFにしてみようと思いました.なのでそういう記事です.

 

PDF

 えいっ


 

PDF作成にあたり使用したツール

・Overleaf:オンラインでTexを書くことができる.日本語使うまでが若干面倒だった.

Powerpoint:図の作成に.最初は某ソフトでやろうとしていたが試用版だったので完成した図にロゴが入りまくっていたため大人しくパワポで作ることにした.そのせいでカスみたいな図になってしまった.

*1:Q.PDFの部分は適当ではないんですか? A.いいえ

受験体験記的なやつ

 

なにこれ

 大学受験が終了しました。結果として筑波大学総合学域群理系Ⅲというところに合格を頂いたので入学手続きをしようと考えています*1(気づいちゃったんですが名称的に「理Ⅲ合格しました!」とか言っても嘘にはならないんですよね)。締め切り諸々を守れれば春から筑波大生と言うことになります。よってここでは適当に受験直前期あたりを振り返ろうかなと思います。

 尚、この記事を書いている時間は日本時間で深夜(2~3時)であり普通に眠いため、この記事は駄文・非文の宝庫になっている可能性があります(公開は人権的な時間に行われる予定です)。ご容赦ください。

 

志望校決定まで

 そもそもの話なんですが、高3の秋くらいまでは東大理Ⅰを志望していました*2理Ⅰ受験を辞めようと思ったのは近年の理情の底点が爆上がりしていることを知ったからというのが主な要因の1つです。仮に東大に入れたとして、進振りで点が足りずに自分の希望する学問を大学で学べないことを危惧しました。

 ですが欲張りなので、進振り的な何かは欲しいなと思っていました(情報系に行きたい気持ちはあるが、大学入って専攻を決めるまでに色々な事を学べる猶予があるのは個人的に大きい)。その条件に見合う大学を探した結果、進振りっぽいことをやり、文理科目どちらも学べる*3、尚且つ理系Ⅲの括りなら情報系に優先的に進むことができる*4総合選抜という入試制度が筑波大に今年から新設される(これに関しては本当に運が良かった)ことを知ったので受験しようと決めました。

 

使った参考書とか

 往々にして受験勉強が面倒だと感じる時がある(というかいつも)のでゲームをしていました。クロッシーロード。本当に無限に時間が溶ける。

play.google.com

 こんな感じで勉強に対して不真面目だったので一日平均何時間くらい勉強したとかそんなことを言ったところでその勉強に中身が伴っていないことを想像することは容易だと思います。まあそもそも最小限の労力で突破するのが理想なのでゴニョゴニョよってそんなことをここで言うのは無意味だと思ったので使っていた参考書等を紹介するにとどめようと思います。

英語

 語彙力アップには鉄壁を使いました。ただ、学校の授業で語彙を付けてからの使用開始です。基礎的な語彙が無いのに鉄壁やっても大概破滅すると思います。自分の知らなかった単語はとりあえずAnkiでDeckに加えました。Ankiは時間があるときに適当にやりました。

play.google.com

文法とかは週1で駿台の英語の授業を受けていました。講師が駿台のテキストをガン無視してオリジナルのプリント主体で授業してくださって、そのプリントの演習量がかなりあったため力が付いたと思います。

 

数学

 高校の数学科が高3になってから定期的にテストゼミを授業中に行うようになったんですが、いい感じに忘れがちなポイントとかを復習できたのではと思っています。

 自分では荻野の天空への理系数学という本をやりました。著者は接点tのあの人。

[三訂]荻野の天空への理系数学 | 荻野 暢也 |本 | 通販 | Amazon

 この本は1周全部やってから2周目は間違えたところのみやりました。尚二次曲線パートに収録されている問題が楕円の問題しかないのは永遠の謎です。

 

物理

 いつだったか忘れたんですが(高2くらいかも🦆)学校が重要問題集(以下重問)を学年で一括購入して配ったのでとりあえずは重問をやっていました。いかんせん物理は(化学もですが)大体の高校が3年生の終わりの方まで未修分野があったりするような科目なので授業に合わせて重問を進めました。また、苦手分野を中心に重要な問題に印をつけ、模試の前等にはその問題達を中心に復習していました。いわば"重要問題集の重要問題集"を作りました。高3の夏くらいになってからは標準問題精講もやっていました(まあこの頃はまだ東大志望なわけで筑波だとオーバーワークな気がしなくもないですが)。

 

化学

  本当に一番苦手な科目だったと言っても過言ではないですが苦手なりに克服に努めた気がします。理論は重問を使っていました。無機は暗記全振りみたいなところがあるので一問一答を使っていました(結構語呂が載ってて覚えやすかったです)。逆に無機以外の部分はほとんど見ませんでした。また、気体の製法は重問の最後のページに載っている一覧で覚えたりしました。有機は学校の授業の復習くらいで事足りると思ったのでそれ以上のことは特にしませんでした。

 

 国語とか地理とか共通テストでしか使わなかった科目は学校の授業の復習だけで完結させました。

 

受け(る予定だっ)た大学及び受験結果(と、有ればコメント)

(この部分だけ違う時間に書いたので文体が違うんですが直すの面倒だし眠いので直しません~)

筑波大学総合選抜理系Ⅲ(国立前期)・・・🌸

電気通信大学情報理工学域(国立後期)・・・受ける予定無し(前期の発表前にここの足切り突破通知が来たので共通テストで変な事(マークミスで0点とか)になっていないことの確認ができただけでも良かった)

早稲田大学基幹理工学部学系Ⅱ・・・✕(敗因は英語のロト6だと思っている。大問1間違えまくった。)

慶応義塾大学理工学部学門C・・・🌸(数学で積分と極限を入れ替えた)

東京理科大学理工学部情報科学科・・・🌸(数学で大問1問飛ぶレベルのミスをしたので人気学科*5であったことも相まって不合格を覚悟したが英語満点に救われたのかもしれない)

明治大学理工学部機械情報工学科・・・🌸(受験教室が受けた学校の中で体感では一番大きかったのでビビった。人が多い。)

 

受験当日とその後(前期のみ)

 ここまで書いて分量があまりないことに気がついたので受験当日の事でも書くことにします。嵩増し大作戦敢行。

 前泊せずに家から当日つくば市に行こうと計画していたので前日は21時くらいに就寝して5時くらいに起きました。健康的8時間睡眠。前述の通り不合格だった早稲田の発表は筑波を受けた翌日だったのでこのことを知ることなく筑波に臨めたのは精神衛生上よかったと思います。当日はつくばエクスプレスが受験生で溢れかえることは想像に難くなかったので体力を温存するためにも確実に座りたいなと考え、行きは少々遠回りですが秋葉原駅からの始発電車に乗りました。「つくばエクスプレスなんて大層な名前が付いているけど内装は普通の電車じゃん。もっと個別席で机付きとかを期待してた」みたいなことを考えていたらつくばに着きました。その後まあ適当に受験会場へ移動。

 

 1科目め、英語。まあ特に言うこと無し。普通に読んで普通に解きました。

 昼食。これは国立に限らずなんですが、親と事前に相談して受験会場に持っていく昼食のメニューは固定していました。こうするとメニューが決まっている謎の安心感が生じてよかったです。

 2科目め、数学。途中で問題冊子が1冊の中でⅠAⅡBパート(前半)とⅠAⅡBⅢパート(後半)に分かれていることに気がつきました。解かなければいけないのは後半なのに気づかずに前半をやっていました。センターで数ⅠAを解かなければならないのに数Ⅰを解いていたことに途中で気がついた人の気持ちが今なら分かる気がします。まあ前半パートの問題は全て後半パートの前半の問題と同じだったので安心したわけですが*6。このプチ事件もあって過去問をやってた時みたいにサクサクは進みませんでしたが限られた時間内で得点の最大化はある程度達成できたと思います。

 3科目め、理科(物化)。物理が異常に簡単でした。まあ毎年簡単目ではあるんですが。これは高得点勝負になるだろうなあと思って解いていたので自己採点時に熱力学の後半で指定文字を使わずに違う文字で解答していたことに気づいたときは背筋が凍りました*7。逆に化学は近年のレベルに比べると若干難化の傾向を感じました。まあ普通にやってればできるよねみたいな難易度の問題を落とさなければ楽々合格点な気がします。化弱にとっては運が良かったです。過去問では無機のクイズ大会が行われていたのに本番で開催されなかったのは悲しかったです。

 

 試験が終了して帰宅して休んで数日経つと某K合塾が解答速報をアップしていたので自分の解答と照らし合わせながら自分が大体何割取れているのかの見積もりを行いました。採点基準が不明(毎年部分点を結構くれると言う噂はあるが)なので全科目に対してとても厳しい見積もり*8をしました。共テの自己採点結果と合算するとここ数年の合格最低点*9は超えていそうだし、数学と化学は難化したっぽいし、易化した物理は配点低いし*10、今年から二次の比率増えたし大丈夫なのでは?の気持ちになりましたが万が一のこともあるので発表前はかなり緊張しました*11。普段努力しないくせにこういう所で人一倍緊張するの、明らかに何かが間違っている気がします。まあ受かってたので良し。

 

最後

 書くことが無いので今後の課題でも見据えますかね。直近の一番の課題は朝起きることだと思っています(本当に朝目覚ましで起きられない)*12。起きられないと大学は本当にヤバいので。程々に勉強と起床は頑張りたいと思います。

*1:追記:手続きをしました

*2:通っていた塾が某K合塾系列の東大現役進学塾とかいうところなんですよね。直前で東大で無いところに志望を変えたの申し訳ない...

*3:この条件が無ければ東工大の情報理工学院を受験していたと思います

*4:https://ac.tsukuba.ac.jp/nyushi/sougou/ikou

*5:多分

*6:大学側は何故問題が共通なのに2パートに分けたのかが不思議でなりません

*7:解答に使った文字は問題で与えられてるから本質的には合ってるし記述式だしなんとかなってくれ~と思ってたらなんとかなりました

*8:各科目あり得ないくらいに厳しく自己採点をして、得点が一番低い科目(案の定化学)を0にして考えました

*9:総合選抜という入試制度は今年からなので理工学類あたりの最低点を参照しました。まあ大差無いやろの気持ち。

*10:https://ac.tsukuba.ac.jp/nyushi/sougou/test

*11:緊張を解す為に発表直前は寝っ転がって生茶のボトルを自分で投げてキャッチしていました

*12:四則演算(5桁当たりの数字をいじくる)を3問解かないとアラームが止まらないようにしたんですが、3日くらい経ったら解き終わって二度寝ができるといういらないスキルが身に付きました

AtCoder Beginner Contest 148

 

A - Round One

問題概要

 1,2,3の中から異なる2数が与えられるので残りの1つを出力せよ。

atcoder.jp

 

解法

 6からAとBを引くとできるし、A^Bでもできる。どっちも天才解法。思いつくのには1333年くらいかかりそう(適当)。僕はif文3つ書きました。やるだけ。

atcoder.jp

 

B - Strings with the Same Length

問題概要

 文字列が2つ与えられるので先頭から交互に出力せよ。

atcoder.jp

 

解法

 for文を使えますか?僕は使えます。やるだけ。

atcoder.jp


C - Snack

問題概要

 パーティーにA人かB人どちらかが参加する。どちらの人数が来ても均等にお菓子を配り切れるような最小のお菓子の個数を求めよ。

atcoder.jp

 

解法

 LCMですか?LCMですね。ライブラリーを貼るだけ。やるだけ。

 

atcoder.jp

 

D - Brick Break

問題概要

 数列中から任意の個数の要素を取り除いて出来上がった数列が1から等差1の等差数列になるようにするとき、取り除く要素の個数の最小値を求めよ。

atcoder.jp


解法

 いわゆるスターリンソート(cfを参照)。先頭から順に見ていき、答えを求めるだけ。やるだけ。

cf)https://qiita.com/Sirloin/items/c9e5c74be3366df65bce

atcoder.jp

 

E - Double Factorial

問題概要

 整数nについて、関数f(n)n<2なら1、otherwiseならf(n)=nf(n-2)を満たすとき、f(n)の結果の数値は末尾に0が何個続くか求めよ。

atcoder.jp


解法

 10=2*5なので、f(n)=nf(n-2)=n*(n-2)*f(n-4)=...=n*(n-2)*(n-4)*(n-6)*...の中の素因数のmin( (2の個数の総和),(5の個数の総和) )で決定される。

 n*(n-2)*(n-4)*(n-6)*...のように降順に並んでいるとき、明らかに素因数としての5の個数の総和のほうが素因数としての2の個数の総和よりも少ない。よって、nまでに5が何個含まれるかどうかを調べることで答えがわかる。ただし、nが奇数の場合、n*(n-2)*(n-4)*(n-6)*...の中に素因数2は含まれないので、答えは必ず0となる。実質中学受験算数。

atcoder.jp

 

F - Playing Tag on Tree

問題概要

 高橋くんと青木くんが木の上でどちらも同じ頂点に来るまで鬼ごっこをする。高橋くんはできるだけゲームを遅く、青木くんはできるだけ早く鬼ごっこを終わらせようとするように動くとき、ゲーム終了までに青木くんが動く回数を求めよ。

atcoder.jp


解法

 両者の戦略を考慮すると、木上の頂点のうち、高橋君の初期位置からの最短距離が青木君の初期位置からの最短距離よりも短い頂点の集合のうち、最短距離が最も遠いものの最短距離が答えとなることがわかる。よって、dijkstraを2回行ってやると解ける。atcoder.jp

JOI 2019/2020 一次予選 (第3回:11月16日(土))

 はじめに

 うく。

A - X に最も近い値 (The Nearest Value)

問題概要

 L以上R以下の整数でXに最も絶対値が近いものは何か。

感想

 ループ回して解けるね。面倒だったんでループ回しました。

 

B - キャピタリゼーション (Capitalization)

問題概要

 文字列Sの"joi"をすべて"JOI"に置き換えよ。

感想

 ループ回して解けるね。面倒だったんでループ回しました。

 

C - 最長昇順連続部分列 (Longest Ascending Contiguous Subsequence)

問題概要

 整数列Aの最長昇順連続部分列の長さを求めよ。

感想

 ループ回して解けるね。面倒だったんでループ回しました。

第8回日本情報オリンピック 予選 E - シャッフル

問題概要

 1からnまでの番号が書かれたカードがこの順に重なって並んでいる。シャッフルをするクエリが与えられるから、全てのクエリを消化した後のカードの束のp枚目からq枚目の内に含まれている書かれている番号がr以下のカードの枚数を求める。

atcoder.jp

 

解法

 nの最大値が10^9なので愚直に配列として持ってシャッフルしていくことはできない。ここでmの最大値が5000ということに注目すると、カードの情報を[1,n]の様に区間として持っておくことによって(先ほどの例は初期状態の1からnがこの順に並んでいる状態)、クエリを全消化しても区間の数はそこまで大きくならないことが分かる(例えば、n=9でシャッフル(2,4)を実行すると、([5,9][3,4][1,2])の様になる)。

 あとは更新の処理で添え字をバグらせたりしないと解ける。

 以上を実装して、AC。O(m^2)。

atcoder.jp

AtCoder Beginner Contest 144 D - Water Bottle

問題概要

 底面がa(cm)の正方形で高さがb(cm)の直方体の容器があり、x(cm^3)の水が入っている。底面の一辺を固定したまま徐々に容器を傾けていく時、何度傾けた時までなら水が零れないか。

atcoder.jp

 

解法

 求める角度をθとする。

 θだけ傾けた時、容器に入っている水の構成する形は三角柱か底面が台形の四角柱になることが分かる。以下この2パターンについてそれぞれ見て行く。

 

 ⅰ)三角柱

 θだけ傾けた時、容器及び水は下図のような状態にある。

f:id:severrabaen:20191101102121j:plain

 θは水面が地面と平行であるから、錯角の関係にある上図の赤色の角度もθとなる。三角柱の底面(図の斜線部)は現状長さbの辺が存在することしかわかっていない。だが、上図のxの長さが判明すると、逆正接(arctan)を応用することにより、θが求まる。C++だとatan2という関数にx,bの長さを与えることで求めることができる。

cpprefjp.github.io

 よって、xの長さを求めることができれば勝ちだが、これは中学受験並みの知識で求めることができる。水はx(cm^3)入っていて、三角柱としての高さはa(cm)であるから、底面積を求めることが容易である(\frac{x}{a}で求まる)。

 底辺α、高さβの三角形の面積は\frac{1}{2}αβで求まるから、これを適切に使用して逆算するとxの長さが求まる。

 ここで、もしx>aであるならば底面は三角形になりえないので、底面は台形、水の形は四角柱だと分かる。そうでないなら先ほどのatan2xbを与え、θを得る。ラジアン表示で返ってくるので適切に度数法に変換してやる必要がある(rad*180/pi=deg)。

 

 ⅱ)四角柱

 θだけ傾けた時、容器及び水は下図のような状態にある。

f:id:severrabaen:20191101103821j:plain

 三角柱の時と同様にやると、赤色の部分がθだと分かるから、atan2ab-xの長さを与えて適切に度数法に変換すれば答えとなる(台形から2辺の長さがaxの長方形を取り去った三角形を考える)。

 底面の台形の面積は先ほどと同様に\frac{x}{a}で求まり、上底α、下底β、高さγの台形の面積は\frac{α+β}{2}γで求まるから、適切に処理することによって、xが求まる。

 よって、atan2ab-xを与えてθラジアン表示で得る。度数法に変換して答え。

 

 上記を実装して、AC。

atcoder.jp