三井住友信託銀行プログラミングコンテスト2019

A問題

B問題

C問題

D問題

E問題

F問題

差分: +36

3完
3完再び・・・。
またこのレベルでレート下がるのか・・・と思ったけど下がらなかった。
ちょっとDが難しめだったみたい？
みんながどこで間違えたか分からないからどこがネックなのかは分からないが、自分のミスはこの問題に対するものではなく競プロ全般に対する知識が甘かったせいなので、たまたまみんなが解けなくてよかった。
それを除いて今回も細かいミスやらかした。
私の人生は常にミスとともにあることを再認識した。

A問題

かんたん。めんどくさい。
最近この手の問題は連想配列を使うことにしている。
問題文ではシングルクォーテーションで囲まれてて少しむっとなりながら全部手打ちしたが、置換とか使った方が良かったかな。

B問題

このループする系でかなり悩んで結局スマートに実装できなかったのがあるのだが、今回はそんなことなく簡単だった。
かなり悩んだ問題が競プロだったかどうかも分からないが、足して余り取って足してってしてたら元に戻っちゃってうわあああってなったの思い出す。
他の人の解法で見たが、Z超えたら26引くの方が簡単だったな。

C問題

びっくりするくらいすぐに二分探索だと分かった。
成長ポイント。
こっちはめぐるちゃんに二分探索教えてもらってるんだが？そんな問題でどうにかなると思ってるのか？
るんるん気分で15分溶かした。

問題文読んで二分探索と認識
+30秒

入力とか二分探索部分とか全体の実装
+2分

d(N)は十進表記での数・・・？それNと違うの？Nは何進法？よく見たら桁数だった。
改行位置の妙。
+1分

実装終わり！
・・・サンプルケースの計算が終わらない。
途中経過とか色々出力してmid=(ok+ng)/2であるべき部分を、mid=(ng-ok)/2にしていることに気づく。
+10分以上

mid=(ok+ng)/2よりもmid=(ng-ok)/2+okの方がより直感的だなと感じる人間なので、その感性と普段mid=(ok+ng)/2で書いてるのがすごく悪い感じに合わさってしまった形。
せっかく二分探索がすごく簡単になるように教えたのに、midの計算間違えるような人は知りませんってめぐるちゃんに言われそう。

D問題

あーうんうんグラフの探索ね。
色数は必ず二色でいけるのでは？と謎なこと思いながら木ってなんだっけと調べ直す。
木ってこんなんだっけと思いながら色数は頂点に集まる辺の数だなと分かる。
彩色する問題だし深さ優先探索でいけそうだ。
グラフの実装もだいぶ慣れてきたし特に確認もせず最後まで実装しちゃったが、サンプルケースは合ってるし提出したらTLE+MLE+RE。ひええ。
3つくらい解法試したが全部だめ。
詳しくは次の記事に書く。
結局はdp[10^5][10^5]の配列を作ったのが間違いで、mapに入れたら通った。
方針も実装も間違っていなかったのが悔やまれる。

E問題

え、うそなんでD解けないの・・・と絶望しながら見た。
うーーーーーん、難しいのか簡単なのか分からない。
こういう問題は手を出さない方が良い。

コンテスト終了後に軽く解説を読んだだけでは理解できなかった。
-1すれば個数を考える必要がないというのはなるほどという感じだが、何通りかを計算するのはどうやるんだろう？

ちなみにEの方が難しい問題は参加したコンテストでは初。

F問題

全く見てない。
コンテスト後に軽く解説を読んだら結構すぐに分かった。
本番でも(Dさえ解ければ)解けたかも？

1が続く部分では、多少損しても1の開始地点近くから始めないと1の連続を飛び越えることができないので、その辺どうしようというのが第一感想。
よく考えてみれば、なるべく多く進むようにして1が連続する手前で進む数を調整して例え1しか進めなくても良いとする場合と、何らかの良い感じに1が連続する手前に止まれるように進む方法を考える場合とでは、移動するサイコロを振る総回数は変わらなさそう。
どこで止まるべきかを再帰的に考えていくと、[0*a][1*b][0*c]みたいな1を0で挟む列になって、aの値はなるべく多く進むようにするかそうしないかでは回数的には一緒だなってことになる。
ならない？

回数求まったら、1の手前まで6,6,3みたいに進んでたのを3,6,6にすれば良いので、今度は再帰的の逆に一番短い[0*a][1*b][0*c]から増やして考えていくと、難しそうだなーってなる。
短い列から考えていくの再帰的って言うのか？
難しそうだなーってなりながらも、後ろから大きくすれば良いんだなと気付けた。
ってこれさっきやったやないかーいってことで、後ろからなるべく多く進めば良いと。

本番思いつけるならこの解法の可能性が高いが、この貪欲法よりもグラフ的な解法の方が勉強になるなぁと感じた。
マスXから行けるマスはX+1～X+Mなので、Xからそれぞれに辺を張ったグラフとして考え、各頂点からゴールまでの最短経路を考える。
ここまで考えられたらRMQ使えそうっていうのは分かる。
辞書順最小にしたいので、振る回数が最小になるものの中から一番手前にあるものを選んでいく。

この既にある情報を使ってグラフを作成する、というのはかなり身につけたい内容。
ABC143 E Travel by Carでも出てきたテクニックで、次のレベルに進む第一歩という気がしている。

ちなみにEでも軽く解説を読んでるが、参加したコンテストが終了した後は解けた解けてないもうすぐ解けそうに関わらずとりあえず軽く解説を読むことにしている。
結局時間内に解ききらなければいけないので、このレベルの考察をするためにはこの問題のこの部分が無駄だったという感覚を磨きたいから。
今の所ミスが無駄だったで終わってるのが悲しいところ。


そんな感じでまた3完。
今回のDのミスは二度としないという誓いのために個別に記事を書きます。
はー悔しい。

差分: +175

5完
申し訳程度に初5完。
申し訳程度に初水色パフォーマンス。
申し訳程度に緑になった。
Eで終了5分前にTLE3回出して終了17秒前に提出したのがAC。
ジャッジ中に終了通知が来て焦った。
EはACしたものの、いわゆる嘘解法ってやつな上にその嘘解法も未完成。
未完成なのは提出段階から分かっていたが、その部分直すのは時間間に合わ無さそうだったので、出さないよりも出した方がワンチャン！と思ったら通ってしまった。
後で(嘘解法を落とすのとは別の)ダメそうなテストケース考えてチェックしたら普通に間違ってる。

A問題

かんたん。
でも最後の中括弧間違えて消して提出しちゃってCE。
焦って再提出したのは次解くぞと開いていたB問題用のファイル。
つまりテンプレートをそのまま提出してしまった。
CEはジャッジに時間かかるし、テンプレートも入力形式も合ってなくてジャッジに時間かかるし、無駄に時間潰した+WA。
かなり凹んだ。

B問題

かんたん。

C問題

焦ったからなのかちょっと理解できなかったけど10分くらいでAC。
サンプルケース使って解くのはもはやただのパズル。
最初は以下のように考えていた。
町iから町jへの行き方はN-1通り。
それらは全て同じ確率のはずだから、iを固定してjをN-1回ループし、それぞれの距離の合計をN-1で割ったものをsumに足す。
町iをN回ループした後のsumが答え。
でも答えが合わない。
N-1で割るんじゃなくてNで割るようにしたらサンプル全部と合ってAC。

D問題

方針はすぐ立ったのに解き方がアホ。
解説PDFと同じように、n+2m=X, 2n+m=Yの連立方程式を立てた。
なんなら変数名まで同じだった。
そこからnを全探索した(?)。
どう考えても不定形の連立方程式じゃないので、解は一意に定まるはずである。
でも答えが何通りでMOD取るってことは、不定形のパラメータ付きの解になるんじゃないかと思い込み、nを1からXまで全探索した。
もちろんオーダーは計算して全探索にしたのだが、連立方程式を立てた意味が皆無である。
しかもひどいことに、係数2がかかる部分を勘違いして実装していて、全然気づかずに方針が間違っているのかと15分以上溶かした。
連立方程式活用してたらこんなことには・・・。
これ解いた時点で45分+1WA。

E問題

本番ACコード - スーパー嘘解法
スーパー嘘解法修正版(正しい嘘解法)

問題の嘘解法。
特に工夫するところも見つからず単純だけど難しいなぁという印象。
またお得意の問題理解ミスなのだが、「T-0.5分後以降に注文できない」を、「T+0.5分後までなら注文できる」と思い込んでいた。
もはや無茶苦茶である。
それに気付いたのが終了15分くらい前で、実装が大きく変化することはなかったものの、細かい部分はおかしかったり無理矢理だったりする。
無駄なソートをしていたり謎にdp[T]の値を使っていたり。
TLEしてるんだからせめてソート部分は消すべきだった・・・。
まずちょっとミスがあった状態でTLE(残り5分)。
ミス直して(時間に関わる部分は直していないので当然だが)TLE。
setをunorderd_setに直して、ソートされていないことに関わる部分も直してTLE。
unorderd_setの代入部分を参照変数に直してAC(残り17秒)。

以下色々書いて修正したけどそもそも方針が間違いだったというお話。
この嘘解法がTwitterでも報告されていたが、自分はその嘘解法すら未完成だった・・・。
未完成のスーパー嘘解法を嘘解法に昇華させる謎の考察だが、せっかく書いたので残しておく。
一番最初に考えたのは、「最後に注文する料理を決めてそれぞれに最大値求めたい！」というお手本のような方針だったのになぜこうなったのか・・・。

方針としてはDP。
dp[i分まで] = pair{おいしさの最大値, 今まで食べた料理の種類}
おいしさの種類がsetからunorderd_setに変えた部分。
iを0~T-1まで計算した後、全てのiに対して、dp[i]のおいしさの最大値+まだ食べていない料理の最大値を調べ、それの最大値が答え。
全体的には間違っていない(と思う)のだが、同じおいしさの時の処理をしていないのがダメ。
(2分, おいしさ2), (2分, おいしさ2), (4分, おいしさ4)という3つの料理があった場合、4分でおいしさ4を得る方法は、0,1番目を選ぶ方法と2番目のみを選ぶ方法があるが、最後に1つ好きなものを足せることを考えた場合、前者は+4できて後者は+2しかできないので、前者を選ぶべきである。
同じ美味しさだと処理しない実装なので、先に2番目が選ばれてていると間違えてしまう。
例えば、嘘解法のコードに[3 5 2 2 2 2 4 4]を入力すると誤った答えが出力される。(正:8, 誤:6)
これを解決するには、まだ選んでいない料理のおいしさの最大値を持てば良い。
が、それを確認するにはO(N)かかって辛いので、選んだ料理のおいしさの最大値を持つと良さそう。
選んだ料理のおいしさの最大値が小さい方が最後においしさが大きい料理を取れる。

あるいは、dpの情報を増やす代わりに、おいしさの小さい順にソートするのも良さそう。
こちらはあまり自信がないが、おいしさが小さい方から見るようにすれば、おいしさの合計値が同じ時に更新しなかった場合、おいしさが小さい料理が積極的に使われているはずである。
例えばおいしさ1,2,2,3,4,7からおいしさ7を作りたい場合、遷移をdp[i]=max(dp[i], dp[i-料理jの時間]+料理jのおいしさ)とする。
2を作る場合は、2のみ。
3を作る場合は1+2のみ。
4を作る場合は3+1が優先されるが、3には1が使われているので2+2。
5を作る場合は4+1が優先されて4+1。
6を作る場合は5+1が優先されるが、5には1が使われているので4+2を見るが、4には2が両方とも使われているので、3+4。
7を作る場合は、6+1が優先されるが、6には1が使われているので5+2を見るが、5には2が両方とも使われているので、4+3。
・・・とここまで書いて、使われているかどうかで優先されても選ばれないかもしれない可能性がありそうなので、うまく行かなさそうな感じがする。
ちょっとその辺の証明できるほどの実力はまだない。
素直に最大値持つことにする。
と言っても嘘解法でACしてしまっているので本当に正しいか分からない。
※正しくないです

F問題

ちょっと見たけど問題文の理解するよりE考えたほうが良さそうと思った。


初めて嘘解法って奴を通してしまった。
初の5完が嘘解法はちょっと嫌だなぁ。
実質4完である。
うまく行かないだろうなと気付いたものの、時間的に厳しそうでそのまま突っ走ってしまった。
Dの勘違いのタイムロスがなければ、最大値を持った正しい嘘解法はできてそう。

新ABC制覇してかなりコツ掴んできた感あったんだけどうまくいかないなぁ。
目下の目標は全体的な速度アップと間違った思い込みをなくすことだ。
今回嘘解法で不本意に緑になったが、その緑すら落とすようなことはないようにしたい。

差分: +39

4完
Dに時間がかかりすぎた。
苦手だったわけではないが、単純に舐めていた。
真剣に解いていたつもりだけど真剣じゃなかったというのかな・・・。
後50分は縮められたはず。

A問題

かんたん。

B問題

かんたん。

C問題

相当悩んだ。
なるべく差が小さい2つの値の積でNを表せれば良いというまではすぐ分かった。
「同じ周の長さの長方形なら面積を最大にできるのは正方形である」というのはなぜか昔から何度も考えたことがあったので、この方針に疑いはなかった。
ただそれを全く実装できない！
とりあえずNを素因数分解して、あとはその組み合わせの積でなるべく差が小さくなるようにする、ナップサック問題的な問題なんじゃないか？とずっと考えていた。
でもそうするとおそらく間に合わないし、そもそもC問題レベルではないと思ったのでそういう解き方ではないと考えた。
あるときふと思いついた、「√Nから探索始めればいいじゃん！」と。
頭カチカチって感じ。
かなりの長時間考えていた気がするが、改めて確認してみると意外と20分しかかかっていなかった。
ここまで24分。

D問題

これ解くのにおよそ1時間！遅い！
算数の問題だな！と思って紙とペンで頑張ってみたのだが全く進まない。
小学生時代相当頭良かったので解けるだろうと高をくくっていたので解いている途中ずっとショックとも戦っていた。
"数学"ではなく"算数"だと完全に認識してしまっていたので、三角関数なんていう概念はなかったのが敗因。
なんとかして相似とか合同とかで解こうとしていた。
角度が30°とか45°とかで固定で、どれだけ溢れるでしょうとかが算数の問題で、サンプルの回答に無限小数らしき実数が出てくる時点で三角関数が出てくるのは明白だ。
サンプルを見るのが遅すぎたのもよくない。
なんならサンプルを見た後にも、今までの算数の思考が残りすぎて、「無限小数？なんで？どうやって出てくるの？長さの掛け算割り算で角度がそんなことになる？」となかなか理解できなかった。
それもあって三角関数使えると気づいてからもすんなりいかなかったが、それでも10分程度でACまで持っていけたと思う。
二分探索でも解けるみたいだが、角度ごとに溢れるかどうか計算できるならそんな遠回りせずに普通に最大角度求められるんじゃないか？と思う。
深く考えていないが、溢れるかどうかだけでも条件分岐が必要とは書かれていたものの、直接求めるよりは単純に計算できるんだろうか。
これを解いた時点で82分。
さすがにきつい。

E問題

Dを解けるはずという確信はあったので、Dを解いている途中にはちらっとしか見ていない。
18分弱で一応考えてみたが、さすがに無理だった。
消化コストAiと食べにくさFiを小×大となるようにソートするところまでは思いついたが、その先がうまくいかなかった。
完食にかかる時間XとFiのペアーをsetに入れて、最も大きいものを取り出してFi減らしてまたsetに入れて～というのをやろうにも、あまりにもKが大きすぎる。
Fiの最小公倍数を求めれば、全ての人が(LCM/Fi)回修行すれば、最初のsetの順番はそのままで全ての要素がLCMだけ減る！という方針が思いついた中では一番考えている感がある。
考えている感はあるが、Fiに10^6, 10^6-1があった時点で終わってしまうのでたいぶしょうもない。
あまり解放について調べていないのだが、答えを決め打ちして二分探索するっぽい。
その解き方自体はどこかでそういうのがある見たレベルにはあるのだが、詳しくは知らないので勉強ポイント。

F問題

未だに問題すら読んでいない。


これから算数の問題っぽいものも数学の問題と心構えて解きます・・・。

最近件の3完のEを解いたのだが、何も見ずに解けてしまった。
参加したコンテストのEで想定解が新しい知識を必要としないものは一番最初だけだったので、久々に自力で解けて嬉しい。
時間的にもそんなにかからなかったので、D解けてたらEも行けたかもなあと惜しい気持ちもある。
この3完は置いておいて、少なくとも練習だとEもたまにじゃなくて安定して解けるようにならないと始まらない感じがたいぶ出てきたので、頑張って経験積んでいきたい。

差分: +106

4完
1週遅れになってしまったからコンテスト終了後急いで書いている。
風邪を押して参加したけど最低限4完できてよかった。
ちなみに月曜日から5日間熱が出て、書いている今も咳はかなりひどい。

A問題

かんたん。

B問題

全探索に苦手イメージがあるものの、問題文に全探索してねと書いてあったのですぐに分かった。

C問題

ちょっと前のFにもあったスライム問題だ！
解説見ると少し難しそうなことを書いているが、1つ前の要素が異なれば答えに+1を繰り返していけば簡単に解けた。

D問題

三角形を作れる条件を正しく把握していなかった。
風邪が悪いよ風邪が。
紙に書いて把握し直してからは5分くらいで解けたイメージ。
ここまで44分。

E問題

これは解けても良かったなぁ。
燃料1回でどこまで行くべきか、をうまく表せなかった。
AからB、BからC、CからDのルートでA→Dを1回の燃料で行けるとすると、Bまで行った場合の残り燃料と、Cまで行った場合のBで補給した場合の残り燃料と補給しなかった場合の残り燃料と、Dまで行った場合のCで補給した場合の残り燃料とBで補給した場合の残り燃料と補給しなかった場合の残り燃料と・・・と、何通りも考えないといけない！どうしよう！が終始抜けなかった。
想定回答はワーシャルフロイド2回らしいが、最短経路求めてから最短経路求めるのは意味分からんけど頭良い。
言われてみれば確かにこういう何通りも道筋があるものを解けるのが最短経路問題だ。
結局補給すればその時点で燃料はMAXになるので、補給した後にいくつか消費した分の燃料を記憶するのではなくて、前回補給した場所から次にどこで補給できるかをグラフで全て記憶すれば確かに全通りを網羅できる。
この問題は解ける可能性十分あったと思っていたが、書いていたらグラフをどういうところで使えるか本当に知っているか？と問うてる問題に見えてきた。
だとすれば、間違いなく経験不足でグラフに苦手意識のある今解けなかったのは当然かもしれない。
ワーシャルフロイドは問題を解いた経験はないものの一応知識としてはあったのだが、今回は問題を解いたかどうかの経験はあまり関係なさそうに思える。

F問題

なんか解けそうだなぁと思いながら色々考えてみたがなんか解けなさそうだなぁになった。
全ての数字を横に並べ、同じ数字があれば上に重ねていくような図を想定し、だるま落としのように下から抜いていくような考え方かなぁと思って進めてみたものの、この形だと抜ける回数までたどり着けなかった。
問題文の「選び、食べる」の言葉選びのセンス○。


今回の反省ポイントはDで理解が浅いまま進めてしまったこと。
三角形の構成条件なんて簡単やろと思ったら確かに簡単だったけど抜けてた。
やっぱり風邪が悪いよ風邪が！