little star's memory

競プロの参加記など

競プロ典型 90 問を Kotlin で解く

この記事は、競プロ典型 90 問を Kotlin で解いたものをリストにしたものです。制作中です。

Kotlin の基本的な入出力については、以下の過去記事をご覧ください。

koboshi-kyopro.hatenablog.com

001 - Yokan Party(★4)

最小値の最大値を求めよという問題のとき、「最小値の最大値は x 以上か」という判定問題を考えると、これは x がある値以下で OK、ある値以上で NG となるので、二分探索が使えます。OK である x の最大値が答えになります。

この問題の場合は「K+1 個のピースのうち最も短いものの長さが x 以上になるか」を考えることになります。言い換えると、「どのピースも長さが x 以上となるように K 回で切れるか」を判定することになります。

提出コード: https://atcoder.jp/contests/typical90/submissions/24001981

002 - Encyclopedia of Parentheses(★3)

制約が小さいので全探索できます。bit 全探索も可能です。以下のコードは DFS を用いています。

提出コード: https://atcoder.jp/contests/typical90/submissions/24002351

003 - Longest Circular Road(★4)

木において2点間の距離の最大値を直径といいます。直径を求めるには、適当に頂点を選び、そこから最遠点 v を求め、再び v からの最遠点 w を求めると、vw が直径となっています。BFS を用いて計算できます。Kotlin では ArrayDeque を用いるとよいでしょう。

提出コード: https://atcoder.jp/contests/typical90/submissions/24426158

004 - Cross Sum(★2)

行の和、列の和を前計算して高速化します。

提出コード: https://atcoder.jp/contests/typical90/submissions/24002686

005 - Restricted Digits(★7)

準備中

006 - Smallest Subsequence(★5)

準備中

007 - CP Classes(★3)

ソートして二分探索を用います。Kotlin では、a.sort() で a をソートし、a.sorted() で a をソートした結果を返します (後者の場合 a 自体はソートされない)。

提出コード: https://atcoder.jp/contests/typical90/submissions/24043849

008 - AtCounter(★4)

"atcoder" の何文字目までを取り出したかという状態をもたせて DP をします。

提出コード: https://atcoder.jp/contests/typical90/submissions/24043957

009 - Three Point Angle(★6)

準備中

010 - Score Sum Queries(★2)

累積和を計算します。sum1[i] は、1 から i 番目までの 1 組生徒の点数の和を表します。

提出コード: https://atcoder.jp/contests/typical90/submissions/24044039

011 - Gravy Jobs(★6)

準備中

012 - Red Painting(★4)

UnionFind を用います。過去記事も参照してください。

koboshi-kyopro.hatenablog.com

提出コード: https://atcoder.jp/contests/typical90/submissions/24063740

013 - Passing(★5)

準備中

014 - We Used to Sing a Song Together(★3)

ソートします。

提出コード: https://atcoder.jp/contests/typical90/submissions/24063838

015 - Don't be too close(★6)

準備中

016 - Minimum Coins(★3)

A 円硬貨を x 枚、B 円硬貨を y 枚、C 円硬貨を z 枚使うとします。x,y,z すべてを全探索すると間に合いませんが、x,y を決めれば、z の値は Ax+By+Cz=N から決まるので、x,y だけ全探索すればよいです。

提出コード: https://atcoder.jp/contests/typical90/submissions/24072733

017 - Crossing Segments(★7)

準備中

018 - Statue of Chokudai(★3)

三角関数を含む数学関数を使う問題です。java.lang.Math または kotlin.math に含まれています。

提出コード: https://atcoder.jp/contests/typical90/submissions/24072912

019 - Pick Two(★6)

準備中

020 - Log Inequality(★3)

小数を扱う際には誤差に注意する必要があります。整数に直して解く、誤差が eps 以下のときに等しいとみなす、などの対処法があります。

提出コード: https://atcoder.jp/contests/typical90/submissions/24072961

021 - Come Back in One Piece(★5)

準備中

022 - Cubic Cake(★2)

最大公約数です。ユークリッドの互除法を実装しましょう。

提出コード: https://atcoder.jp/contests/typical90/submissions/24162670

023 - Avoid War(★7)

準備中

024 - Select +/- One(★2)

必要な操作回数が K 以下かつ、K と偶奇が等しいかを判定します。

提出コード: https://atcoder.jp/contests/typical90/submissions/24162773

025 - Digit Product Equation(★7)

準備中

026 - Independent Set on a Tree(★4)

木は二部グラフです。DFS によって二部グラフにすると、どちらかの集合は N/2 頂点以上を含むので、ここから N/2 頂点を選べばよいです。

提出コード: https://atcoder.jp/contests/typical90/submissions/24162923

027 - Sign Up Requests (★2)

Set を使うと解くことができます。Kotlin では MutableSet が追加・削除可能な Set となります。set.add(s) を行うことで、s が存在していなければ True を返して追加し、すでに存在していれば False を返します。

提出コード: https://atcoder.jp/contests/typical90/submissions/24163084

028 - Cluttered Paper(★4)

二次元いもす法を用います。

提出コード: https://atcoder.jp/contests/typical90/submissions/24163414

029 - Long Bricks(★5)

準備中

030 - K Factors(★5)

準備中

031 - VS AtCoder(★6)

準備中

032 - AtCoder Ekiden(★3)

N! 通りの順列をすべて試します。Kotlin には next_permutation 関数がないので、作る必要があります。

提出コード: https://atcoder.jp/contests/typical90/submissions/24414542

033 - Not Too Bright(★2)

コーナーケースに気を付けましょう。制約の上限だけでなく下限にも着目することが大事です。

提出コード: https://atcoder.jp/contests/typical90/submissions/24414695

034 - There are few types of elements(★4)

尺取り法です。Map を用いて区間内における値の個数を記録します。また、尺取り法で Queue を用いることもできます。詳しくは以下の記事をご覧ください。

qiita.com

提出コード: https://atcoder.jp/contests/typical90/submissions/24414812

035 - Preserve Connectivity(★7)

準備中

036 - Max Manhattan Distance(★5)

準備中

037 - Don't Leave the Spice(★5)

準備中

038 - Large LCM(★3)

64bit 整数型で扱えないような巨大な数が登場する場合もあります。Kotlin では BigInteger が使えるので、使えるときは使いましょう。

提出コード: https://atcoder.jp/contests/typical90/submissions/24414879