season's quarterly

数学/物理/プログラミング

AtCoder に登録したら解くべき精選過去問 10 問を Common Lisp で解いてみた

始めに

数日前に唐突にLISPに入門したのでやってみました。 qiita.com

参考資料

Common Lisp

AtCoderCommon Lispで解いた人の記事

第1問 ABC 086 A - Product

A - Product
提出

(defun solve (a b)
    (if (= (mod (* a b) 2) 0) "Even" "Odd")
)
(format t "~A~%" (solve (read) (read)))

入力は(read), (read-char), (read-line)を使う。それぞれ整数、文字、文字列を読み込む。出力にはprincformatがある。
関数の定義にはdefunを使う。関数は前置記法つまり(関数名 引数1 引数2 ...)で書く。 余りにはmod, 'rem'がある。違いは負の数の扱い。

第2問 ABC 081 A - Placing Marbles

A - Placing Marbles
提出

(defun solve (a b c)
    (+ (if (equal a #\1) 1 0) (if (equal b #\1) 1 0) (if (equal c #\1) 1 0))
)
(princ (solve (read-char) (read-char) (read-char)))

文字や文字列の比較にはchar=, string=, equalがある。

第3問 ABC 081 B - Shift Only

B - Shift only
提出

(defun two_count (a)
    (if (= (mod a 2) 1) 0 (+ (two_count (/ a 2)) 1))
)
(defun solve (n)
    (if (> n 0) (min (two_count (read)) (solve (- n 1))) 30)
)
(princ (solve (read)))

LISPは動的型付けなので/だと有理数になることに注意。切り捨てにはfloor, truncateを使用する。違いは負の数の扱い。

第4問 ABC 087 B - Coins

B - Coins
提出

(defun solve (a b c x)
    (if (> a 0)
        (+ (solve (- a 1) b c x) (solve 0 b c (- x (* 500 a))))
        (if (> b 0)
            (+ (solve a (- b 1) c x) (solve a 0 c (- x (* 100 b))))
            (if (> c 0)
                (+ (solve a b (- c 1) x) (solve a b 0 (- x (* 50 c))))
                (if (= x 0) 1 0)
            )
        )
    )
)
(princ (solve (read) (read) (read) (read)))

第5問 ABC 083 B - Some Sums

B - Some Sums
提出

(defun digit_sum (n)
    (if (> n 0) (+ (digit_sum (floor n 10)) (mod n 10)) 0)
)
(defun solve (n a b)
    (let ((x (digit_sum n)))
        (if (> n 0) (+ (solve (- n 1) a b) (if (and (<= a x) (<= x b)) n 0)) 0)
    )
)
(princ (solve (read) (read) (read)))

変数にはletを使う。

第6問 ABC 088 B - Card Game for Two

B - Card Game for Two
提出

(defun solve (n a)
    (if (equal a nil)
        0
        (if (= n 0)
            (+ (solve 1 (cdr a)) (car a))
            (- (solve 0 (cdr a)) (car a))
        )
    )
)
(defun init (n)
    (if (> n 0) (append (init (- n 1)) (list (read))) (list))
)
(let ((a (init (read)) ))
    (princ (solve 0 (sort a #'>)))
)

listでリストを作ることができる。carで先頭の要素を取得し、cdrで以降の要素を取得する。sortで比較関数を指定してソートする。
ちなみにlengthで長さが取得できるが、線形時間なので注意。空リストかどうかを判定したいときは(equal l nil)(null l)を使う。

第7問 ABC 085 B - Kagami Mochi

B - Kagami Mochi
提出

(defun solve (s a)
    (if (equal a nil)
        1
        (+ (solve (car a) (cdr a)) (if (< s (car a)) 1 0))
    )
)
(defun init (n)
    (if (> n 0) (append (init (- n 1)) (list (read))) (list))
)
(let ((a (sort (init (read)) #'<)))
    (princ (solve (car a) (cdr a)))
)

append, consでリストを結合する。
https://www.nak.ics.keio.ac.jp/class/lisp/union.pdf

第8問 ABC 085 C - Otoshidama

C - Otoshidama
提出

(defun select (l1 l2)
    (if (> (car l1) (car l2)) l1 l2)
)
(let ((n (read)) (y (read)))
    (defun solve1 (a b)
        (let ((c (- n (+ a b))))
            (if (and (>= c 0) (= (+ (* 10000 a) (+ (* 5000 b) (* 1000 c))) y))
                (list a b c)
                (if (> a 0) (select (solve1 (- a 1) b) (solve2 a b)) (solve2 a b))
            )
        )
    )
    (defun solve2 (a b)
        (let ((c (- n (+ a b))))
            (if (and (>= c 0) (= (+ (* 10000 a) (+ (* 5000 b) (* 1000 c))) y))
                (list a b c)
                (if (> b 0) (solve2 a (- b 1)) (list -1 -1 -1))
            )
        )
    )
    (format t "~{~A~^ ~}" (solve1 n n))
)

第9問 ABC 049 C - Daydream

C - Daydream
提出

(defun solve (s)
    (let ((n (length s)))
    (cond
        ((and (>= n 5) (equal (subseq s (- n 5) n) "dream")) (solve (subseq s 0 (- n 5))))
        ((and (>= n 7) (equal (subseq s (- n 7) n) "dreamer")) (solve (subseq s 0 (- n 7))))
        ((and (>= n 5) (equal (subseq s (- n 5) n) "erase")) (solve (subseq s 0 (- n 5))))
        ((and (>= n 6) (equal (subseq s (- n 6) n) "eraser")) (solve (subseq s 0 (- n 6))))
        ((= n 0) "YES")
        (t "NO")
    )
    )
)
(princ (solve (read-line)))

第10問 ABC 086 C - Traveling

C - Traveling
提出

(defun calc (b)
    (let ((ti (car b)) (x (car (cdr b))) (y (car (cdr (cdr b)))))
        (if 
            (and
                (= (mod ti 2) (mod (+ (abs x) (abs y)) 2))
                (>= ti (+ (abs x) (abs y)))
            )
        0 1)
    )
)
(defun solve (a)
    (if (= (loop for l in a sum (calc l)) 0) "Yes" "No")
)
(defun init (n)
    (loop for i below n collect (list (read) (read) (read)))
)
(defun delta (a)
    (loop for b on a collect 
        (if (null (cdr b))
            (car b)
            (diff (car b) (car (cdr b)))
        )
    )
)
(defun diff (s1 s2)
    (list
        (- (car s1) (car s2))
        (- (car (cdr s1)) (car (cdr s2)))
        (- (car (cdr (cdr s1))) (car (cdr (cdr s2))))
    )
)
(princ (solve (delta (reverse (init (read))))))

105オーダーで再帰するとスタックオーバーフローするのでループを用いる。ループにはloopを使う。返り値にはcollectsumなどがある。
【Common Lisp】loopマクロの使い方まとめ - プログラミング原人の進化論

最後に

間違いなどありましたら指摘していただけるとありがたいです。

高校時代にやったこと

1年(2018/04-2019/03)

4月

高校に入学する。一番最初の学力調査みたいなやつで学年一位だったのを覚えてる。
最初は帰宅部。なんかパソコン部は興味あったんだけど、中学の時みたいに休日出勤あったら辛いなあとか思ってた。実際は文化部はゆるゆるだった。
図書館が広くて、大学の数学と物理の本が揃ってた。蔵書数は15000冊とからしい。

7月

友達に誘われてクイ研に入ったのが多分この頃。高校の夏季講習みたいなやつに強制参加させられたので高校生クイズは参加しなかった。

8月

解析力学の本を借りて読んでた。
解析力学 (物理入門コース 2) | 小出 昭一郎 |本 | 通販 | Amazon
夏休みの最後当たりに数学・物理のアカウントを作りました。


2019年の終わりまでは基本的に数学オリンピックの問題を解いて解答を載せるだけのアカウントだった。

10月

人生で初めて折り紙を設計した。これめっちゃ楽しい。


設計理論とか全然知らないんだけど、立体を平面に広げたときの余白をどう折れば良いか考えていろいろ試行錯誤してたらできた。

11月

情報の授業の前に先生にパソコン部に誘われた。当時の部長がpublic_yusuke氏だった。タイピングめっちゃ早かったり、数学基礎論の本持ってたり、理数科の課題研究見せてもらったりしたけど色々やばかった。この人に競プロを教えてもらって、その場でAtCoderのアカウント作って、D - Five, Five Everywhereを解かされた。Twitter教えたときめっちゃ「キモい」って言われた。その場でパソコン部に入ることになって、一か月後の情報オリンピック予選に出ることも決まった。
これがなかったらPCKもJOIもSuperConも出てなかったし、情報科学の達人に参加することもなかった。自分の人生がかなり劇的に変わったのはずなので感慨深い。

12月

JOI予選に参加して予選落ちします。過去問では300点取れてたのに本番では140点しか取れなくて悔しかった。

1月

数オリの予選に通った。

2月

2年(2019/04-2020/03)

5月

電磁気学のpdfを書いた。物理学のpdfは大体EMANの物理学と専門書を読んで書いてる。他にもpdf書いてるけど、別に検証とかされてないし勝手な解釈もあるので、内容の正しさは保証できないです。あと図を入れるべきところを面倒臭がって入れてなかったりする。ちなみに日付は手動のままなので更新されてない。
復刻版 バークレー物理学コース 電磁気 (バークレー物理学コース 復刻版 2) | 飯田 修一, 飯田 修一 |本 | 通販 | Amazon
Electromagnetism.pdf - Google ドライブ

6月

競プロのアカウントを作ります。

7月

高校生クイズに出た。


相対性理論やる前に微分幾何やらないとなあと思って学校の図書館で本借りた。
Differential Geometry.pdf - Google ドライブ

9月

public_yusuke氏とPCK出たら予選通過してしまった。
season1618.hatenablog.jp

10月

電気回路とか制御工学(古典制御)を多少齧ってた。「サイバネティクス」を借りた。

11月

PCK本選は同年代の競プロerと知り合うきっかけになったのでとても良かった。旅費が1万円を超過する場合にはその超過分を会津大学が払ってくれるし、その一万円は学校が払ってくれたので、会津旅行にただで行けて最高でした。顧問がステーキ奢ってくれたのと、夜中に皆でコンテスト出たのが楽しかった。
season1618.hatenablog.jp

12月

JOI予選通過した。
season1618.hatenablog.jp
この記事を読んで言オリ面白いなって思ったので出た。なお勉強は全くしていない。
zohe.hatenablog.com

1月

この年の数オリは予選落ちした。
season1618.hatenablog.jp

2月

一瞬だけ関数解析の本読んでた。綺麗に忘れたけど。


JOI本選も何人かと名刺交換した。PCKに比べて全体的に質素だった。部屋が独房って呼ばれてるし。
season1618.hatenablog.jp
熱・統計力学の勉強してた。
熱・統計力学 (物理入門コース 7) | 戸田 盛和 |本 | 通販 | Amazon
VSCodeが使えるようになったので、Webブラウザのようなものを作ろうとしてた。
弊学は数学の授業中に折り紙折ってても何も言われません。

3月

コロナでN予備校が教材出してたので機械学習のやつだけやった。実装はしてない。


コロナの影響で数学甲子園の中止が発表されて悲しかった。
この本が結構面白かった。生物の本だけど情報の話も出てきた。オートマトンとか正規表現の話に初めて触れたんだけど結構深いんだなあと思った。
生命の物理 (新装版 現代物理学の基礎 第8巻) | 大沢 文夫, 寺本 英, 斎藤 信彦, 西尾 英之助 |本 | 通販 | Amazon

情報科学の達人」プログラム受講生に採択されてしまった。
JOI本選erから一定数採るということだったので、自分のとこにも宣伝が来ていて応募したんだけど、まさか選ばれるとは思ってなかった。内容としてはこんな感じ。第一段階では、色んな分野の先生からオンライン講義を受講しつつ、グループ分けされてメンターの先生から出された課題をこなす。第二段階では研究をしたりする。グループは再編成された。
休校になったのでこの頃から競プロの精進を始めた。

3年(2020/04-2021/03)

4月

文化祭のゲーム作ろうと思っててUnityを触ってた。結局文化祭中止になったけど。達人の講義動画を見るようになった。この時はアニメとかいっぱい見てた。

5月

波動光学とか色彩に興味を持ってた。


AtCoder青になりました。
season1618.hatenablog.jp
PAST中級だった。悲しい。

6月

適当に後輩を誘ってSuperCon予選に参加して予選通過しました。予選通過したと同時に本選の中止が発表されました。
season1618.hatenablog.jp
物理チャレンジの実験課題をやりました。

7月

なんかJavaの逆アセンブラ作ってる。


JPhO理論問題コンテストに出た(一次予選落ち)。今年はオンラインだった。

8月

達人の課題でAmoebaSATのパラメータを調整して高速化するというのをやってた。AmoebaSATというのは、粘菌の動きを模倣したアルゴリズムでSATを解くやつ。粘菌を使って首都圏の交通網をシミュレーションする研究を知ってる人も多いかもしれない。
粘菌コンピュータ - Wikipedia
粘菌から着想した解探索コンピュータ | 理化学研究所
まあ大したことはできなかったなあ。
量子力学をやらんとなーと思って本読んでた。あんまり深入りできなかったけど。
量子力学 I 原子と量子 (物理入門コース 5) | 中嶋 貞雄 |本 | 通販 | Amazon
量子力学 II 基本法則と応用 (物理入門コース 6 ) | 中嶋 貞雄 |本 | 通販 | Amazon
例年APIOはJOI本選通過者が参加できるんですけど、この年はコロナの影響で、本選erで参加を希望した者のうち本選成績上位60名が参加できることになりました。
season1618.hatenablog.jp
ニュース博識甲子園に出た。本来は二週間前にやるはずだったんだけど、ネットのトラブルでほとんどの参加者が参加できない事態になってやり直しになった。


数学検定一級を受検したんだけど一次しか合格できなかった。

9月

適当に後輩を誘ってPCK予選に出て予選通過しました。
season1618.hatenablog.jp
筑波AC入試の出願をした。
本選が中止になったSuperCon本選ですが、代わりにスーパーコンピュータの富岳を使わせてもらえることになりました。SuperConを主催してるのは東工大と阪大で、富岳持ってるのは理研だったから、そんなことできるんだーとか思ってた。


この時期は特に忙しかった。

10月

高校生クイズに出た。


JChOに出た(一次予選落ち)。
学校で「色彩学概説」を借りて絵具とかメディアについて調べてた。
色彩学概説 | 千々岩 英彰 |本 | 通販 | Amazon

網羅的じゃないけどpdfも書いた。
Visual Art.pdf - Google ドライブ

11月

志望校を東工大に変えるなどした。
PCK本選は今回は学校からだった。いやー会津行きたかったなー。
season1618.hatenablog.jp

12月

情報科学の達人の第二段階がこのあたりに始まって、週一の進捗報告会も始まった。第二段階ではStochastic ComputingでReservoir Computingを実装する取り組みをやってた。


まあ大したことはできなかったなあ。
冬休みはずっと共通テストの勉強をしてた。

1月

共通テスト
season1618.hatenablog.jp

2月

個別試験
season1618.hatenablog.jp
これは受験の反動。

3月

東工大受かった。

大学受験記(個別試験)

season1618.hatenablog.jp

前置き

イキリ受験記です。生存バイアスです。

志望校

昔から大学では理学をやるんだろうなって思ってたんですけど、数学や物理の本は高校でだいぶ読んだし、高校に入ってからは情報系との縁に恵まれるところが多かったし、結構興味も出てきたので夏休みくらいから情報系に志望変更しました。お金がないので国立が良かったです。ある程度上位になるとあんまり違いはないと思っていたので、競プロが盛んな東大京東工大筑波大のどれがが良いなあと思いました。阪大は積分サークルのノリが苦手だった(偏見)。文系は好きでも得意でもなかったので、東大と京大はやめました。東工大は後期が無かったので後期は筑波大に決まりました。第一志望は最初東工大だったんですけど、筑波では他学群の授業が受けられると聞いて筑波に変更して、東工大では他学院の授業が受けられると聞いて東工大に変更しました。11月のことです。ちなみにこれは東工大の先生に直接聞きました。達人erはメンターの先生に大学のことを聞くのもありだと思います。オープンキャンパス(オフライン)も行ってないし、冠模試は既に終わってました。
というわけで前期を東工大、後期を筑波にしました。筑波の後期は情報科学類がないので理工学群です。私大は記念受験的な意味合いが強かったのでまともに調べませんでした(カス)。せっかくの受験なので有名所は押さえておきたいと思って早稲田と慶應理科大に出願しました。ちなみに共通テストですが、私大は独自試験のみで使用せず、国立は両方とも足切りがなかったので、完全に塗り絵でした。
試験日程ですが、第n+1志望の入学金振り込み期限が過ぎる前に第n志望の合否発表があると嬉しいです。国立志望の場合、そんな気の利いた私大はないのですが。僕は最初の合否発表が遅くて、前期の三日前までどこも受かってない状態だったのであまり精神的によろしくなかったです。

勉強

参考書は完全におさがりです。理科大慶應の赤本は兄、東工大と筑波の赤本は先輩からのものです。お金をあまり使いたくなかったので塾も行きませんでした。模試の判定はずっとC以下で、直近の東進模試でも東工大D、早慶E判定だったけど結局全部受かりました。なんか過去問を見る限り普通に受かるよなあと思いつつ、模試の判定では一貫してD,Eとかだったのでおかしいなあと思っていました。まあだから判定とかじゃなくて問題が解けるかどうかを見た方が良いんだと思います。大体どこの大学でも6割取れれば合格できるっぽいです。とはいえ理科大以外はあんまり自信なかった。

筑波大学情報学群情報科学類AC

ACというのはアドミッションセンター入試(AOみたいなやつ)で、ACしたわけではないです。賞状(数オリ、情オリ、PCK、SuperCon)、pdf(電磁気学微分幾何相対性理論)とかを送ったんですけど、書類選考で落ちました。自己推薦書と志願理由書が適当だったかもしれないし、実績が足りなかったかもしれないです。
俺「†情報科学の達人†と申しますw」
情報科学類「書類落ちですw」


俺を落としたこと、後悔させてやるぜ。

東京理科大学理工学部物理学科

理科大って同じ物理学科でも理学部とか理工学部とかあるんですけど、そういうのはちゃんと調べましょう。僕は適当に選びました。共通テスト終わってから赤本を開きました。10年前の赤本です。理科は物理と化学のどちらか一方だったので物理を選択した。
自信はありました。
f:id:season1618:20210222165007p:plain

慶應義塾大学理工学部学門A

本番二週間前から過去問をやり始めました。10年前の赤本です。
ちなみにスマホに頼らず電車に乗るぞと思って15分くらい路線図を睨んでたけど、結局何も分かりませんでした。悲しい。
感触は微妙でした。数学は終了20分前くらいから見直してたのでほぼ満点取れた自信があるけど、化学は3割くらいしか取れてないと思います。半分空欄だったので。
f:id:season1618:20210222165153p:plain

早稲田大学先進理工学部物理学科

QuizKnockの山本氏と同じところですね。学科は応用物理なので違うけど(応用物理は第二志望だった)。先進理工という響きがかっこよくて出願しました(カス)。よく調べると基幹理工の方が良かったかもなあという気持ちにもなってくる。早稲田は赤本持ってないので直前に一年分やっただけです。有名大学はネットに過去問載ってるから良いよね。数学は全部記述なんですよね。解答用紙配られたときに知りました。英語は慶應より難しい印象を受けたのですが、後半の方に英語というよりも英語で算数の問題を解くような大問があったので、本番でもそれから先にやりました(←素晴らしい学習能力)。結局英語できないままなんですけど、できないなりに矛先を見つけて戦えたかなあという気がします。当日は強風で電車が遅延したので試験時間が繰り下がって、試験後も遅延してたので帰宅したのが翌日でした。
自信はありませんでした。
f:id:season1618:20210226191425p:plain
この時点でまだどこも受かってないのでとにかく東工大の勉強を死に物狂いでする必要があります。

東京工業大学情報理工学院

10日前に赤本を開いたときは馬鹿なんじゃないかと思いました。この赤本はpublic_yusukeに譲っていただきました。かなり助かったので大変感謝しています。この赤本は問題を年度ごとではなく分野別に分けていて、難易度も付与されていたので、こちらの方が合っている受験生もいるのではないかと思います。
f:id:season1618:20210309180540j:plain
本番まであまり時間がなかったので、化学は物質の構造、有機化学、高分子化合物に絞って勉強しました。英語と物理は4問くらいやった気がする。数学は6割くらい解きました。ちなみに数学は去年と一昨年の分を授業中に解いていた。それから前年の物理と化学をやりました(これもネットに載ってた)。このころは一日10時間くらい勉強してた気がする。
解答用紙に名前を書く欄がなくて、受験番号(とその下二桁)を書くだけでした。なんで?大岡山キャンパスだったので二日目帰るときにチーズケーキだけ撮ってきた。f:id:season1618:20210309213016j:plainf:id:season1618:20210309213020j:plain
体感が

  • 数学180/300
  • 英語70/150
  • 物理120/150
  • 化学80/150
  • 合計450/750

だったので手応えは微妙でした。


[ここに開示が入る]

感想

筑波に落ちた以外は全て望み通りの結果だった。4年間社会から放っておいてもらえる権利を得ることができました。いっぱい勉強します。

大学受験記(共通テスト)

season1618.hatenablog.jp

全体の感想

2020年って結構やばくて、受験を差し引いても高校三年間で一番忙しかった気がする。具体的には、JPhO予選(一次予選落ち)出たり、
SuperCon予選に参加したり、コロナの影響でJOI本選落ちでもAPIOに参加できるようになったり、
PCK予選出て、SuperCon予選通過したけどコロナで本選が立ち消えになった代わりに富岳使えることになったり、JChO予選(一次予選落ち)に出たり、PCK予選通ったので今度は
本選出たりしてました。あと夏休みにSATの研究始めたり、11月から毎週進捗会に参加したりと、本当にわけが分かりません。共通テストの前日も進捗会に参加してたのはイカれてたと思う。本格的に受験勉強を開始したのは9月の下旬くらいだったと思います。
時間とお金の無駄だと思っていたため塾には行きませんでした。金銭に余裕がある方ではないのでね。あと参考書も買うつもりはなかったんですが、親が勝手にZ会の共通テスト攻略演習というのを注文していました(12か月分3万円)。国語と英語と地理はこの問題集を使いました。
競プロは8月に休止したけど、アニメはずっと見てたしTwitterもやめなかった。

9月

ここで9月の進研模試の結果を見てみましょう。

  • 国語98(現80 + 古18)
  • 英語96(R61 + L35)
  • 数学187(IA87 + IIB100)
  • 物理100
  • 化学63
  • 地理52


...
当時の自分の実力をまとめるとこんな感じだと思います。

  • 国語:現代文は運、rand(60, 90)。古文漢文はカス。
  • 英語:Rは最後まで文章が読み終わらない。語彙力が壊滅的。Lはカス。
  • 数学:まあできる。
  • 物理:まあできる。
  • 化学:計算問題はできる。無機有機はカス。
  • 地理:常識がない(「ロシアは社会主義」「スイスは経済的に少し貧困だよね~」)。

というわけでこの時期から頑張って勉強します。

10月

英語Rはそれまで本文を全部読んでから設問を読んでいました。WPMを改善する方向の努力はあんまり効果が無かったので、立ち回りを工夫することにします。設問を読みつつ本文を読んでいくと意外と最後まで読み切れました。それからコミュ英の授業が教科書の読解から私大過去問の演習に変わりました。貰ったテキストに載っていた英単語がレベル別に分かれていたのが単語を覚えるモチベーションになったと思います。これで20点上がります。
英語Lは中学からほとんど勉強したことがありませんでした(CDプレイヤーを持ってなかったのでしょうがない)。ちなみにYouTubeで英語聴いてもまともに上達しませんでした。初心者がやっても効果ないかもしれん。今回はウェブ音声が入手できたのでやっと勉強します。サンプル問題を一回分復習するとなぜか平均に到達しました。これで30点上がります。
単語を覚えるにあたってそもそもどの単語を覚えれば良いか分からなかったりしたので、よく出てくる評論のテーマで調べてました。WikipediaYouTubeでglobal warming, climate change, air polution, earthquake, volcano, extinction, civilization, hierachy, social class, solar system, self-driving carなどで検索してみると多少対策になります。volcanoの記事を読んでいて、「eruptってなんだっけ...噴火か(n回目)」みたいな。文章の中で同じ単語が何度も出てくるので覚えやすいと思う。
無機化学有機化学の勉強をします。20点上がります。

11月

11月のマーク模試の結果です。

  • 国語122(現68 + 古54)
  • 英語153(R86 + L67)
  • 数学177(IA92 + IIB85)
  • 物理87
  • 化学81
  • 地理50

古典が上がってるのは、現代文を急いで読んで古典をしっかり読んだら意外と内容が取れたからだと思う。
古典の授業が演習になりました。古文単語を少し覚えます。あと基本的に恋と仏教と自然を愛でるくらいしかしないので単語の意味を決め打ちできるのかなあと思ったりしました。漢文は親しみのない意味でも結構熟語で使われてるんだなって気付いた。例えば、

  • 少:若い→少年
  • 経:営む→経営
  • 済:救う→救済

ちなみに「経」と「済」は経世済民で覚えれば良いと思います。こういうのは漢字一字で検索すると少 | 漢字一字 | 漢字ペディアとかが出てくるので、熟語と合わせて馴染みのない意味が見つかったりする。ばらつきが酷いけど古典で50点ほど取れるようになってたと思う。

12月

地理で山脈の位置とか覚え始める(は?)。あと地誌と各国の経済成長とか。一番意外だったのはイスラエルが先進国だったことです。10点上がります。
本番までの足掻き

1月

国名と位置を覚えます(は?)。地誌は民族・言語・宗教、移民難民、紛争の内容とかを調べた。半導体って精密機械じゃないらしいです(時計とか)。
青パックやりました。

本番

本番前日にごちうさの最終話をもう一周しました。「チノおねえちゃん...」で萌え尽きた。
規則正しい生活習慣を送りましょう。


本番で最も重要なのは、受験票を持っていくこと、電車を乗り間違えないこと、名前と受験番号を書くこと、選択問題を間違えないこと、マークをずらさないことです。これが本質だと言っても過言ではない。
本番に自己最高点、受験生の鑑では。でも満点は取れませんでした。英語Rが何故か8割いってた。嬉しい。現代文で運が良くて94点だったの嬉しい。
ありがとう...

PCK2020本選参加記[EngelBæts!]

11/14に開催されたパソコン甲子園2020本選に参加しました。
予選参加記はこちらです。
season1618.hatenablog.jp

本選当日


今回はオンライン開催ということで、本選競技中の選手の写真を撮ることになっていたのですが、開始30分程で撮ることになっていました。

問題1 ケーキの価格

差が税率2%分かつpは50の倍数なので50で割る。

問題2 角度の変換

3600で割ったり、3600で割ったものに3600をかけて引いて60で割ったり、60で割った余りを取ったりするとできます。

問題3 ホットケーキ

焼く回数に差ができないように焼くと最小の回数にできる。例えばホットケーキA,B,C,D,Eがあったとする。一回目にA,B,Cを焼いて、二回目はまだ焼いていないD,Eを優先してD,E,Aを焼く、三回目はまだ一回しか焼かれていないB,C,D,Eを優先してB,C,Dを焼くというようにする。よって\lceil 2N/3 \rceilを出力すれば良い。ただしN = 1の時だけ2。これを忘れて1ペナ。

問題4 最小のMAW

辞書順最小であるためにはS中の最も小さい文字だけを使うことが必要。この文字をcとする。Tの長さをS中のcの最大の連続する個数より1多くすれば、その他の条件も満たすことができる。

問題5 スロットマシン

列ごとに0-9の個数を数えて、掛けて足せば良い。
ここまでで34分。去年は競技時間いっぱいかけて5問正解だったのでかなり余裕です。この時点では11位だったらしい。まあ高難度解けないとだめだよね。

問題6 はんぶんこ

尺取りでやるんだろうなあとか思いつつ実装しきれる自信がなかったので飛ばします。

問題7 旅館の客室番号

8進数にして引き算して10進数に直せば良い。100桁なので多倍長整数で足し算(引き算)と掛け算の筆算を実装するのが大変だった。が、どうしても通らないので15:30頃に問題6に戻る。

椅子を温める

実装ができたので提出するが通らない。6も7も解法は分かってるのに通らないのできつかった。何も分からないので問題7で愚直解法と比較してみたが違う答えが出てこない。16:20頃にとりあえず怪しいところを変更して提出するとAC。草。問題8に移る気にはならなかったので、問題6のコードのデバッグに取り掛かる。面積の式が間違ってたので喜々として提出するけどWA。結局原因が掴めないまま競技終了。

結果

まあ去年より解けたから良いんではないでしょうか。
f:id:season1618:20201114201029p:plain
f:id:season1618:20201114201017p:plain


全体の解答状況
f:id:season1618:20201114201021p:plain
やはり問題6の正答率が悪いですね。正答数、正答率共に問題8と逆転してるので、問題8をもっと考えれば良かったかも。

感想

ライブラリは今回も使いませんでした。今回は後輩が3問も通してて凄かった。

PCK2020予選参加記[EngelBæts!]

9/12に開催されたPCK2020予選に参加しました。
本選はこちらです。
season1618.hatenablog.jp
PCK2019の参加記はこちらです。
season1618.hatenablog.jp
season1618.hatenablog.jp

チーム

チーム名は「EngelBæts!」です。世の中には「Angel Beats!」「Angel係数」「Engel係数」という言葉があるのですが、「Engel Beats!」だけなかったのではい。10文字制限なのでスペースを排除してeaを発音記号でごまかしました。相方は競プロ未経験の一年生です。

練習

当日の一週間前から軽く練習を始めました。3年なので部活は休止してましたが、電車が来るまでの40分ほどでAOJ PCKの虚無埋めをしてました。前日は家で2018年の予選の難しい問題を解きました。9完できたので去年より成長したなあという感じです。

予選当日


去年は問題をよく読まなかったりサンプルを確認せずに提出してペナルティを重ねたので、今年はサンプルを全部確認してから提出するようにした。

問題1 緯度経度

La/3600,Lo/3600をそれぞれ出力。LatitudeとLongitudeというらしい。

問題2 商店街へのお出かけ

ヤエちゃんが辿り着けるとき(s \leqq m)1足して、タケコちゃんが辿り着けるとき(w - s \leqq m)2を足せば良い。

問題3 あいさつまわり

左端の座標をx、右端の座標をy、モチヒト君の現在地をmとすれば、min(m - x, y - m) + y - xが答え。

問題4 カラフル円盤通し

配列をreverse。初期値を0としてそれまでの最大値より真に大きければインクリメント。

問題5 写真の回転

写真を回転させる関数を作った。あとは回転数を数えて(1なら+1、-1なら+3)4で割った余りの数だけ適用させる。

この辺はよく覚えてないけど30分で5完したらしい。

問題6 テトラへドロン

color[i][j] = color[i-4][j-2]なので8通りだけ考えれば良いんだけど頭壊れるやつ。結局12パターン全部書き出した。これが一発で通ったのはかなり精神的に良かった。

問題7 加工機

最初素直に配列使ってやったらREになったので制約を見るとW, D \leqq 10^5だった。C \leqq 10^5なので削る区画を管理して、四方を見てどれだけ表面積が増えるか判断。区画が端にあるかどうかで場合分け。思ったより時間かからなかった。

問題8 高速道路網

最初dfsでやってTLEしたのでbfsでやった。トポロジカルソートのライブラリを印刷していなかったので、bfsでやるかーって実装したけど結局トポソになってた(は?)。ある頂点に辿り着いた時点での経路数C_iと経路長L_iをもっておけば、辺の終点でそれぞれ\Sigma C_i, \Sigma C_i + L_iと更新できる。WAになったので最大ケース(と思われる)を確認するとlongにすれば良いことが分かったのでそうする。


最初デバッグ出力を消し忘れていて、もう一度提出したんだけどジャッジが詰まってたので結果が分かったのは競技終了後だった。ここでWAだったらかなり悔しい思いをしていたので良かった。
問題9以降は見てない。

結果

f:id:season1618:20200916150211p:plainf:id:season1618:20200916150236p:plain


全体の解答状況
f:id:season1618:20200916150138p:plain
3と7の正答率が低いなあという印象。
実力枠じゃなかったのでちょっと不安だったけど、無事通っていたので嬉しい。ただで会津旅行行けないのは残念だけど。

感想

去年の教訓を活かすことができたので良かった。実際去年が7完6ペナだったので成績は良くなった。あと結局自分が全部ACしたけど、後輩も自分の後に通してて凄いなあと思った。

APIO2020参加記

APIO 2020
https://contest.apio2020.id/
アジア太平洋情報オリンピック - 情報オリンピック日本委員会

一通のメール

2020年のAPIO(アジア太平洋情報オリンピック)は新型コロナウイルスの影響で現地開催ができなくなったので、JOI本選出場者で参加を希望した者のうち本選の成績上位60名が参加できるということでした。結局参加を希望したのが59名だったので全員参加できることになりました。やったー。


今年の主催はインドネシアです。人口が2.6億人いるのが意外だった。あと日本との時差は2時間。
インドネシア - Wikipedia

ラクティス

提出の仕方を確認した。

A.Accident Average

数列の追加クエリと範囲内の平均の最大値を求めるクエリのやつ。小課題1,2だけで16点。

B.Organizing Party

パーティで親しくなった人が一人でない人を探すインタラクティブ問題。二分探索で満点。

C.The Game of Pajel

パズルの得点を最大化するOutput Only。ケース1,2,3だけクリアして17点。
16 + 100 + 17 = 133点。まあプラクティスなので。

開会式

YouTubeで配信してた。最初はインドネシアの国家が流れてたらしい。最大で170人くらい視聴してた。
www.youtube.com
リンク変えて上げ直したらしくコメント欄もなくなってました。かなしいね。

競技本番

競技時間は選べるのですが、推奨時間(JOIのスタッフが待機している)である8月15日13:00-18:00に出ました。

A.壁の塗装 Painting Walls

Subtask1(12) f(k) <= 1
連番になっている作業員の長さをLとして(L + M - 1) / Mの総和。誤読してて一時間かかってしまった。(14:24)

B.都市の代表者の交換 Swapping Cities

Subtask3(17),Subtask4(20) 答えを決め打ち二分探索で深さ優先探索すればいけると思ったけどWAが取れず。(16:29)
Subtask1(6) 色々勘違いしてて30分かかってしまう。(17:07)
Subtask5(23) LCAでできると思ったけど時間が足りず。

C.楽しいツアー Fun Tour

時間がなくて見れなかった。

振り返り

f:id:season1618:20200821221208p:plain
結局12 + 6 + 0 = 18点。出来そうだと思った小課題をほぼクリアすることができなかった。普段のコンテストより圧倒的に時間が長いのにもたもたしてたら直ぐに終わってしまった。かなり悔しい。単純に5時間かけて18点しか取れないのがかなり辛い。人生で最も競プロができない(理想とかけ離れていた)5時間だった気がする。


目標は達成していた。

閉会式

こっちは230人くらい視聴してた。最後にメダリストが発表されました。
www.youtube.com
日本からは金1人、銀5人の6人が日本代表となりました。自分より年下の人がたくさん活躍してて凄いなあという感じです。そっか~~俺日本代表になり損ねたのか~実質サマーウォーズじゃん笑。
「何の日本代表になれなかったの?」
「えーっと、アジア太平洋情報オリンピックって言って」
「へーなんかやってみてよ」
「そうですね...先輩の誕生日いつですか」
「7月19日。平成4年の。」
「曜日がいつかわからない?wフッフッフw心配することなかれwwこんな時にも役に立つのが競技プログラミング、伝家の宝刀†二分探索†を使わせていただきますぞ!wwwまずは曜日を(0+2e9)/2=1e9にセットして……ウオーーーーーーーーーー!!!!!!!NP困難(悲しい)」
「...」

感想

悲しい。