ABC122解説がしたかった
A - Double Helix
問題の通りに実装するだけ
using System; using System.IO; namespace Contest { class Program { public void Solve() { var sc = new Scanner(); string b = sc.Next(); if (b == "A") Console.WriteLine("T"); if (b == "T") Console.WriteLine("A"); if (b == "C") Console.WriteLine("G"); if (b == "G") Console.WriteLine("C"); } static void Main(string[] args) => new Program().Solve(); } }
B - ATCoder
for文でleftを0から|S|まで回す
[left,right)がACGT文字列を満たす間rightを増やす = S[right]がACGTじゃないならbreak
答えを更新
leftをrightにする
つまりやるだけ
using System; using System.IO; namespace Contest { class Program { public void Solve() { var sc = new Scanner(); var S = sc.Next(); int ans = 0; for (int left = 0; left < S.Length; left++) { if (C(S[left])) { int right; for (right = left + 1; right < S.Length; right++) { if (!C(S[right])) break; } ans = Math.Max(ans, right - left); left = right; } } Console.WriteLine(ans); } bool C(char c) => c == 'A' || c == 'T' || c == 'G' || c == 'C'; static void Main(string[] args) => new Program().Solve(); } }
C - GeT AC
sum[i]を[0,i)の'AC'の個数とする
[l-1,r-1]の'AC'の個数は
S[l-2...i-1]が'AC'ならsum[r] - sum[l]
じゃないならsum[r]-sum[l-1]
一文字目でACが成立することはありえないので上の条件分岐なしでsum[r] - sum[l]してよさそう
using System; using System.IO; using System.Text; namespace Contest { class Program { public void Solve() { var sc = new Scanner(); int N = sc.NextInt(); int Q = sc.NextInt(); string S = sc.Next(); var sum = new int[N + 1]; for (int i = 1; i < N; i++) { sum[i + 1] = sum[i]; if (S[i] == 'C' && S[i - 1] == 'A') { sum[i + 1]++; } } var sb = new StringBuilder(); for (int i = 0; i < Q; i++) { var l = sc.NextInt() - 1; if (l > 0 && S[l] == 'C' && S[l - 1] == 'A') l++; int r = sc.NextInt(); sb.AppendLine((sum[r] - sum[l]).ToString()); } Console.Write(sb.ToString()); } static void Main(string[] args) => new Program().Solve(); } }
D - We Like AGC
メモ化再帰
...i文字で2個前がj、1個前がk、一番後ろがlで何通りか
条件を満たさないパターンは0
using System; using System.IO; namespace Contest { class Program { private int Mod = 1000000007; private int[,,,] memo = new int[101, 4, 4, 4]; public void Solve() { var sc = new Scanner(); int N = sc.NextInt(); long ans = 0; //memoを全部-1で初期化 for (int i = 0; i <= N; i++) { for (int j = 0; j < 4; j++) { for (int k = 0; k < 4; k++) { for (int l = 0; l < 4; l++) { memo[i, j, k, l] = -1; } } } } for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { for (int k = 0; k < 4; k++) { ans += C(N, i, j, k); ans %= Mod; } } } Console.WriteLine(ans); } int C(int index, int one, int two, int last) { //既に計算済み = memoが-1じゃないならmemoをそのまま返す if (memo[index, one, two, last] != -1) return memo[index, one, two, last]; if (index == 3) { if (Check(-1, one, two, last)) return 1; else return 0; } else { int res = 0; for (int i = 0; i < 4; i++) { if (Check(i, one, two, last)) { res += C(index - 1, i, one, two); res %= Mod; } } memo[index, one, two, last] = res; return res; } } //i,j,k,lがAGC文字列ならfalse //Aを0、Cを1、Gを2、Tを3とする bool Check(int i, int j, int k, int l) { if (i == 0 && j == 2 && k == 1) return false; if (i == 0 && j == 1 && k == 2) return false; if (i == 2 && j == 0 && k == 1) return false; if (i == 0 && j == 2 && l == 1) return false; if (i == 0 && k == 2 && l == 1) return false; if (j == 0 && k == 2 && l == 1) return false; if (j == 0 && k == 1 && l == 2) return false; if (j == 2 && k == 0 && l == 1) return false; return true; } static void Main(string[] args) => new Program().Solve(); } }
感想
Dで時間かかった
A 1:37 (1:37)
B 6:47 (5:10)
C 19:23 (12:36)
D 83:28 (64:05)
これはABC121解説ですか?
C - Energy Drink Collector
店をAで昇順にソート
安い順に貪欲に買っていく
D - XOR World
なので
を高速に求められればいい
２進数にしてそれぞれの桁のbitが立っているかどうか判定する
のi桁目のbitが立っている→
でi桁目のbitが立っているのが奇数個
の位が0が
個1が
個ずつループする
iが0なら
2ループ(4個)でxorが0に戻る
で
なら1、それ以外なら0
それ以外
1ループでxorが0に戻る
かつ
なら1
解説にあった
を使ったほうが楽そう
感想
30分台
Dの実装でちょっと詰まった
ABC 120 解説のようななにか
B - K-th Common Divisor
なので
から
までループ
を割り切る整数でカウンタを増やしてカウンタが
のとき出力
D - Decayed Bridges
「島」「橋」「崩落」→Union Find
から
までのループで不便さを計算→
の橋を直す
最初の不便さは
を
から行き来できる島のグループの大きさとして
の橋を直すと
が既に行き来できるなら不便さは変わらない
できないなら不便さが減る
逆に出力して橋を壊していく
「知っていれば一瞬で解けるが知らないと難しい問題」
Submission #4454612 - AtCoder Beginner Contest 120
1時間切れたがなんだかモヤモヤ
ABC 119 解説(いいえ)
A - Still TBD
4月は30日までなのでmmが4より大きいならTBD、4以下ならHeisei
B - Digital Gifts
やるだけ
許容される誤差もとそれなりに大きいのでdouble使えば気にしなくていい
心配ならdecimal使おう
不要なusingのせいで2CE
C - Synthetic Kadomatsu
とNが小さいので全探索
N桁の4進数で0が不使用、1,2,3がA,B,Cに使う
D - Lazy Faith
から東西に一番近い(神社 or 寺)に行く。そこから一番近い(寺 or 神社)を探す
東西で2パターン、最初に行くのが神社 or 寺で2パターンある
一番近い寺社は2分探索で探す
...のは思いついたが3RE1WA
なので余裕を持って一番近い社寺から西に5、東に4それぞれ10(社,寺)から最寄りの寺社の東4西5を調べた
はみ出すところはcontinue;
Submission #4375306 - AtCoder Beginner Contest 119
感想
今回のDみたいな問題苦手すぎる
慣れなければ
今日の精進
ABC010 D - 浮気予防
問題URL https://atcoder.jp/contests/abc010/tasks/abc010_4
解説
nodeが個
の無向辺、
の有向辺のグラフで最小カット
入力周りで10REした
Gが0のときpの行は改行のみになるらしい
自分で実装したFord–Fulkersonで3TLE
camypaperさんの競プロライブラリを使わせてもらった
https://bitbucket.org/camypaper/complib
すごいかんたん
ABC 118 解説(感想)
B - Foods Loved by Everyone
問題URL https://atcoder.jp/contests/abc118/tasks/abc118_b
長さMの配列でその食べ物が好きな人が何人いるかをカウントする
カウンタがNの食べ物の個数を出力すればいい
C - Monsters Battle Royale
問題URL https://atcoder.jp/contests/abc118/tasks/abc118_c
ユークリッドの互除法的な操作をするので答えはAの最大公約数
D - Match Matching
問題URL https://atcoder.jp/contests/abc118/tasks/abc118_d
使える数のうち使うマッチが最小の数(使う数が同じときは数が大きいもの)をできるだけ並べてあまりをどうにかしようとしたができなかった
とNが小さいのでメモ化再帰
で
dp[i][j] をi本のマッチを使って表現できる最大の数、 jをdp[i][j]個使用すると見て長さ10の配列(1~9を使用)として持っておく
i-match(j)が探索済みの時dp[i-match(j)]の参照渡しをしてしまってメモの値まで変わるところで躓いた
時間内に提出できず
解説見ずに解けたからセーフ
感想
400点程度で躓いてしまった
何をとち狂ったのか録画して参加していたのだがかっこ悪いので公開はしない後悔はしている
TwitchでのMinecraftのModpack導入方法
タイトルの通りです
WindowsでMinecraftが既にインストールされている前提です
https://app.twitch.tv/downloadでTwitchのインストーラーをダウンロード
インストーラーを起動し、「インストールする」をクリック
インストールが終わるとTwitchが起動します
アカウントを持っている場合ログイン、持っていない場合サインアップ
ログインするとこうなる
「Mods」をクリック
「Minecraft」をクリック
「インストールする」をクリック
まだ何もありません
「すべてのModパックを参照する」をクリック
遊びたいModpackを探します
今回は「All the Mods 3」を選びました
遊びたいModpackをマウスオーバーすると「インストールする」と出るのでクリック
インストールが始まるので終わるまで待ちましょう
マイModパックに戻るとインストールしたModpackが追加されています
遊びたいModpackの「再生する」をクリック
Minecraftのランチャーが起動するのであとは通常のプレイと同じです
よいMinecraftライフを
