2023-11-25

トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)

トヨタシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 330)に参加しました。

結果

A,B,Cの3問正解でした。

C問題を難しく考えすぎてかなり時間を無駄にした。最近まずは全探索を考えるっていう基本を忘れがちだと思った。

A - Counting Passes

問題文の通り実装して答える問題。
N人の点数が入力されるのでL点以上を取った人数を答える。

標準入力と数値の大小判定ができれば答えられる問題。

B - Minimize Abs 1

なんか変数がいっぱい出てきてなんか面倒そうだなと思った問題。

長さNの数列が入力されるから条件を満たす長さNの数列Xを出力する問題。
Xの条件がちょっとややこしい。（Yとか言う変数が急に出てくるのが悪い）

ある範囲[L,R]が指定されるので、 $A _ {i}$ からの距離がこの範囲の任意の値(Y)の距離以下となるような $X _ {i}$ を求めて数列Xを答えるという問題。（ $|X _ {i} - A _ {i}| \leq |Y - A _ {i}|$ となるXを答える問題。）ただし $L \leq X _ {i} \leq R$

$A_{i}$ が $L \leq A _ {i} \leq R$ の時、 $X _ {i} = A _ {i}$ となる。そうじゃないと $Y = A _ {i}$ の時に条件を満たせなくなる。

$A _ {i}$ が $A _ {i} \lt L , R \lt A _ {i}$ のときは $X _ {i}$ は[tex:A{i}]に1番近いRかLになる。そうじゃないとYが[tex:A{i}]に1番近いRかLの時に条件を満たせなくなる。

要するに $X_{i}$ は $|Y - A _ {i}|$ を最小化するYに合わせれば良い。

よって、 $A _ {i}$ が $L \leq A _ {i} \leq R$ かどうかを判定して、 $X _ {i}$ は $A _ {i}$ かRかLのどれかを当てはめれば良い。

C - Minimize Abs 2

非負整数Dが与えられるので $|x ^ 2 + y ^ 2 - D|$ を最小化する問題。

Dの制約が $1 \leq D \leq 2 \times 10 ^ {12}$ となっているのでDはかなり大きくなる可能性がある。

いろいろ考えて迷走した結果かなり時間をロスしてしまった問題。

ACできる解法としては、xかyのどちらか一方を0から $\sqrt{D}$ の範囲で全探索して、他方は $\sqrt{x ^ {2} - D}$ で算出する。そうやって求めたx,yをもとに $| x ^ {2} + y ^ {2} - D |$ を計算していき最小値を答えとして出力する。

最初は、 Dがかなりでかいのと最小値を求める問題だったので二分探索で対応するのかなと思って解いていた。 xとかyを二分探索で探索して $|x ^ 2 + y ^ 2 - D|$ をどこまで小さくできるのかを探索すれば良いのかなと思って解いてた。
よくよく考えると二分探索は単調増加や単調減少する時に適応できる探索方法だけど、今回最小化しようとしている式は単調に変化するような式じゃないから使えない。解き方を考えるときに単調性まで考慮できていればそもそも二分探索は候補に挙がらないなあ…

2023-11-18

Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 329）

競技プログラミング

Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 329）に参加しました。

結果

A,B,C,Dの4問正解でした。

C問題を考えすぎてロスしたり、E,F問題に手を出したものの解ききれなかったりした。

A - Spread

文字列が与えられるので文字と文字の間に空白を挟んで出力する問題。

文字列の内容を1文字ずつ出力しつつ、一緒に空白も出力させつつ、最後の文字だけは個別に出力すれば解ける。ループとかで文字列を1文字つづ扱えれば解ける問題。

B - Next

複数の整数が与えられるので2番めに大きい値を答える問題。

整数をsetに入れて2番めに大きい値を取り出せば解けそうだけど、C++のsetは要素番号とかでアクセスできるタイプの型ではないので、大人しく配列にして降順にソートして2番めに大きな値を探して出力した。

C - Count xxx

文字列が与えられるので、1種類の文字だけで作れる部分文字列の種類数を答える問題。

はじめはしゃくとり法で答え候補の文字列を実際に作りながらsetで種類数を管理していたけどTLEになってだめだった。
なので方針転換してはTLEするというのを数回繰り返してどんどんシンプルになっていった。

最終的に各文字が最大で何個連続するかを数えて、最後に文字別の最大連続個数を足して行って答えとした。

いろいろ試していたけど、文字列の扱いをやめれば高速に処理できるようになっていたので、文字列をこねこねするのはそこそこ重い処理だったみたい。

D - Election Quick Report

N人の候補者に合計M票が投票されるので、1票ごとにその時点での当選者を出力する問題。
個人的にはC問題より簡単な気がした問題。

各候補者の得票数と現在の当選者、当選者の得票数を管理しつつ、
1票投票されたらその人の得票数と現在の最大得票数を比較して当選者を更新し出力していった。

D問題にしては簡単な気がする…

E - Stamp

だけで構成された文字列に対して上からスタンプを押すみたいに一部を指定された文字列に置き換えていった場合、指定された文字列が作れるかどうかを答える問題。

ある文字列を別のある文字列に変換できるかどうかというタイプの問題はゴールからスタートに向かって逆算していくのが定番の解き方だなあと思いつつ、文字列の操作は面倒だなあとか思いながら解き方を考えてた。

最終的にいい方法が思いつかなかったので後回しにすることにして時間内には解けなかった。

F - Colored Ball

N個の集合から指定された2つをマージしていく処理を繰り返していく問題。

E問題で悩んでいたときに順位表を見るとE問題よりF問題のほうが正解者数が多かったので、こっちの方が解きやすいのかなと思って解いてみた。

結局時間内には解けなかった…

C++でsetをマージする関数があるには有ったけど、マージ後の一方は破棄されるみたいで微妙にこの問題とは相性が悪くて使いづらかった。

なんだかPythonで解けば簡潔に解けそうな気はした。

2023-11-11

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)

競技プログラミング

トヨタ自動車プログラミングコンテスト2023#7(AtCoder Beginner Contest 328)に参加しました。

結果

A,B,C,Dの4問正解でした。

E問題は単純な最小全域木を求める問題だと思って解いてたけど勘違いしてた。勘違いに気づいたのが残り5分のところで、どうにか対応させられないかと考えたけど5分じゃ無理だった。

A - Not Too Hard

問題文のとおりに処理して答える問題。

数値を受け取ってX以下なら合計に加えて、という処理をN回繰り返して最後に合計を出力すれば解ける。

数値の入力とif文、数値の加算と標準出力ができれば解ける問題。

B - 11/11

月日がゾロ目かどうかを判定して、ゾロ目の月日の日数を答える問題。

解き方を考えていると月と日それぞれを10進数表記としたときにゾロ目になるかどうかって言うのが面倒だなと思った。月日を4桁表記にして何種類の数字が出てくるかで判断できれば簡単だけど、11/01の時4桁表記だと1101だけど、月と日それぞれを10進数表記にすると11と1になってゾロ目ってことになる。

結局愚直に解くことにした。10進数表記の月と日を受け取ってそれぞれに対して、10の余りを取ってsetに入れて10で割ってを繰り返して、最終的にsetの要素数が1かどうかでゾロ目だったかどうかを判定した。

C - Consecutive

文字列が与えられるので指定された区間で同じ2文字が連続する回数をQ回答える問題。

Qの最大値がそこそこ大きくてO(Q)で解けないとTLEしそうだなと思った。と言うことは1回の質問ではO(1)で解きたい。

先頭から任意の位置までで同じ2文字が連続するのは何回かを予め数えておけば、区間[l,r]が指定されても事前に数えた結果からO(1)で答えられると考えて解いた。
前もって計算した累積和を使って解くのと同じ様だなと思った。

D - Take ABC

A,B,Cのみからできた文字列に対して最初に出てきたABCを削除するという処理を再帰的に行った結果残った文字列を出力する問題。

C++だと文字列の削除はちょっと面倒だなとか、ABCを空文字に置き換えれば良いのかなあとか、C++のreplaceだと指定した1文字を置き換えたり、正規表現に一致した箇所全部を一括で変換するからちょっと違うなあとか思いながら解き方を考えた。

最終的には、
文字列を先頭から順番にスタックに入れていく。Cが出てきたらスタックの上2つを見てABCの文字列が完成していればCはスタックに入れないし確認のために取り出したABもスタックには戻さない。ABCになっていないなら順番に気をつけながらスタックに戻してCをスタックに加える。最後にスタックから文字を取り出して文字列を復元して答えた。

E - Modulo MST

最小全域木を求める単純な問題かと思いきやそうではなかった。

与えられたKで割った余りがグラフのコストになるので、単純な最小全域木に余計な辺を加えてもKで割った余りが単純な最小全域木より小さくなることはあり得る。このことに気づくのが遅かったので解ききれなかった…

どの辺を選んでどの辺を選ばないかを考えないといけなくなるので、全通りの探索が必要っぽい。

2023-11-04

HHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327)

競技プログラミング

HHKBプログラミングコンテスト2023(AtCoder Beginner Contest 327)に参加しました。

結果

A,B,C,Dの4問正解でした。

B問題でのしょぼいミスのせいでWAを連発したのがちょっとつらい…

D問題もちょっとした見落としでWAしたので全体的にペナルティが痛かった。

A - ab

問題文のとおりに処理する問題。

与えられた文字列にabかbaが含まれているかどうかを判定して答える。文字列の初歩的な処理ができれば解ける問題だと思う。

B - A^A

Bが与えられるのでB= $A ^ {A}$ となるAがあるかどうかを答える問題。

Bは最大で $10 ^ {18}$ なのでAの候補は最大でも16くらい。
なのでオーバーフローしないように型を気にしながら16以下の $A ^ {A}$ をそれぞれ計算していく。計算結果がBと一致するかどうか探して一致したらそのAを答える。

別解としては数学でゴリ押しな解き方もできそう。 $A ^ {A} = B$ の両辺に $log_A{}$ を取って計算すると $A = log_A{B}$ になるのと、 $log_A{B} = \frac{\log_x{B}}{\log_X{A}}$ だったと思うでの、ライブラリのlog計算で $log_A{B} = \frac{\log_x{B}}{\log_X{A}}$ を計算して出てきたものが整数になるかどうかでA が存在するかどうかを判断できると思う。

C - Number Place

$9 \times 9$ のマスに1~9が書かれているので、この内容が数独の解として成立しているかどうかを判定して答える問題。

横一列と縦一列、 $3 \times 3$ のマス目で見たときの3パターンそれぞれ順番に判定を行っていけば特に困らず解けると思う。

今回はマス目の数字が1桁だけなので各数字を文字とみなして、9マス分の数字を1つの文字列にくっつけた。その後その文字列をソートして、ソート結果が123456789となっているかどうかで、ある9マスが条件を満たしているかどうかを判断していった。

D - Good Tuple Problem

はじめはよく分からなくて色々考えていったけど、結論としては二部グラフかどうかの判定問題だった。

2つの数列S,Tが与えられるけど、 $S _ {i} とT _ {i}$ が1組の辺となる。なので、ノード同士の接続状況を整理したら後は各ノードに色を塗りながら深さ優先や幅優先で探索していって、二部グラフかどうかを判定する。

単純に二部グラフの判定問題として出題すると簡単に解かれそうだからちょっとひねった問題の書き方をしているように見える。

2023-10-21

キーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）

競技プログラミング

キーエンスプログラミングコンテスト2023秋（AtCoder Beginner Contest 325）に参加しました。

結果

A,B,C,E問題の4問正解でした。

D問題がちょっと難しいなと思ってE問題を見てみたらグラフの問題でした。グラフなら解けそうな気がしたのでD問題を飛ばして、先にE問題を解いてみた。

A - Takahashi san

名字と名前が与えられるので名字 sanと出力する問題。

使用する言語の標準入出力ができるなら特に困らないと思う。
久々にこういった標準の入出力ができれば解ける内容のA問題が出た気がする。

個人的にはこれくらいの内容がA問題らしいA問題だと思う。

B - World Meeting

N箇所の拠点の人数と世界標準時からの時差が与えられるので、現地時間で09:00-18:00の間でどこか1時間会議を開くとき最大で何人が会議に参加できるかを答える問題。

世界標準時で0時から23時それぞれの時間帯に会議を開催した場合に何人参加できるかを数えて、1番人数が多いときは何人かを答えれば良い。
現地時間は(世界標準時＋時差)mod24で考えると、世界標準時+時差が24時以降になっても対応できる。

C - Sensors

問題文にはセンサーがとか連動してとかあるけど、要するにH×Wの画像のうち一部の画素が黒い画像があって、8連結で考えるときに連結成分が何個あるかを答える問題。

連結成分の数を答えれば良いので、Union-Find木で解くことにした。黒い画素に番号を振って、連結している画素同士は連結していき、最終的に連結線分が何個できているかを答える。

Union-Find木以外だと幅優先とか深さ優先で連結している画素を辿っていきつつ、連結成分数を数えていけば答えられると思う。

E - Our clients, please wait a moment

コストの最小値を求めるグラフの問題。

都市1から途中までは車で移動して、どこかの都市から都市Nまでは電車で移動するとき、都市１から都市Nまでの最短の移動時間はどれくらいになるかを答える。

途中で移動手段を電車に切り替えるとそれからは電車しか使えないと言う設定がちょっと面倒だと思う。

結論としては都市１から各都市への車で移動したときの最短移動時間と、都市Nから各都市へ電車で移動したときの最短移動時間を計算する。そこが分かれば、２種類の最短移動時間を組み合わせて都市１から都市iまでは電車で移動し、都市iから都市Nまでは電車で移動した場合の最短移動時間がO(1)で計算できるようになる。なのでiを1~Nの全通りで試して最短移動時間を探して答える。

2023-10-07

ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)

競技プログラミング

ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)に参加しました。

結果

A,B,C,Dの4問正解でした。

30分ちょっとでD問題まで解けて、後の時間ずっとE問題考えてた。 E問題の確率を mod998244353で求めるっていうのが全く分からなかった。定義を読んでみてもどこからその数字出てきた！？ってなって、たぶんこれは解けないやって思った。

A - Weak Beats

0,1でできた文字列の偶数番目の文字が全部0かどうかを判定して答える問題。

文字列の任意の文字を取得できるかどうかと、その文字列が特定の文字かどうかの判定ができれば解ける問題。

B - Round-Robin Tournament

o,xで構成された試合結果がN人分与えられるので、勝利数別プレイヤー番号別にソートして上から順番にプレイヤー番号を出力する問題。

文字列からoの数を数えて各プレイヤーの勝利数を計測する。次に勝利数とプレイヤー番号でペアを作って、そのペアをソートして上から順番にプレイヤー番号を出力して解いた。ソートは、勝利数に関しては大きい順、プレイヤー番号に関しては小さい順と項目によって昇順、降順が異なるので自作の大小比較用関数を作成して、それを使ってソートを行った。

勝利数とプレイヤー番号をセット管理しつつ、そのセットをうまくソートできれば解ける。

別の方法で解くなら、勝利数の最大値を求めて、勝利数の最大値から0まで順番に探索対象の勝利数を変化させつつ、
各ループで対象としている勝利数と一致しているプレイヤー番号を小さい順に出力していけば解けそう。

C - World Tour Finals

N人のプレイヤーがM問ある問題の一部を解いている。問題を解いているかどうかはo,xでできた文字列で与えられる。現時点の最高スコアに追いつくには最小であと難問解けば良いかを各プレイヤー分答える問題。

問題の点数と問題番号でペアを作って、点数の高い順位ソートする。それとは別に各プレイヤーの現在のスコアを計算し最高点を求める。各プレイヤーに対して、点数の高い順に何問解けばスコアが現時点の最高スコアを超えるか数えて出力する。

B問題に続いて、ペアを作ってソートすれば後は簡単な処理で解ける問題。この問題も2つの項目をセットでソートして管理するのがポイントだと思う。

D - Merge Slimes

サイズ $S _ {i}$ のスライムが $C _ {i}$ 匹いる。同じサイズ2匹で倍のサイズのスライム1匹に合成できる。
スライムの数を最小で何匹にできるかを答える問題。

合成するのは同じサイズ同士だけだし、合成した結果2匹が1匹になるので合成できる時は合成したほうがスライムの数は減らせる。なので、サイズが小さいスライムから順番に可能な限り合成していけばスライムの数は最小にできる。

スライムのサイズや数は最大で $10 ^ {9}$ になるので1から順番そのサイズのスライムがいるかどうか確認しながら処理していくと間に合わない。

存在するサイズとそのサイズが何匹いるかをうまく管理すれば解ける問題。 B,C問題も2つの項目をセットで管理する問題だったけど、今回は一方の項目の値が動的に変わったり、項目が追加されたりがあり得る。なので値の更新や項目の追加がやり辛いペアを使うのは相性が悪い。
今回は処理速度的に不安だなと思いながら連想配列のmapを使って解いた。

合成後の新しいサイズのスライムの数は $C _ {i}$ /2匹追加になるし、合成後の元のサイズのスライムの数は $C _ {i}$ を2で割った余りになる。

サイズの小さい順にこの処理を順番に実施しつつ、各サイズで余ったスライムの数を数えていけば簡単に答えが出せる。

E - Playlist

問題の内容的にDPで解く問題だと思った。

それ以前に問題文の内容が一部分からなくて解ける気がしなかった。確率を mod998244353で求めるというのが意味不明だった。

定義を読むと xz≡y(mod998244353) を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。　ってあるけど、どうやってそれを求めるのか分からなかった。出力例1の解説でzとして突然369720131が出てきてて、どこからその数字持ってきた！？ってなってた。

定義を読んでると暗号化理論でこんな感じの数式みたことあるなあと思ったりした。