れとろのメモ置場

とあるSEのメモ置場

AtCoder Beginner Contest 295

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

結果

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

D問題が難しかった。あと普段より頭の回転が鈍かった気がするなあ。

英字配列のHHKB使ってしばらく経つけど相変わらず慣れないなあ… 脳のリソースの一部がキー入力に持っていかれる。大人しくJIS配列のキーボード買い直そうか… 普段ネットする程度なら大丈夫なんだけどなあ。

A - Probably English

与えられるN個の単語に指定された単語が含まれるかどうかを答える問題。

ループを回しつつ、if文なりで探している単語と一致しているかどうかを確認して、 最後にYes/Noを出力すればいい。

if文での文字列判定やループが使えるかどうかな問題だと思う。

B - Bombs

説明は簡単だけど実装は面倒な処理を正確に実装する問題。

入力用の盤面と出力用の盤面を用意して、 入力用の盤面に応じて出力用の盤面を作成していった。

爆弾があればマンハッタン距離の範囲で空きマスに更新していく処理がちょっと面倒。 今回は中心座標と範囲を渡すと空きマスに更新する関数を作って処理していった。

C - Socks

N枚の靴下の色を与えられるのでいくつ同じ色のペアが作れるかを答える問題。

連想配列で色別に枚数を数えておき、枚数割る2で何ペア作れるのかを全色分計算して答えれば良い。 連想配列を知っているかどうかな問題だと思う。

Nや色の種類の制約が大きめだからC問題にいるけど、実装の楽さならB問題よりも簡単だと思う。

D - Three Days Ago

文字列Sが与えられるので条件を満たす区間を数え上げる問題。

いろいろ考えたけど結局解けなかった。
愚直に解こうとするとN(|S|^ {2})になってTLEしそう。

あとは、区間の数え上げなのでしゃくとり法が使えそうな気がして考えてみたけど、今回はしゃくとり法が使える種類の問題じゃなかった。

結局解けそうな方法は思いつかなかった。

AtCoder Beginner Contest 293

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

結果

A,B,C,Dの4問正解でした。C問題からちょっと手間取って時間がかかった。

微妙にレーティングは上げれたからいいけど、もう少し早くD問題まで解いておきたいなあ。そのほうがレーティングが上がりやすいし。

A - Swap Odd and Even

先頭から2文字ずつ前後を入れ替えて行き、操作後の文字列を出力する問題。
123456が214365となるような文字列の入れ替えを行っていく。

B - Call the ID Number

N以下値を持つの数列が与えられるので、1~Nで数列に含まれない数値を昇順に列挙する問題。

N個分のフラグを用意して、数列に含まれる値はフラグを立てておく。 最後に先頭からフラグを確認していき、フラグが立っていない値を順番に出力すればよい。

C - Make Takahashi Happy

各マスに数字が書かれたマス目があり、左上の端から右下の端へ移動する。その時に各マス目の数字が被らないような移動方法は何通りあるかを答える問題。

数字が被っているかどうかの判定は、通った道の数値を全部setに入れておいて、setのサイズと移動距離が一致するかどうかで判断できそう。 なので、そこまでの数値のsetを持ちながら深さ優先探索で条件を満たす経路を全探索して答えた。

ペアで座標を持ちつつ、座標とsetのペアをスタックに入れていき深さ優先探索を行った。 数字の被り判定をsetでやるのを前提に解こうとしたのでちょっと強引だった気がする。

D - Tying Rope

両端が区別できるロープがN本合って、どのロープの端とどのロープの端を結ぶかが与えられる。最終的に輪がいくつできて、輪になっていない塊が何本あるかをそれぞれ答える問題。

輪になっているのかの判定をどうしようかなとか、このロープの端は結ばれた結果どのロープの端となっているのかなどをどうやって管理しようかなと考えてみたものの、なかなか考えがまとまらなかった。

最終的にはUnion-Findを使って解いた。 ロープ同士を結合する時に、番号が小さいロープが親となるように結合しつつ、それぞれの親を確認して一致していた場合は輪になったと判断してカウント。 輪になっていない連結成分は、連結成分全体から輪の数を引いて求めた。

E - Geometric Progression

問題文と数式は簡単なのに解くのはすごく難しい…

総和のMODを取るので、各項のMODを取ったものを足しても同じ答えになる。各項はAの累乗なので、AのMODを取ったものを累乗しても答えは一致する。 と考えつつ、累乗のMODを取っているとどこかでループが起きると考えた。ループ部分をまとめて処理すれば総和の計算はかなり圧縮できるので、

  1. Aの累乗のMod Mに関してループを検出する。
  2. ループ開始までの合計を計算する
  3. 1ループの合計を計算する。
  4. 0乗からX-1乗までで何回ループするかを計算する。
  5. 最後の方のループになりきれない部分の合計を計算する
  6. ループまで、ループ中、ループ終了後それぞれの合計を足したものを出力する。

で解けると思ったけど、Mが大きすぎるとエラーになって解けなかった。

AtCoder Beginner Contest 292

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

結果

A,B,C,Dの4問正解でした。
途中よくわからないバグでエラーが起きたり、コードは間違っていないはずなのにテストケースの答えが一致しなかったり、かと思えば大してコードを変更していないはずなのに今度はちゃんとテストケースと答えが一致して無駄に時間をロスしたりと、珍しい現象でちょっと時間を無駄にしたコンテストだった。

A - CAPS LOCK

英小文字の文字列を英大文字の文字列へ変換し出力する問題。

C++ならtransformと_toupperを組み合わせると1度の処理で文字列全体を変換できるのであんまり困らない。
もしくは1文字ずつ大文字に変換して出力する。a~zとA~Zはそれぞれchar的には連番なので各文字の値にaとAの差(aとAの距離)を足せばtoupperとか使わなくても大文字に変換できそう。

B - Yellow and Red Card

イエローカードかレッドカードが提示されるイベント(クエリ)がいくつか与えられるので、選手別に退場しているかどうかを管理して、指定された選手が退場しているかどうかを答える問題。

クエリを処理しながら指定された要素の状態を答える問題であり、クエリの数はそれほど多くないのでクエリを順次処理しながら答えていくのでも十分間に合いそう。
答える時には何かしらの値を参照するだけで判断したいので、選手別に状態を管理できるようにしておく。

選手の人数はそれほど多くないので、選手の人数分の配列で状態を管理すれば良い。
イエローカードは2回で退場、レッドカードは1回で退場なので、レッドカードはイエローカード2回分とみなして 各選手がイエローカード何回提示されているのかをカウントしておく。

退場処分を受けたか質問されると、その選手がイエローカードを2回以上提示されているかどうかでYes/Noを判断して答える。

C - Four Variables

AB+CD=NとなるA,B,C,Dの組み合わせ数を答える問題(A,B,C,D>0)。

考えたこととしては

  • 愚直に得ならA,B,C,Dをそれぞれ1~Nまで全通り試して解く。けどO(N ^ {4})になってTLEするのが目に見えるので論外。
  • 1 \leq N \leq 2000なのでO(N ^ {2})くらいの解じゃないとTLEになりそう。
  • A,B,C,D>0なのでAB,CDの最小値は1で最大値はN-1までを考えておけば良い。
  • ABを1から1ずつ増加させると、CDはN-1から1ずつ減少していく。
  • AB=XとするとCDはN-Xであり、C=1、D=(N-X)で条件は満たせるのでAB,CDはそれぞれ1~N-1までの全ての値の可能性があり得る。
  • 1~N-1までのA,Bの組み合わせ数をどうにかして計算しておけばその結果はC*Dの組み合わせ数としても利用できる。

だから、次に1~N-1それぞれのA,Bの組み合わせ数を計算しようとした。 これはA*B=XとなるA,Bの組み合わせの数になる。そしてこれはXの約数の個数と一致する。

よって問題を解く手順としては以下になると考えた。

  1. 1~N-1それぞれの値の約数の数を求める
  2. A*B=Xとした時、1~N-1まで順番に、Xの約数の数 \times (N-X)の約数の数 を計算し合計する。
  3. 合計した値を出力する。

D - Unicyclic Components

無向グラフが与えられるので連結成分ごとに頂点の数と辺の数が一致するかどうかを計算し、一致しないものが1つでもあればNoをそうでないならYesを答える問題。

連結成分ごとに処理するので、Union-Findを使ってどの頂点が連結成分になっているのか判断するのが楽そうだと思った。

どのへんがどの連結成分に含まれるのか分かれば、連結成分ごとの頂点の数を数えるのは簡単にできる。 また、頂点がわかればその連結成分に何本の辺が含まれているのかが計算できる。

そこで以下の手順で解いてみた。

  1. Union-Findで各頂点はどの頂点をRootとする連結成分に含まれるのかを計算する。
  2. 各頂点で 頂点→Rootの値からどの連結成分に含まれるか判断し、Root別に自分をRootとする頂点の数、その頂点が持つ辺の数を数える。
  3. 各Rootで 自分をRootとする頂点の数 と その頂点が持つ辺の数の合計 が一致するかを確認する。
  4. 1つでも一致しない場合があればNoを出力して処理を終了する。
    最後まで処理が終われば全ての連結成分で条件を満たすことになるのでYesを出力する。

Sky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 289)

Sky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 289)に参加しました。

結果

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

D問題までは30分かからないくらいで解き終わったのにE問題がさっぱりわからなかった。
とりあえず愚直に解くように実装してみたけどそれでもだめだった...

A - flip

問題文の通りに処理する。
文字列を先頭から見ていって1なら0を、0なら1を出力させれば良い。

文字列の操作と条件分岐がわかれば解ける問題。

[B - V

漢文に返り点がある時の読み順を答える問題。 問題文の通りに実装できれば解けそう。

返り点があるときは下から上に読むので、スタックに入れていって返り点が出てこなくなったらスタックの中身を順番に取り出していけば良いなあと思ったので、スタックを使って実装した。

C - Coverage

bit全探索で全通り確認して条件を満たす場合を数え上げる問題。

条件:選んだ集合を合わせると1~Nまでのすべての数を含む

M個の集合に対してbit全探索で選ぶ選ばないを決めて、選ぶ集合をマージしていく。最終的に集合のサイズがNになるかどうかで条件を満たしているかどうかを判断した。

D - Step Up Robot

DPの中だと割りと簡単な方な気がする問題。モチの設定がなかったらすごく初歩的なDPの問題。

DP[i段目]=たどり着ける・たどり着けない として、 今i段目にいるときにi+A _ {x}にたどり着ける としてDP[0]から順番に更新していきDP[X] がどうなっているかを答える。 i段目にモチがある場合は移動できないので、その段の処理はスキップする。

Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)

Toyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)に参加しました。

結果

A,B,Cの3問正解でした。
D問題がやけに難しかった。一旦おいておいてE問題を解いたほうが良かったかも。 E問題はさっと問題文を読んだ所感だとDPで溶けそうな問題だと思った。

A - Many A+B Problems

問題文の通り処理する。

標準入力でちゃんと数値を2つ受け取れれば困らない程度の難易度のいつも通りのA問題。

B - Qualification Contest

これも問題文の通り処理する。

N個の文字列を受け取りつつ、前からKだけ保存してからソート後に順番に出力する。

ソートがわからないならsetに入れてソートはプログラム側に任せておいてsetの先頭から順番に出力させるのでも良いと思う。

C - Don’t be cycle

グラフの閉路を検出する問題だと思う。

閉路をなくすために辺を削除するけど最少で何本の辺を削除すれば良いかを答える問題。 閉路が1つあったときに閉路じゃなくすには辺を1本削除すれば良いと思ったので、削除する辺の最小値=閉路の数と考えた。

閉路の検出は深さ優先探索かUnion-FindでできるのでUnion-Findで処理した。 具体的にはノードを2つ併合するときにそれぞれの親が一致していれば閉路ができると判断した。

D - Range Add Query

思ってたよりも難しい問題だった。そこそこ時間を使ったけど結局解けなかった。

数列Aが与えられるのでQ回条件を満たすかどうかを答える問題。
条件は数列Aの一部の区間が指定されるのでその区間の部分数列に対して、 連続するK個の要素に任意の値cを足す という処理を0回以上行い部分数列の全要素を0にできるかどうか。

ちょっと面倒な問題をQ回解くとみなして考えてみていた。
気がついたこととしては

  • 各処理は独立して行われるので処理の順番は入れ替わっても問題ない。
  • 連続するK個の要素の内先頭の項番をiとすると、何回でもiを選択していいけど毎回の処理は独立しているので各iは1回だけ選択すれば十分
  • 全部0にできるかと言うのは全部0の状態からその状態へ遷移できるかと同義なので全部0の状態から考えたほうが良い事が多い

ということで考えていくとi=1から順番に処理していくとして考えていったほうが考えやすそうと思った。

次にcはどうやって決めていくかを考えてみたけど、i番目の項の値はK-1個前から1個前までのcの値の和に影響すると気づいた。 なんとなくフィボナッチ数列っぽなあと思ってcを求める処理を実装してみた。

iの範囲が1~n-K+1なのでn-K+1番目の項までは確実に0にできるので、n-K番目~n番目の後までが0にできるのかどうかを確認してYes,Noを出力させるように実装してみた。 でも結局コンテスト時間には間に合わなかったし、提出してみるとTLEになって散々な結果だった。

ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)

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

結果

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

もう少しでE問題も解けそうだったから悔しい。

あと、何故かキー入力の調子が悪かった。相変わらず英字のHHKBを使っているけれど記号とFnキーの入力でどこだっけと考える時間が入って思うように入力できなかった。いつもはもう少しスラスラ入力できるのにどうしたんだろう。

A - Range Swap

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

数列Aのコピーを用意して、P~QとR~Sをコピーへ移してから出力する。

B - Cat

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

naをnyaに置き換えた文字列を出力するだけで良いので、 1文字ずつ出力しながら、今出力した文字がnで次の文字がaの時aの前にyを出力するだけで回答できる。

C - Rotate and Palindrome

全通り探索してコストが最小のものを答える。

操作は2つあるけど任意の1文字を置き換える操作は最後にまとめて行えば良い。
任意の文字列を後ろへ移動させる処理は、元の文字列を2つ続けたものをi文字目を先頭にN文字抜き取ったものを対象にすれば1回ずつ文字列の操作をしなくて済んで楽だと思った。 文字入れ替え後の文字列は先頭と後方から順番に1文字ずつ比較していけば文字置き換えの回数は簡単に求められる。

なので各回で必要なコストは簡単に計算できるのでminとかで最小値を更新し続けて最後に結果を出力する。

D - Money in Hand

ただのDPで解く問題。

DP[i番目の硬貨まで確認した][残り金額j円]=ブール値 としてi番目の硬貨までを使ってj円が支払い可能かどうかを計算していった。最後に残り金額0円でtrueとなっているものがあるかどうかを探して支払い可能かどうかを答える。

E - Souvenir

有向グラフで最短経路問題を解きつつ、別途設定されている価値を最大化する問題。

ダイクストラで最短経路を計算しつつ、合わせて価値の最大値を計算していけば解けそうだと思った。 なので普段のダイクストラでホップ数と次ホップノードだけ管理しているところに、そこまでの価値を追加して管理しようとして調べながら拡張していたら時間が切れた。

AtCoder Beginner Contest 285

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

※いつもと違って日曜日に開催なので翌日の仕事に影響しないようにいつも以上に簡潔に考察の整理

結果

A,B,C,Dの4問正解でした。D問題がいつもより早く解けた気がする。

A - Edge Checker 2

配列で2分木を作るときに親子関係がどうなっているかを知っていればすぐに解ける問題。

子の番号は親の番号2と親の番号2+1になるのでa,bの関係がこれに当てはまるかどうかを判定する。

B - Longest Uncommon Prefix

問題文を読んでもいまいち何をすればいいかわからなかった問題。

入力例とその解説を読んで何をするのか読み取った。その後、読み取った内容から実装して入力例だと答えが一致することを確認してから提出。

i = 1,2,・・・N-1それぞれの場合で、 文字列中の文字をi文字飛ばしで比較していき、何文字目までは一致しないかを求めて出力する。

C - abc285_brutmhyhiizp

26進数変換をする。 A~Zで構成された26進数表記の値が与えられるので10進数に変換して出力する。

D - Change Usernames

文字列を頂点とみなしてS[i]からT[i]へ有向辺を伸ばしてく。 最終的に出来上がるグラフにループがあるかどうかを判定し、ループがなければYes、ループがあればNoを出力する。

E - Work or Rest

もう少しで解けそうな気がして時間内には解けなかった問題。

とりあえず考察としては、

  • 適用される生産性はmin(最後に休んでからの日数,次の休みまでの日数)
    →N日間のうち休日が1日だけだったとしてもAの後ろ半分は利用されることがない。 min(最後に休んでからの日数,次の休みまでの日数)は、休日、1日、2日、・・・、N/2-1日、N/2日、N/2日、N/2-1日、・・・2日、1日、休日(翌週)といった具合で変化していく。
    週の半分をすぎると、最後に休んでからの日数より次の休みまでの日数の方が小さくなるのでAの後ろ半分は参照されることはない。

  • 連続n日働いた場合の生産性の合計は\Sigma ^ {n} _ {i=1} A _ {i} \times 2になる。
    総和が欲しいので累積和を予め計算しておけばこの部分はO(1)で算出できる。

このあたりで時間がなくなった来たのでとりあえず、i日連続で勤務した時の生産性を計算して、 サイズNの箱をサイズiのアイテムで埋めていったときの生産性の最大値はいくつになるのかという問題に置き換えて解こうとした。

改めて文章にしてみるともろにナップサック問題だけど、コンテスト中はナップサック問題だとは気づけなかったので貪欲法で解こうとして、でも入力例には合わないなあ、どこか考慮漏れがあるのかなあとデバックをしていた。