れとろのメモ置場

とあるSEのメモ置場

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

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

結果

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

D問題のデバッグにすごく時間が掛かった… 解き方の方針自体は問題文を読んで直ぐに思いついたけど、サンプルケースの答えとなかなか一致しなくて延々とデバッグをしていた。

三分探索すれば良いのは直ぐわかっていたから、最終手段として蟻本とか鉄則本でコードのサンプルを探そうとして索引を見てみたけどまさか扱っていなかったとは…

A - wwwvvvvvv

文字列中のvの数とwの数を数えてvの数+2*wの数を出力する問題。
文字列の扱い方の練習みたいな問題。

B - LOOKUP

TがSの部分文字列になっているかどうか判断する問題。文字列ライブラリの検索処理を使えば直ぐに判断できる。

もしくはSを線形探索してTと同じ文字列部分があるかどうかを順番に見ていけば良さそう。 文字列の長さ的に愚直に線形探索しても間に合いそう。

C - RANDOM

同じサイズの2種類の格子が与えられるので、一方の列を並び替えてもう一方の格子が作れるかどうかを判断する問題。 2重ループとソートで解ける。

まず2種類の格子それぞれの列成分の配列を作る。(格子を行列をみなした時に転置行列を求める) あとはそれぞれの配列をソートして、各要素の文字列が一致しているかどうかを確認する


ABCD
EFGH
IJKL
と言った具合に格子があれば
S1=ABCD
S2=EFGH
S3=IJKL
と変数では保存しているので、(入力を受け取る関係で大体の言語だとこう管理するよね…)
S'1=AEI
S'2=BFJ
S'3=CGK
S'4=DHL
と変換したものを配列で管理して、その配列をソートする。

元の格子の列を並び替えて一致させられるなら、2つの格子の転置をソートすると全く同じ並びになるはず。

D - Freefall

下に凸な関数の最小値を求める問題。

問題文を読むと求める答えは下に凸な関数の最小値っぽいと気が付いた。凸関数の最大値、最小値なら3分探索で求めることができるのでサクッとコードを書いた。
でも微妙にバグってたせいでサンプルケース3がなかなか答えが一致しなくて延々とデバッグしていた。

時間ギリギリでなんとか解けたけどすごく時間がかかった。