結果
問題 | No.1376 Simple LPS Problem |
ユーザー |
![]() |
提出日時 | 2020-11-07 13:39:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 240 ms / 2,000 ms |
コード長 | 1,064 bytes |
コンパイル時間 | 3,105 ms |
コンパイル使用メモリ | 194,404 KB |
最終ジャッジ日時 | 2025-01-15 21:29:49 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h> using namespace std; // バックトラッキングで力まかせに探索 // S[i]を終端とする長さkの文字列が回文でなければtrueを返す bool not_palindrome(int i, int k, string &S) { int l = i - k + 1; int r = i + 1; for (int j = 0; j < r - l; ++j) { if (S[l + j] != S[r - j - 1]) { return true; } } return false; } // バックトラッキングにより条件を満たすSを構築する // S[i]に0または1をセットし、S[i]を終端とする長さK+1の部分文字列とS[i]を終端とする長さK+2の部分文字列が回文でなければi+1へ進む bool f(int i, string &S, int K) { if (i == S.size()) { return true; } for (int j = 0; j <= 1; ++j) { S[i] = '0' + j; if (not_palindrome(i, K + 1, S) and not_palindrome(i, K + 2, S) and f(i + 1, S, K)) { return true; } } return false; } int main() { int N, K; cin >> N >> K; string S(N, '0'); if (f(K, S, K)) { cout << S << endl; } else { cout << -1 << endl; } }