2022-11-05

AtCoder Beginner Contest 276

競技プログラミング

AtCoder Beginner Contest 276に参加しました。

結果

A,B,C,D問題の4問正解でした。E問題がちょっと上手い方法を思いつかなかった… 何も考えずに幅優先探索とは深さ優先探索をするとTLEになりそうだったので他の方法を色々考えてみたけどいけそうな方法が思いつかなかった。

A - Rightmost

問題文の通りに処理して結果を出力する問題。

ちょっとだけ工夫して、文字列の後ろからaを探していき、1番後ろのaが後ろから何文字目なのかと文字列全体の文字数をもとに、文字列最後のaが先頭から何文字目かを計算して出力した。

与えられる文字列が高々100文字程度なので大人しく先頭から探索していくので十分だとは思う。

B - Adjacency List

setの配列を使えば簡単に処理できる問題。

道路の元に対応するsetへ道路の先の都市を入れていけば、setのサイズ=都市iと道路で直接結ばれた都市の数になり、setの先頭から順番に要素を出力すれば昇順になっている都市の番号となる。

setを使わないならたぶん配列で処理することになるけど、重複の考慮とソートするっていう処理が入ると思う。 B問題なら多分TLEになることはないとは思う。データ構造を工夫してシステム側に処理を任せられる部分は丸投げにしたほうが心配することが少なくて気が楽だけど。

C - Previous Permutation

Nが最大で100と小さいので $N ^ {3}$ の解法でも間に合うかなと思って1回愚直に解いてみた。（TLEだったけど。）

１～Nまでを順番に追加した配列を用意して1個前の配列を保存しながらPと完全一致するまでnext_permutationを繰り返し、完全一致したときに保存しておいた1個前の配列の中身を出力した。

計算量的に大丈夫だと思って愚直に解くとTLEだったので他の方法を考えてみたけど、少し調べたらprev_permutationという関数が見つかった。辞書順で1個前の順列を取得できるらしいのでPに対してprev_permutationを実行して結果を順番に出力した。

$a _ {i}$ を $2 ^ {x} \times 3 ^ {y} \times X$ と言う形式で表したときにすべての $a _ {i}$ に対してXが同じなら $a _ {1} = a _ {2} =...=a _ {N}$ を満たす状態にできると言える。ただ、答えは必要な操作の最小回数なので全部Xになるまで操作を行うと、本来は操作しなくても良かった操作を何回か行ったことになるかもしれない。

まずは $a _ {i}$ に対して2で何回割れるか、3で何回割れるかを数えていき、それぞれの最小値を求める。それぞれの最小値以上は操作をする必要はないので最小値との差分を数え上げていく。

例えば、4と8が有ったとき $4 = 2 ^ {2}、8 = 2 ^ {3}$ だから5回操作すれば全部1にできるけど、全部同じ値にしたいなら1になるまで割る必要はなく、4は4のまま、8は1回操作して4に置き換えれば全部を4にできるので操作回数は1回で済ませられる。

2022-10-22

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

競技プログラミング

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

結果

A,B,Cの3問正解でした。あと10分遅れでD問題も正解だった。

デバッグに時間がかかってD問題が時間内には解けなかったのが悔しい。計算量削減の方針などは合っていたけどデバッグが間に合わなかった。

A - Batting Average

入力した2数の割り算を少数第4位で四捨五入して小数点以下3桁までを出力させる問題。末尾0埋めで出力させるのが面倒くさい。

計算して少数第4位に5を加えて、少数第3位までを文字列にして出力させた。よくよく考えたらsetprecisionとかprintfで小数点以下の桁数を指定して出力できるからわざわざ文字列に変換しなくてよかったかも。

B - Line Sensor

マス目に.か#が書かれているから各列の#の数を出力する問題。

2重ループで処理すれば特に困らないと思う。

C - Ameba

2分木を作っていく問題かなと思った。

$A _ {i}$ の子2つに親の値+1を設定していくだけの問題。二分木を配列で実装する場合、親がiとしたとき子のインデックスが2iと2i+1になることを知っていれば特に悩まずに実装できるのかなと思う。

D - Robot Arms 2

指定された条件で点を置いていったときに最後の点が指定した座標に設定できるかどうかを判定する問題。

条件は

点 $p _ {1} = (0,0)$
点 $p _ {2} = (A _ {1},0)$
点 $p _ {N+1}$ は指定された座標(x,y)
点 $p _ {i}$ と点 $p _ {i+1}$ の距離は $A _ {i}$
線分 $p _ {X}p _ {X+1}$ と線分 $p _ {X-1}p _ {X}$ が直行するように点 $p _ {X+1}$ を設定する

愚直に

深さ優先探索で順番に点を設定
前回X軸にそって点を設定した場合と、前回Y軸に沿って点を設定した場合に分けして処理

でやってみたらTLEだった。

すこし考察してみると、

X軸に沿って点を設定した場合とY軸に沿って点を設定する場合は交互に起きる
各操作でX座標かY座標のどちらかしか変化しない

→処理をX軸に関してとY軸に関してに分離して考えることができる。

と気づいたので愚直に解いたときは2次元で考えていたことを1次元 $\times$ 2回に修正して実装した。それでもTLEだったので $p _ {i}$ に関して1度チェックした座標は処理を省くように少し修正してみた。最終的にACできたけど、デバッグ中にコンテストが終わってしまった。デバッグで少し手間取ってケアレスミスを連発していたのがちょっともったいなかった。
ギリギリ時間内にACできただろうなあ。

2022-10-15

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）

競技プログラミング

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）に参加しました。

結果

A,B,Cの3問正解でした。
D問題は解き方や高速化の方針は解説と一致しているのになぜかTLEがいくつか出てACできなかった。
想定解通りの解き方しているのにTLEになるのは納得いかないなあ。

A - A Recursive Function

要するにNの階乗を出力する問題。

再帰関数を作って解くなり、ループで計算するなり好きな解き方をすれば良いと思う。言語によっては階乗計算用の関数が用意されてそう。

B - Broken Rounding

1の位から $10 ^ {K-1}$ の位まで順番に四捨五入した時の最終結果を答える問題。

四捨五入の実装が面倒くさいだけの問題。四捨五入する位に5を足して、 $10 ^ {x}$ で割って端数を切り捨てて同じ数をかけて桁数をもとに戻していった。

C - (K+1)-th Largest Number

何回問題文を読んでもなにをどうすれば良いのか良くわからなかった。
とりあえず入力例1とその解説を読んで処理内容を推測して解いていった。

なんとなく読み取った範囲だと、数列の項 $A _ {i}$ より大きい数が何種類あるのかを数えて、K種類の場合の項数を答えるっていうのをK=0～N-1まで順番に出力すれば良いっぽい。

なのでどの値が何個あるのか数えて、重複を省いて大きい順に並び替える。
ある値より大きい数の種類数がいくつかっていうのは、要するに0-indexで大きい順に何番目かということ。

結局、 K番目に大きい値が何個あるのかをK=0~N-1まで順番に出力すれば良い。

D - LRUD Instructions

高速にシミュレートして答える問題だと思う。

巨大なマス目の中に少しだけ壁がある状態で指定された行動のシミュレートを行う。 1回の行動で移動する距離がとても大きい場合があるので1マスずつのシミュレートではTLEする。
この問題の肝はたぶんこのシミュレートをどうやって高速化するのかという部分だと思う。

マス目のサイズに対して壁の量はかなり少ないので、今いる位置から移動方向にある1番近い壁の位置を高速に求めて、壁にぶつかるから壁の手前で止まるか壁に届かないから指定された距離移動するかを判断して現在位置を更新、出力していけば良い。

今いる位置から移動方向にある1番近い壁の位置を高速に求めるのは、今いる位置と移動方向の行（または列）の壁の位置のリストから二分探索で求めれば良いと思う。
そのために行別と列別に壁の位置のリストを用意しておく。そのリストも全行、全列分用意するとメモリ不足になるので連想配列などを使って壁がある行・列だけ用意しておく。

上記をまとめると以下を繰り返す。

壁の座標を受け取ったときに行別と列別に壁の位置リストを作り、列番号や行番号を指定すればそのリストを参照できるようにする。
移動方向と移動距離を受け取ったときに、現在地をもとに移動方向に壁があるかどうかを確認
- 壁がない場合、指定された距離移動
- 壁がある場合、移動方向で1番近い壁を二分探索で探し、移動距離をもとに壁の手前まで、或いは指定された距離を移動
移動後の位置がマス目の外側にいかないように補正する。

公式解説の想定解法と上記の解き方は同じはずなのに、解説のサンプルコードと同じC++で実装してもTLEするテストケースがいくつか有った。納得いかないなあ。

改めて解説を読んだり自分のコードを見直してみようとは思うけど…

2022-10-08

AtCoder Beginner Contest 272

競技プログラミング

AtCoder Beginner Contest 272に参加しました。

結果

A,B,Cの3問正解でした。 D問題は合ってそうだけどどっかバグってたっぽい。テストケースはACだったけど提出するとWAで、だめなパターンを見つけられなかった…

A - Integer Sum

問題文の通り処理する。

入力される値の合計を計算して出力する。標準入力で数値を受け取れるなら特に困らない問題。

B - Everyone is Friends

少しややこしくて簡単な解き方がちょっと思いつかなかった。

入力を受け取り人xがk回目の舞踏会に参加したかどうかをフラグ化してから、 xが参加した舞踏会の参加者をsetに追加していき（x自身は除く）、 setのサイズがN-1になっているかどうかで判定を行った。

C - Max Even

2数の和の内、偶数となるものの最大値を求める問題。

和が偶数になるのは偶数＋偶数か奇数＋奇数の場合なので、入力される数値を偶数のグループと奇数のグループに分けてからそれぞれをソートし、1番大きいものと2番めに大きいものを足す。答えの候補が2つできるので大きい方を出力する。

D - Root M Leaper

マス目上を指定された距離ちょうどで移動した場合に書くマスは何回目の移動でたどり着くかを全マス分答える問題。

多分移動可能なマスを探す部分でバグっていてACできなかった。

基本的な方針としては幅優先探索で移動可能なマスを見ていった。また、移動可能なマスは、x座標を固定してx座標がXのときのy座標が何になるのかを算出してyが $N \times N$ のマス目の中に収まりかつ整数値になるかどうかで移動可能かどうかを判断した。

2022-10-01

京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)

競技プログラミング

京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)に参加しました。

結果

A,B問題の2問正解でした。

なかなかに酷い結果だった。C問題でハマり、D問題を先に解こうとしたけどTLEなり、改善案がぱっとは思いつかなかったのでC問題に戻ったけど最終的にC問題も解けず…

A - 484558

入力された数値を16進数に変換するだけの問題。 A問題にしてはちょっとめんどくさい気がする。

16で割った余りを求めて、16で割ってを繰り返して16進数変換後の各桁の値を求めつつ、各桁の値を文字列に変換していった。 C++なら文字列の0～9は'0'に0~9を足せば用意できるし、A~Fは'A'に０～５を足せば用意できる。なので各桁の値が9以下ならそれを'0'に足して10以上なら10を引いたものを'A'に足す。

あとは変換後の文字列が1桁なら先頭に0を足して出力すれば良い。

B - Maintain Multiple Sequences

多次元配列の指定された要素を出力する問題。多次元配列の扱い方を知っているかどうかの問題だと思う。

特に詳しく考える必要もなく、入力を配列に入れてその後指定されるQ個の要素を順番に出力する。ちょっと気をつけるとすると配列は0始まりに対して、要素の指定は1始まりなので1つずらしてあげるくらいかなあ。

こっちがA問題でも良い気がする。

C - Manga

微妙にハマってACできなかった…

基本的にシミュレートで答えを求めようとしたけどうまくシミュレートできなかった。

考察としては

最初N冊しか持っていないので答えとしてありえる最大値はNになる。
（N冊本を持っていて1巻ずつ順番に読むのでN+1巻以降は絶対に読めない。）
同じ巻は2冊以上いらない。
2冊売って1冊買うので操作を繰り返すほど手元の冊数は減っていく。

なので最初に売って問題ない本が何冊あるのかを数えて何冊買えるのかを計算する。あとは1巻から順番に揃っているかどうかを確認していった。足りない巻数がある場合は買える冊数を1消費して買ったことにして次を見ていった。

あとはWAになる度にどんなパターンだとだめか考えて修正してを繰り返していったけど、完全に直しきることはできなかった。

D - Flip and Adjust

サクッと実装してみたけどTLEになったし修正方法もすぐには思いつかなかった…

はじめはDPで解こうとして、DP[i番目のカード][表・裏]=和　として解こうとしたけど最終的にN枚のカードの表裏の情報も必要になるので違うかなと思って別の解き方を考えることにした。

次に思いついたのが幅優先探索で全通り試してみる方法。とは言えNの最大値が100なので計算回数が最大で $2 ^ {100}$ でざっくり計算すると $2^{100} = 1024 ^ {10}$ なので十中八九TLEしそう。

サクッと実装して提出してみたけど案の定TLEした。この方針だと特に計算量の改善方法が思いつかなかった。

解説を読むとDPで解くのが想定解だったっぽい。

2022-09-17

UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)

競技プログラミング

UNICORN プログラミングコンテスト2022(AtCoder Beginner Contest 269)に参加しました。

結果

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

久々に4問解けた気がする。E問題も解説を見ると解き方の方針は合ってたっぽい。もう少し時間があってデバッグが間に合っていればACできた気がする。

A - Anyway Takahashi

問題文の通り計算結果と指定文字列を出力すれば良い。

計算結果出力後に改行するのを忘れなければ正解できると思う。

B - Rectangle Detection

解き方が色々とありそうな問題だと思う。

＃で表現された長方形の領域が行と列の2軸でどこからどこまでかを求めて答える問題。ループで長方形の開始の行と終了の行、開始の列と終了の列を探して答えれば良い。

文字列の中で特定の文字を含むかどうかを探す関数が有るかとか使い方を調べるのが面倒だったのと、2重ループで全文字を確認しても時間に余裕が合ったので、A,B,C,Dを適当な値で初期化してから S[i][j]が#の時 $A=min(A,i)$ , $B=max(B,i)$ , $C=min(C,j)$ , $D=max(D,j)$ を計算して最終的なA,B,C,Dを出力することにして解いた。

C - Submask

まず問題文を読むと10進数表記の数値を2進数に変換してどのビットが1になるのか求める必要があるのがわかる。そこからは色々解き方がある気がする。

最初はbit全探索で全通り確認することを考えたけど最大で $2 ^ {60}$ 回処理することになるのでTLEしそうだなと思った。（コンテスト後に気づいたけど、1となるビットは最大でも15個なので1となるビットの内どれを含めるかのbit全探索なら $2 ^ {15}$ 回の処理になるからこれならTLEせずに済みそう。）

次に $2 ^ {x}$ ならDP[x][何か]でも処理できることが多いのでDPで解けないかなあと考えてみた。 DP[iビット目][選ぶ/選ばない]として手計算してみるとビットが1のときだけ値が変化するので最終的に DP[i番目の1となるビット][選ぶ/選ばない]でDPできそうだなあと思いた。よくよく考えるとDP[i]の結果に対して $2 ^ {x}$ を足す・足さないで分岐していくので幅優先探索の要領で探索していくほうが良さそうと思って幅優先探索で解いていった。

D - Do use hexagon grid

最終的には連結成分の数を答えるので、Union-Find木で処理していくのが良さそうだなと思ってUnion-Find木で解いていった。

黒いマスの数は最大で1000個なのでどの点とどの点がつながっているかを2重ループで調べてもTLEはしないので、全組み合わせで点同士が連結しているかを確認し処理していった。

Union-Find木を知っていればそれほど難しい問題ではないように思う。

E - Last Rook

インタラクティブな問題は珍しいかった。

問題としては、各行・列には1個だけコマが置ける時、どのマスにコマを置けるかを答えれば良い。

問題文を読んですぐに2分探索を使って行と列を個別に探索すれば良いと思った。

最終的にデバッグが間に合わなくてACできなかったけど、解説を見てみたら解き方の方針は合っていたっぽい。

コンテストが終わって見直してみたらちょっと修正しただけでACできた… 質問回数の上限である20回でループを回していたけど、20回目で特定できたときに答えを出力するの忘れてたみたい。ループの中で1ループ1質問でコードを書いていたので20回目の質問でマスを特定できたときはループを出てから何もしていなかった。このミスがなければ時間ギリギリだったけどACできたのでちょっと悔しいなあ。

2022-09-10

ユニークビジョンプログラミングコンテスト2022 夏(AtCoder Beginner Contest 268)

競技プログラミング

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

結果

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

C問題は問題を読むと難しそうな気がしたので先にD問題を見て、解けそうな気がしたからDから先に解いてみたけど失敗だった...
問題を読んだときの第一印象と違ってC問題は簡単だったし、逆にD問題は難しかった。最終的にD問題はACできなかったのでD問題にかけた時間は丸々無駄になったし順位もそこそこ落ちちゃった。

A - Five Integers

入力された整数の種類数を答える問題。

整数をsetに入れていき、setのサイズを答えれば良い。
setを知っているかどうかがポイントな気がするけど、A問題にしては難しい気がする。

B - Prefix?

問題文の通り解いていけば良い。

各文字列の先頭からSの文字数分だけ順番にSとTのi番目の文字が一致するかどうかを確認すれば良い。不一致な文字が出たらNoが確定するし、 Sの末まで確認が終わればYesになる。

ループと文字の比較がわかれば解ける問題。

C - Chinese Restaurant

問題文を読んだ第一印象と少し考察しての難易度が少し違った問題。

愚直に考えると、1ずらした場合はどうなる、2ずらした場合はどうなる、・・・N-1ずらした場合はどうなるを計算して最大値を答えれば良さそう。ただ、Nが最大 $2 \times 10 ^ {5}$ でこの方法だと $O(N ^ {2})$ になるのでTLEになる。

少し考えてみて、ある料理 $p _ {i}$ に注目してみると、この料理は位置 $p _ {i}-1, p _ {i}, p _ {i}+1$ のどこかの位置にいれば人iは喜ぶことになる。具体例として料理 $p _ {i}=4$ とすると、この料理は3,4,5のどこかに位置にいれば人4は喜ぶ。

つまり、今位置iに料理 $p _ {i}$ があるので $p _ {i}-1-i, p _ {i}-i, p _ {i}+1-i$ の3通りのどれかだけズレせば人iは喜ぶ。 N個の料理全部対して上記を計算して、何回ずらせば喜ぶ人が1番多いかを数えれば答えが求まる。 3通りの計算は $O(1)$ でできるし、料理N個分の処理は $O(N)$ でできる。計算後の結果確認も $O(N)$ でできるので最終的に $O(N)$ で問題が解けることになる。 $O(N)$ だとTLEしないのでACできる。