いろはちゃんコンテスト Day2 解いたやつの解法

　参加しました。Day2が5/2だと思っていたので参加が遅れ、開始から約80分後に参戦しました。The 典型な問題ばかりなので勉強になりました(なったと思います)。

結果

　3完+1点の計901点で撤退(解くのにかかった時間は大体10~15min.)。最終順位は178位でした。

A問題概要

　(実質)2つの文字列の最長共通部分文字列(以下LCS)の長さ+1を求める。

A問題解法

　概要でほぼ答えを言ったようなものだが、SとTのLCSの長さを求めると自ずと答えが分かる。

　この文字列の長さを求めるのにはDPが最も都合がいい。

　dp[i][j]=S₁...S_iとT₁...T_jに対するLCSの長さとし、DPをする。典型。

　尚、DPテーブルの更新は

　dp[i+1][j+1]=

max(dp[i][j]+1,dp[i][j+1],dp[i+1][j])(S[i+1]==T[j+1])

max(dp[i+1][j],dp[i][j+1])(otherwise)

とすると嬉しくなる。

B問題概要

　(0,A)と(X,B)を結ぶ直線と(S_x,S_y)と(T_x,T_y)を結ぶ直線が交差するかを判定せよ。

B問題解法

リンク先のやつを使うと簡単。すごい!!(←は？(ただの宣伝))

github.com

C問題概要

　与えられる数列の大小関係を崩さないまま圧縮せよ。

C問題解法

　実はほぼ同じ問題がAtCoderの過去問にある。

atcoder.jp

　ほぼ同じだが出力の際に+1しないとWAになる。普通に書いた方が速いです。mapで殴りまくるとACできる。

D

　フローですか?これ。フローを書いたことがないので知りません。

E

　nCrで殴れば解けそうって思って実装したがサンプルが1つだけ合わなかったため断念。